为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？
Java 6 的 Arrays.sort 方法对基元数组使用快速排序，对对象数组使用合并排序。我相信大多数时候快速排序比合并排序更快并且消耗更少的内存。我的实验支持这一点，尽管两种算法都是 O(n log(n))。那么为什么不同的类型使用不同的算法呢？
Java 6's Arrays.sort method uses Quicksort for arrays of primitives and merge sort for arrays of objects. I believe that most of time Quicksort is faster than merge sort and costs less memory. My experiments support that, although both algorithms are O(n log(n)). So why are different algorithms used for different types?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
最可能的原因：快速排序不稳定，即相等的条目在排序过程中可能会改变它们的相对位置；除此之外，这意味着如果对已经排序的数组进行排序，它可能不会保持不变。
由于原始类型没有标识（无法区分具有相同值的两个 int），因此这对它们来说并不重要。但对于引用类型，它可能会给某些应用程序带来问题。因此，对于这些，使用稳定的合并排序。
OTOH，不对原始类型使用（保证 n*log(n)）稳定合并排序的一个原因可能是它需要对数组进行克隆。对于引用类型，引用的对象通常比引用数组占用更多的内存，这通常并不重要。但对于原始类型，直接克隆数组会使内存使用量增加一倍。
The most likely reason: quicksort is not stable, i.e. equal entries can change their relative position during the sort; among other things, this means that if you sort an already sorted array, it may not stay unchanged.
Since primitive types have no identity (there is no way to distinguish two ints with the same value), this does not matter for them. But for reference types, it could cause problems for some applications. Therefore, a stable merge sort is used for those.
OTOH, a reason not to use the (guaranteed n*log(n)) stable merge sort for primitive types might be that it requires making a clone of the array. For reference types, where the referred objects usually take up far more memory than the array of references, this generally does not matter. But for primitive types, cloning the array outright doubles the memory usage.
根据 这个答案中引用的 Java 7 API 文档，对象数组的
Arrays#Sort()现在使用 TimSort，它是归并排序和插入排序的混合体。另一方面，原始数组的 Arrays#sort() 现在使用 双枢轴快速排序。这些更改从 Java SE 7 开始实施。According to Java 7 API docs cited in this answer,
Arrays#Sort()for object arrays now uses TimSort, which is a hybrid of MergeSort and InsertionSort. On the other hand,Arrays#sort()for primitive arrays now uses Dual-Pivot QuickSort. These changes were implemented starting in Java SE 7.我能想到的一个原因是快速排序的最坏情况时间复杂度为 O(n^2)，而归并排序保留最坏情况时间复杂度为 O(n log n)。对于对象数组，人们普遍期望会有多个重复的对象引用，这是快速排序效果最差的一种情况。
有一个不错的各种算法的视觉比较，特别注意最右边的不同算法的图表。
One reason I can think of is that quicksort has a worst case time complexity of O(n^2) while mergesort retains worst case time of O(n log n). For object arrays there is a fair expectation that there will be multiple duplicate object references which is one case where quicksort does worst.
There is a decent visual comparison of various algorithms, pay particular attention to the right-most graph for different algorithms.
我正在上 Coursera 的算法课程，在其中一次讲座中 Bob Sedgewick 教授提到了 Java 系统排序的评估：
I was taking Coursera class on Algorithms and in one of the lectures Professor Bob Sedgewick mentioning the assessment for Java system sort:
java.util.Arrays 对基本类型（例如 int）使用 quicksort，对实现 Comparable 或使用的对象使用 mergesort一个比较器。使用两种不同方法的想法是，如果程序员使用对象，空间可能不是一个至关重要的考虑因素，因此 mergesort 使用的额外空间可能不是问题，如果程序员使用基本类型可能会影响性能是最重要的，所以使用快速排序。
例如：
这是排序稳定性很重要的例子。
就是为什么稳定排序对于对象类型有意义，尤其是可变对象类型和具有比排序键更多数据的对象类型，而归并排序就是这样一种排序。但对于原始类型来说，稳定性不仅无关紧要。这是没有意义的。
资料来源： 信息
java.util.Arrays uses quicksort for primitive types such as int and mergesort for objects that implement Comparable or use a Comparator. The idea of using two different methods is that if a programmer’s using objects maybe space is not a critically important consideration and so the extra space used by mergesort maybe’s not a problem and if the programmer’s using primitive types maybe performance is the most important thing so use the quicksort.
For Example:
This is the example when sorting stability matters.
That’s why stable sorts make sense for object types, especially mutable object types and object types with more data than just the sort key, and mergesort is such a sort. But for primitive types stability is not only irrelevant. It’s meaningless.
Source: INFO
Java 的 Arrays.sort 方法使用快速排序、插入排序和归并排序。 OpenJDK 代码中甚至实现了单枢轴快速排序和双枢轴快速排序。最快的排序算法取决于具体情况，获胜者是：小数组的插入排序（当前选择 47 个）、大部分已排序数组的归并排序以及剩余数组的快速排序，因此 Java 的 Array.sort() 尝试选择最佳算法来排序根据这些标准进行申请。
Java's
Arrays.sortmethod uses quicksort, insertion sort and mergesort. There is even both a single and dual pivot quicksort implemented in the OpenJDK code. The fastest sorting algorithm depends on the circumstances and the winners are: insertion sort for small arrays (47 currently chosen), mergesort for mostly sorted arrays, and quicksort for the remaining arrays so Java's Array.sort() tries to choose the best algorithm to apply based on those criteria.