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

Why does Java's Arrays.sort method use two different sorting algorithms for different types?

提问by zjffdu

Java 6's Arrays.sortmethod 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?

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

采纳答案by Michael Borgwardt

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.

最可能的原因：quicksort不稳定，即相等的条目在排序过程中可以改变它们的相对位置；除此之外，这意味着如果你对一个已经排序的数组进行排序，它可能不会保持不变。

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.

OTOH，不对原始类型使用 (guaranteed n*log(n)) 稳定归并排序的一个原因可能是它需要对数组进行克隆。对于引用类型，被引用的对象通常比引用数组占用更多的内存，这通常无关紧要。但是对于原始类型，完全克隆数组会使内存使用量增加一倍。

回答by msw

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.

我能想到的一个原因是快速排序的最坏情况时间复杂度为 O( n^2) 而归并排序保留最坏情况时间为 O( n log n)。对于对象数组，有一个公平的预期，即会有多个重复的对象引用，这是快速排序最差的一种情况。

There is a decent visual comparison of various algorithms, pay particular attention to the right-most graph for different algorithms.

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

回答by kukido

I was taking Coursera class on Algorithms and in one of the lectures Professor Bob Sedgewick mentioning the assessment for Java system sort:

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

"If a programmer is using objects, maybe space is not a critically important consideration and the extra space used by a merge sort maybe not a problem. And if a programmer is using primitive types, maybe the performance is the most important thing so they use quick sort."

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

回答by Will Byrne

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.

根据此答案中引用的 Java 7 API 文档，Arrays#Sort()对象数组现在使用TimSort，它是MergeSort和 InsertionSort 的混合体。另一方面，Arrays#sort()对于原始数组，现在使用Dual-Pivot QuickSort。这些更改从 Java SE 7 开始实施。

回答by David McManamon

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.

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

回答by Dinesh Kumar

java.util.Arraysuses quicksortfor primitive types such as int and mergesortfor objects that implement Comparableor 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 mergesortmaybe's not a problem and if the programmer's using primitive types maybe performance is the most important thing so use the quicksort.

java.util.Arrays对原始类型使用快速排序，例如 int 和mergesort用于实现Comparable或使用Comparator 的对象。使用两种不同方法的想法是，如果程序员使用对象，那么空间可能不是一个非常重要的考虑因素，因此归并排序使用的额外空间可能不是问题，如果程序员使用原始类型，那么性能可能是最重要的，所以使用在快速排序。

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

资料来源：信息