根据维基百科：
“在 Java 中，Arrays.sort() 方法根据数据类型使用合并排序或调整的快速排序，并且当排序的数组元素少于七个时，为了实现效率切换到插入排序”
但为什么？合并排序和快速排序都是O(n log n)。
问问题
1832 次
5 回答
10
算法不同的地方在于它们的典型案例行为，这就是插入排序是最糟糕的地方之一。另一方面，对于非常小的集合 (n ≈ n 2 )，插入排序的简单性获胜。
Java 的算法选择规则优先选择 QuickSort，并且由于特定限制而只回退到其他东西。即 QuickSort 是一种不稳定的排序，因此仅适用于基元的排序。对于引用类型，从 OpenJDK 7（以前的 MergeSort）开始使用 TimSort。
于 2013-05-16T12:43:20.010 回答
1
这不是特别的：
Arrays.java 的排序方法对基元数组使用快速排序，对对象数组使用合并排序。
为什么 Java 的 Arrays.sort 方法对不同的类型使用两种不同的排序算法？
此外，根据文档：
例如，sort(Object[]) 使用的算法不必是归并排序，但它必须是稳定的。
还有来自 javadoc 的另一个引用：
这种排序保证是稳定的：相同的元素不会因为排序而重新排序。
实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要的比较次数远少于 n lg(n)，而当输入数组是随机排序时，它提供了传统归并排序的性能。如果输入数组接近排序，则实现需要大约 n 次比较。临时存储要求从几乎排序的输入数组的小常数到随机排序的输入数组的 n/2 对象引用不等。
该实现在其输入数组中同等地利用升序和降序，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。
该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。
于 2013-05-16T12:41:55.660 回答
1
快速排序和归并排序的平均性能都是 O(n log n) 。在最坏的情况下，快速排序是 O(n^2)。
于 2013-05-16T12:45:49.517 回答
0
他们转向调整合并排序，因为从统计上发现，对于实际部分排序的数据集，这种方法可能比快速排序快一点。
于 2013-05-16T12:43:08.950 回答
0
Java 7 使用 Timsort - 合并和插入的混合体。事实上，它被广泛使用——android、Octave、python 也使用它。 http://en.wikipedia.org/wiki/Timsort
于 2013-10-15T11:56:11.137 回答