0

如果我有两个数字列表，为了能够获得单个排序列表，我应该先对单个数字进行排序然后进行合并排序，还是应该将两个列表合并为一个列表，然后应用有效的排序算法?

4

2 回答 2

3

无论哪种方式，您都可以提出论点；这取决于许多因素：

列表 A 和 B 的选项是：

  1. 排序（A 连接 B）
  2. 合并（排序（A），排序（B））

如果 A 和 B 几乎都已排序且大小相似，那么可以在两者上都执行在几乎已排序的列表上快速运行的操作，例如插入排序。然后你进行合并，这需要线性时间，使选项（2）接近线性。但在这种情况下，如果每个列表中的值范围相似，则选项 (1) 根本不会好，给你留下可能 O(n log n) 的东西，假设你的值不适合基数或计数种类。也就是说，对于许多排序算法，较长的列表会受到伤害，因为数据移动的距离更长。

现在我们可能会想出选项（1）更好的情况。

但是，如果您发现选项 (2) 在您的情况下总是更好，这并不意味着您应该天真地应用递归拆分和合并方法，因为这样做会产生开销。

但就像所有关于“哪种排序方法更好”的问题一样，你真的必须看看：

  • 列表的大小
  • 列表中值的范围（最小值，最大值）（因为在某些情况下可以使用 O(n) 排序）
  • 无论它们是接近排序的、接近反向排序的、完全随机的还是其他
  • 是否允许、禁止外部存储器等。
  • 无论您是在内存中排序还是对文件进行排序
  • 列表的大小是否大致相同，或者一个比另一个长得多。

简而言之，“视情况而定”，但如果列表已经拆分并且您的排序算法对列表长度敏感，那么您可以从选项 (2) 中获得一些好处。

于 2012-08-04T07:04:51.130 回答
0

如果它们尚未排序，我只需将它们组合起来并进行一次排序。如果将它们分别排序然后进行合并排序更有效，那么最有效的排序算法将这样构建：任意将列表一分为二，分别排序并合并。但事实并非如此，所以......

于 2012-08-04T06:49:51.187 回答