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

Question

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

Answer 1

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

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

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

Answer 2

根据本答案中引用的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)的最坏情况时间.对于对象数组,可以期待存在多个重复对象引用,这是快速排序最差的一种情况.

各种算法都有一个不错的视觉比较,特别注意不同算法的最右边的图形.

Answer 4

我在 Coursera 上的算法课和 Bob Sedgewick 教授的一次讲座中提到了 Java 系统排序的评估：

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