为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？

Question

Java 6的Arrays.sort方法使用Quicksort作为基元数组，并对对象数组进行合并排序。我相信大多数时候Quicksort比合并排序更快，并且内存更少。我的实验支持这一点，尽管两种算法都是O（n log（n））。那么为什么不同的算法用于不同的类型呢？

Answer 1

最可能的原因：快速排序不稳定，即同等条目可以在排序期间改变其相对位置;除此之外，这意味着如果您对已经排序的数组进行排序，它可能不会保持不变。

由于原始类型没有标识（没有办法区分具有相同值的两个整数），这对它们无关紧要。但对于参考类型，它可能会导致某些应用程序出现问题。因此，使用稳定的合并排序。

OTOH，不对原始类型使用（保证n * log（n））稳定合并排序的原因可能是它需要复制数组。对于引用类型，引用对象通常占用的内存比引用数组多得多，这通常无关紧要。但对于原始类型，克隆数组会使内存使用量翻倍。

Answer 2

根据this answer中引用的Java 7 API文档，对象数组的Arrays#Sort()现在使用TimSort，它是MergeSort和InsertionSort的混合体。另一方面，原始数组的Arrays#sort()现在使用Dual-Pivot QuickSort。这些更改是从Java SE 7开始实现的。

Answer 3

我能想到的一个原因是，快速排序的最坏情况时间复杂度为O（n ^ 2），而mergesort保留了O（n log n）的最坏情况时间。对于对象数组，可以期待存在多个重复对象引用，这是快速排序最差的一种情况。

有一个体面的visual comparison of various algorithms，特别注意不同算法的最右边的图形。

Answer 4

我正在参加关于算法的Coursera课程，并在其中一个讲座中教授Bob Sedgewick提到Java系统排序的评估：

“如果程序员正在使用对象，也许空间不是一个非常重要的考虑因素，并且合并排序使用的额外空间可能不是问题。如果程序员使用原始类型，那么性能可能是最重要的，所以他们使用快速排序。“

Answer 5

Java的Arrays.sort方法使用快速排序，插入排序和合并排序。在OpenJDK代码中甚至实现了单个和双枢轴快速排序。最快的排序算法取决于具体情况，获胜者是：小数组的插入排序（当前选择47个），大多数排序数组的mergesort，以及其余数组的快速排序，因此Java的Array.sort（）尝试选择最佳算法根据这些标准申请。

Answer 6

java.util.Arrays对原始类型使用quicksort，例如int和mergesort，用于实现Comparable或使用Comparator的对象。使用两种不同方法的想法是，如果程序员使用对象可能是空间不是一个非常重要的考虑因素，那么mergesort使用的额外空间可能不是问题，如果程序员使用原始类型可能性能是最重要的，那么使用快速排序。

例如：这是排序稳定性问题的示例。

这就是稳定排序对于对象类型有意义的原因，特别是可变对象类型和具有比排序键更多数据的对象类型，而mergesort就是这样的排序。但对于原始类型而言，稳定性不仅无关紧要。这毫无意义。

资料来源：INFO