1

假设我有一些我知道已经排序的集合，例如 {0,2,10,23,65} 和 {3,5,8..}。可以将任意数量的预排序集组合成一个排序集的最佳排序算法是什么？这种排序的效率如何？

4

3 回答 3

4

你不需要对它们进行排序，你需要合并。这是通过O(M+N)使用一个简单的循环来完成的，该循环保持两个索引查看两个部分的当前元素，将两者中较小的一个添加到最终序列中，并将索引推进一个。

这是伪代码：

int[] parts1, parts2 // Sorted parts
int i = 0, j = 0;
while i != parts1.Length || j != parts2.Length
    if i != parts1.Length || j != parts2.Length
        if parts1[i] < parts2[j]
            res.Add(parts1[i++])
        else
            res.Add(parts2[j++])
    else if i != parts1.Length
        res.Add(parts1[i++])
    else
        res.Add(parts2[j++])

在每一步，循环都会前进i或j，执行parts1.Lenght + part2.Length次数。

于 2012-05-09T23:41:59.213 回答
2

最简单的方法是比较您拥有的列表的头部，取最小的一个，并将其添加到排序集中。重复直到所有列表都为空。

效率方面，它总是在时间上是线性的。这将花费您必须合并的项目总数。

这实际上是Mergesort的第二阶段。

于 2012-05-09T23:43:16.217 回答
1

假设集合中有O(n)元素O(k)。一个标准的合并将是O(n * k).

如果你只有 2 套，这没什么大不了的。如果你有1000个，它可能是。在这种情况下，您可以保留按其下一个最小元素组织的集合的优先级队列。这个变种是O(n log(k)).

于 2012-05-10T07:26:15.093 回答