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

Question

Java 6 的 Arrays.sort 方法会根据数组的类型使用快速排序或归并排序。虽然这两种算法都是 O(n log(n))，但我认为大多数情况下快速排序比归并排序更快且需要更少的内存。我的实验支持了这一点。那么为什么 Java 会为不同类型的数组使用不同的算法呢？

- zjffdu

---

快速排序的最差情况时间复杂度是N^2，而不是NlogN。 - codaddict

等等，如果你有一个 Integer 数组或者其他什么类型的数组呢？ - Tikhon Jelvis

你读的源代码里难道没有解释吗？ - Humphrey Bogart

这份信息已经不再最新。自Java SE 7开始，MergeSort被替换为TimSort，QuickSort被替换为双轴快速排序(Dual-Pivot QuickSort)。请查看下面我的答案中提供的Java API文档链接。 - Will Byrne

请参阅 https://dev59.com/m2Up5IYBdhLWcg3woonS，JDK 7+ 请参阅 https://dev59.com/YVwY5IYBdhLWcg3wq5fl?noredirect=1&lq=1。 - rogerdpack

最近版本的C++库因此使用introsort，这是一种观察递归深度的快速排序版本，如果递归深度过深，则切换到堆排序，其最坏情况下为O(n log n)。这使得introsort在所有情况下都是O(n log n)，而不会在每种情况下都产生更大的堆排序开销。 - Dinesh Kumar

Answer 1

最有可能的原因是： 快速排序不是“稳定”的，即相等的元素在排序过程中可以改变它们的相对位置；这意味着如果你对一个已经排序好的数组进行排序，它可能不会保持不变。

由于基本类型没有身份（无法区分两个具有相同值的int），这对它们来说并不重要。但对于引用类型，这可能会对某些应用程序造成问题。因此，对于这些情况使用稳定的归并排序。

另一方面，不使用（保证n * log（n））稳定的归并排序的原因可能是它需要制作数组副本。对于引用类型，所引用对象的内存通常比引用数组的内存多得多，因此这通常并不重要。但对于基本类型，直接克隆数组会使内存使用量增加一倍。

- Michael Borgwardt

---

使用快速排序的另一个原因是，在平均情况下，快速排序比归并排序更快。尽管快速排序比归并排序进行更多的比较，但它进行的数组访问要少得多。如果输入包含大量重复条目，则三向快速排序也可以实现线性时间，这在实际应用中并不罕见（我猜双轴快速排序也具有此属性）。 - Jingguo Yao

对于原始类型，它不会克隆数组，可以就地排序，所以我认为唯一的原因是稳定性契约，基本上... - rogerdpack

Answer 2

根据这个答案中引用的Java 7 API文档，Arrays#Sort()现在用于对象数组的排序使用了TimSort算法，它是归并排序和插入排序的混合算法。另一方面，基本数据类型数组的Arrays#sort()现在使用Dual-Pivot QuickSort算法。这些变化自Java SE 7开始实施。

- Will Byrne

---

选择两种不同的算法并不是一个答案。 - Alexandr

Answer 3

我能想到的一个原因是，快速排序的最坏时间复杂度是O(n^2)，而归并排序保持了O(n log n)的最坏时间。对于对象数组来说，有很大的可能性存在多个重复的对象引用，这种情况下快速排序会表现得更差。

这里有一个不错的各种算法的可视化比较，特别注意右侧图表中不同算法的表现。

- msw

---

Java的快速排序是一种修改过的快速排序算法，它不会退化为O(n^2)。据文档所述，“该算法在许多数据集上提供了n*log(n)的性能，而其他快速排序算法则会因这些数据集而降为二次方性能。” - sbridges

Answer 4

我正在参加算法Coursera课程，在其中的一节课中Bob Sedgewick教授提到了Java系统排序的评估：

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

- kukido

---

这并不是主要原因。在这句话之后，视频中嵌入了一个关于“为什么对于引用类型使用归并排序”的问题（因为它是稳定的）。我认为Sedgewick没有在视频中提到这一点是为了留给观众提问。 - likern

Answer 5

java.util.Arrays使用快速排序算法对基本数据类型如int进行排序，使用归并排序算法对实现了Comparable接口或使用Comparator的对象进行排序。采用两种不同方法的原因是如果程序员使用的是对象，则空间可能并不是一个关键问题，因此使用归并排序算法所使用的额外空间可能不是一个问题；如果程序员使用的是基本数据类型，则性能可能是最重要的考虑因素，因此使用快速排序算法。例如：当排序稳定性很重要时，可以看下面的示例。

这就是为什么稳定排序对于对象类型特别是可变对象类型和除排序键之外还有更多数据的对象类型很有意义，而归并排序就是这样一种排序方法。但对于原始类型来说，稳定性不仅无关紧要，而且毫无意义。

来源：INFO

- Dinesh Kumar

Answer 6

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

- David McManamon