在合并排序的最后一步，我们有两个排序列表，我们试图将它们组合成一个排序列表，逻辑将如何发展？
这就是我天真的想法：获取列表#1 的每个元素并将其与列表#2 的每个元素进行比较，然后在列表#2 中找到它的位置。基本上就像插入排序。
但显然这不是它的发生方式，因为这给了我 O(n^2) 的复杂性。但是归并排序是 O(nlogn)。那么最后一步是如何发生的呢？
问问题
115 次
2 回答
1
它使用归并排序。归并排序没有单独的排序算法，它是一种排序算法。
所以你的原始列表已经排序，所以最小的元素总是在开头。比较 A 和 B。取两者中较小的一个并将其添加到结果列表的末尾。重复直到两个源列表都为空。
于 2013-08-23T14:39:39.790 回答
0
这在很大程度上取决于您如何构建要排序的数据。
合并排序往往主要用于外部排序，例如对磁盘上的文件进行排序。在这种情况下，您通常从一些输入文件中获取输入，并将结果写入单独的输出文件。
如果你对链表进行排序，你通常会做同样的事情——获取 N 个输入列表并生成一个输出列表。由于您可以通过操作链接将元素从一个列表移动到另一个列表，因此这不需要（太多）额外的存储空间或时间。
您似乎真的在询问对数组进行就地排序。如果您想就地合并排序数组，有几种已知的算法，但它们有些不重要。
[我不喜欢只使用链接到我猜是这里的真正答案，但算法真的有点多，甚至在这里概述。]
于 2013-08-23T14:47:31.443 回答