为什么Java使用归并排序来对大于7个元素的数组进行排序

Question

根据维基百科的说法：

“在Java中，Arrays.sort()方法使用归并排序或经过优化的快速排序，具体取决于数据类型和实现效率，在排序少于七个数组元素时切换到插入排序。”

但是为什么呢？归并排序和快速排序都是O(n log n)。

- joker

---

https://dev59.com/7HA65IYBdhLWcg3wqASt - zw324

我知道Yannis会出现并因为这个事情批评我，但这可能应该在程序员上发表。 - Mike G

这里是代码作者的回答 https://dev59.com/m2Up5IYBdhLWcg3woonS - Sanghyun Lee

Answer 1

算法的不同之处在于它们的典型情况表现，而插入排序是其中最差的一种。另一方面，对于非常小的集合（n ≈ n²），插入排序的简单性胜出。

Java的算法选择规则优先选择QuickSort，只有由于特定限制条件才会回退到其他算法。QuickSort是一种不稳定的排序算法，因此仅适用于基本数据类型的排序。至于引用类型，则自OpenJDK 7起使用TimSort（以前是MergeSort）。

- Marko Topolnik

---

附加说明：插入排序在小的集合上表现更好，因为它具有较低的常数因子，而大O符号无法记录。请注意，例如：对于n < 10，n^2 < 10n。 - Bernhard Barker

@Dukeling 是的，这就是我的观点。简单意味着低常数因子。 - Marko Topolnik

Answer 2

这并不是临时抱佛脚的做法:

Arrays.java的sort方法对于原始类型的数组使用快速排序，对于对象数组使用归并排序。

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

此外，根据文档：

例如，sort(Object[])使用的算法不必是归并排序，但必须是稳定的。

再引用一句来自javadoc的话：

这种排序保证是稳定的：相等的元素不会因为排序而被重新排列。 实现说明：此实现是一种稳定的、自适应的、迭代式的归并排序，当输入数组部分排序时，需要比 n lg(n) 次比较，同时在输入数组随机排序时提供传统归并排序的性能。如果输入数组几乎排序完成，则大约需要 n 次比较。临时存储需求因接近排序的输入数组而变化很小，对于随机排序的输入数组，需要 n/2 个对象引用。 该实现在其输入数组中充分利用升序和降序，并可以利用同一输入数组的不同部分的升序和降序。它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。 该实现是从 Tim Peters 的 Python 列表排序（TimSort）中改编的。

- zw324

Answer 3

快速排序和归并排序在平均情况下都是O(n log n)。在最坏情况下，快速排序是O(n^2)。

- Andy Thomas

---

他们的平均情况不是O(n^2)，而是O(nlogn)。 - Rami Jarrar

谢谢你指出这个。我关注的是n^2最坏情况，不小心把平均情况也打成了n^2。 - Andy Thomas

Answer 4

他们转向了调整过的归并排序，因为发现在真实的部分排序数据集上，从统计学角度来看，这种方法可能比快速排序稍微快一些。

- AlexR

---

Java从未对基本类型使用MergeSort，也从未对引用类型使用QuickSort。 - Marko Topolnik

他们是谁？请提供参考资料。 - zw324

这是用于Collections.sort的。同时，它也被称为快速排序。尽管如此，我相信主要原因仍然是稳定性。 - zw324

Answer 5

Java 7使用Timsort - 一种合并和插入的混合排序算法。实际上，它被广泛使用 - 安卓、Octave和Python也在使用它。 http://en.wikipedia.org/wiki/Timsort

- Struggler