sorting - 包含已排序和未排序列表的列表的排序列表

Question

有 k 个列表，其中包含 m 个未排序的列表 (0 <=m < k)。如何将列表合并为一个也应该排序的大列表，没有提供有关已排序列表的信息。

Answer 1

假设 n 是所有列表中的总元素数。

假设此元素数量在所有列表之间平均分配，您可以执行以下操作：

• 对每个未排序的列表进行排序

• 合并所有列表中的所有元素

运行时分析：

每个列表中的元素数等于 n/k。

因此，对每个未排序的列表进行排序需要 O((n/k) log(n/k) => 对所有 m 个列表进行排序的运行时间等于 O(m (n/k)*log(n/k))。

合并部分需要 O(n)。

因此，我们得到整体运行时间 = O(n + m*(n/k)*log(n/k))。

Answer 2

您可以使用插入排序，这将是一个简单的答案。最糟糕的是它本身会运行 O(n**2)。

否则对未排序的列表进行排序（合并或快速排序）并将它们合并。根据您的 m 和 k，您可以进行一些微优化。在这里，您的复杂性将是基于 n 的 O(nlogn)。你可以弄清楚它与 k 和 m 的对应关系。

Answer 3

使用随机快速排序对未排序的列表进行排序，然后使用合并排序合并所有已排序的列表。