algorithm - 合并排序数组和未排序数组

Question

将已排序的数组与未排序的数组合并，得到最终的排序数组。能不能做得更好，不是很明显的方法。

final_sorted_array=merge(sort(unsorted_array), sorted_array)

我假设合并步骤类似于合并排序中的合并步骤

我们知道任何最好的通常都受到 O(n log n) 的限制。我试图了解有序数据（了解有关数据的信息）通常在多大程度上有用。

标签： algorithmsorting

Answer 1

假设您的第一个数组称为 A1n1元素，而您的第二个数组称为 A2n2元素：

以 为代价扩展 A1 的长度并将 A2 附加到其上O(n2 + c)，其中c是一个常数。应用快速排序并以O( (n1+n2)*log(n1+n2) ). 您提到您不想要明显的方式，但是，您希望以最好的方式完成工作。这可能是最好的方法，因为它允许您仍然使用通常是最快的数据结构的常规数组（当然，这具体取决于您正在处理的任务）。

但是，另一种可能性是使 A1 成为规则数组的链表 insetad，出于分析的目的，我们将不考虑将 A1 从规则数组转换为链表的成本。因此，该方法是将 A2 的有序每个元素插入到 A1 中。插入有序的明显方法是验证 A1 的每个元素，然后决定在哪里插入，以O(n1 + c)每次插入为代价。然而，更聪明的方法是对 A1 进行二分搜索，以决定 A2 的每个元素应该插入的位置，代价是O(log(n1) + c)每次插入。在这种情况下，会有n2插入，即总成本n2*O(log(n1) + c). 在这种方法中，您不需要移动任何 A1 元素，因为我们假设您使用链表，您只需检查这些元素。这就是为什么这个渐近函数看起来更好的原因，这个数据结构让你能够只查看 A1 原始元素而不实际移动它们。

要决定应该使用哪种方法，我建议您分析数组合并后的算法，选择最适合您需要的选项。