104

我们知道快速排序是最快的排序算法。

JDK6collections.sort使用归并排序算法而不是快速排序。但是 Arrays.sort 使用快速排序算法。

Collections.sort 使用合并排序而不是快速排序的原因是什么？

4

1 回答 1

199

极有可能来自 Josh Bloch §：

我确实写了这些方法，所以我想我有资格回答。确实没有单一的最佳排序算法。与归并排序相比，快速排序有两个主要缺陷：

  1. 它不稳定（如 parsifal 所述）。

  2. 它不保证n log n 性能；它可以在病理输入上降级为二次性能。

稳定性对于原始类型来说不是问题，因为没有区别于（值）相等的身份概念。对于 Bentely 和 McIlroy 的实现（或随后的Dual Pivot Quicksort ），二次行为的可能性被认为不是问题，这就是为什么这些 QuickSort 变体用于原始排序的原因。

对任意对象进行排序时，稳定性很重要。例如，假设您有表示电子邮件消息的对象，您首先按日期对它们进行排序，然后按发件人排序。您希望它们在每个发件人中按日期排序，但只有在排序稳定时才会如此。这就是为什么我们选择提供一种稳定的排序（合并排序）来对对象引用进行排序。（从技术上讲，多个连续稳定排序会导致键的字典顺序与排序相反：最终排序确定最重要的子键。）

无论输入是什么，合并排序都能保证n log n（时间）性能，这是一个很好的附带好处。当然有一个缺点：快速排序是一种“就地”排序：它只需要 log n 外部空间（以维护调用堆栈）。另一方面，合并、排序需要 O(n) 外部空间。如果输入数组几乎已排序，则 TimSort 变体（在 Java SE 6 中引入）需要更少的空间 (O(k))。

此外，以下是相关的：

java.util.Arrays.sort 和（间接）java.util.Collections.sort 用于对对象引用进行排序的算法是“修改过的合并排序”（如果低子列表中的最高元素小于高子列表中的最低元素）。” 它是一种相当快速的稳定排序，可保证 O(n log n) 性能并需要 O(n) 额外空间。在当时（由 Joshua Bloch 于 1997 年编写），这是一个不错的选择，但今天我们可以做得更好。

自 2003 年以来，Python 的列表排序使用了一种称为 timsort 的算法（以编写它的 Tim Peters 命名）。它是一种稳定的、自适应的、迭代的归并排序，当在部分排序的数组上运行时，它需要远少于 n log(n) 的比较，同时在随机数组上运行时提供与传统归并排序相当的性能。像所有适当的合并排序一样，timsort 是稳定的，并且在 O(n log n) 时间内运行（最坏情况）。在最坏的情况下，timsort 需要 n/2 个对象引用的临时存储空间；在最好的情况下，它只需要很小的固定空间。将此与当前实现进行对比，后者总是需要额外的空间来存储 n 个对象引用，并且仅在几乎排序的列表上优于 n log n。

Timsort 在此处详细描述：http: //svn.python.org/projects/python/trunk/Objects/listsort.txt。

Tim Peters 的原始实现是用 C 语言编写的。Joshua Bloch 将其从 C 语言移植到 Java 中，并对最终代码进行了广泛的测试、基准测试和调整。生成的代码是 java.util.Arrays.sort 的直接替换。在高度有序的数据上，此代码的运行速度最高可达当前实现的 25 倍（在 HotSpot 服务器 VM 上）。在随机数据上，新旧实现的速度是相当的。对于非常短的列表，即使在随机数据上，新实现也比旧实现要快得多（因为它避免了不必要的数据复制）。

另外，请参阅Java 7 是否对方法 Arrays.Sort 使用 Tim Sort？.

没有单一的“最佳”选择。与许多其他事情一样，它是关于权衡的。

于 2013-03-01T09:20:11.600 回答