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

最可能的原因是: 快速排序不是 稳定，也就是说，相等的条目可以在排序过程中改变它们的相对位置; 除了其他原因之外，这意味着如果对一个已经排序的数组进行排序，它可能不会保持不变。

由于基元类型没有标识(无法区分具有相同值的两个 int) ，因此这对它们来说无关紧要。但是对于引用类型，它可能会给某些应用程序带来问题。因此，对这些用户使用稳定的合并排序。

OTOH，不对基元类型使用(保证 n * log (n))稳定合并排序的原因可能是它需要克隆数组。对于引用类型，引用对象通常比引用数组占用更多的内存，这通常并不重要。但对于原始类型，直接复制数组会使内存使用量增加一倍。

我能想到的一个原因是，快速排序的最坏情况时间复杂度为 O (N ^ 2) ，而合并排序的最坏情况时间为 O (N log n)。对于对象数组，有一个公平的期望，将有多个重复的对象引用，这是一种情况下，快速排序做得最差。

有一个不错的 各种算法的可视化比较，特别注意最右边的图为不同的算法。

我参加了 Coursera 关于算法的课程，在一次讲座中 Bob Sedgewick 教授提到了 Java 系统分类的评估:

“如果一个程序员正在使用对象，也许空间并不是一个严格的 重要的考虑因素和合并排序使用的额外空间 如果程序员使用基本类型，也许 性能是最重要的，因此他们使用快速排序。”

根据 这个答案中引用的 Java7API 文档，用于对象数组的 Arrays#Sort()现在使用 TimSort，它是 MergeSort 和 InsertionSort 的混合体。另一方面，原语数组的 Arrays#sort()现在使用 双轴快速排序。这些更改是从 JavaSE7开始实现的。

Java 的 Arrays.sort方法使用快速排序、插入排序和合并排序。甚至在 OpenJDK 代码中实现了单轴和双轴快速排序。最快的排序算法取决于具体情况，获胜者是: 小数组的插入排序(目前选择了47个) ，大部分排序数组的归并排序，剩余数组的快速排序，所以 Java 的 Array.sort ()尝试根据这些标准选择最佳的应用算法。

Java.util.数组 对基本类型使用 快速排序，例如对实现 可比的或使用 比较器的对象使用 int 和 合并排序。使用两种不同方法的想法是，如果程序员使用对象或许空间不是一个非常重要的考虑因素，所以 合并排序使用的额外空间可能不是一个问题，如果程序员使用基本类型或许性能是最重要的事情，所以使用 快速排序。

例如: 这是排序稳定性至关重要的示例。

这就是为什么稳定排序对于对象类型是有意义的，特别是可变对象类型和数据多于排序键的对象类型，而合并排序就是这样一种排序。但对于原语类型，稳定性不仅是无关紧要的。毫无意义。

资料来源: 信息