Java中原始数组的快速排序与归并排序比较

Question

我知道Java的Arrays.sort方法在对对象数组（或对象集合）进行排序时使用MergeSort，因为它是稳定的；在对原始数据类型数组进行排序时，Java使用QuickSort，因为我们不需要稳定性，即两个相等的int是无法区分的，即它们的身份无关紧要。

我的问题是，在处理原始数据类型时，为什么Java不使用MergeSort保证的O(n log n)时间，而选择了平均O(n log n)时间的QuickSort？在相关答案之一的最后一段中here，解释了这一点：

对于引用类型，所引用对象通常占用的内存远大于引用数组，这通常并不重要。但对于原始数据类型来说，克隆数组会直接使内存使用量翻倍。

这是什么意思？克隆引用仍然至少与克隆原始类型同样昂贵。除了上述原因外，是否还有其他使用QuickSort（平均O(n log n)）而不是使用MergeSort（保证O(n log n)时间）在原始数据类型数组上的原因？

- qrius

Answer 1

并非所有的O(n log n)算法具有相同的常数因子。在99.9%的情况下，快速排序所需的n log n时间比归并排序更快。我不知道确切的乘数--它会因系统而异--但是，例如，在平均情况下，快速排序可以比归并排序快两倍，并且仍然具有理论最坏情况n^2的性能。

此外，快速排序不需要在第一次克隆数组，而归并排序则必须这样做。但是，如果您想要稳定的排序，则对于引用类型，您别无选择，必须接受复制，但是对于原始类型，您不需要接受该成本。

- Louis Wasserman

Answer 2

复制引用仍然至少与复制原始数据一样昂贵。大多数（或全部？）Java实现将对象数组实现为对象指针（引用）的数组。因此，如果对象的大小大于指针（引用），则克隆指针（引用）数组将消耗比克隆对象本身更少的空间。

我不知道为什么使用了“克隆”这个术语。归并排序分配第二个临时数组，但该数组并不是原始数组的“克隆”。相反，适当的归并排序会根据自底向上的迭代或自顶向下的递归级别交替从原始数组到临时数组或从临时数组到原始数组方向合并。

根据我在网上搜索到的信息，Java的双轴快速排序跟踪“递归”，如果递归深度过大，则切换到堆排序以保持O(n log(n))时间复杂度，但成本因素更高。

快速排序与归并排序之间的对比。

除了稳定性之外，归并排序在对指向对象的指针（引用）数组进行排序时可能更快。与快速排序相比，归并排序移动更多指针，但比较被解引用指针访问的对象较少。在一个具有16个寄存器（大部分用作指针）的系统上，例如64位模式下的X86，4路归并排序与常规快速排序的速度大致相同，但我不记得在常见库中看到过4路归并排序，至少不是针对PC。

- rcgldr

Answer 3

Arrays#sort(primitive array) 不使用传统的快速排序算法，而是使用Dual-Pivot Quicksort，它比快速排序更快，而快速排序又比归并排序更快，部分原因是它不需要稳定性。

从javadoc中可以得知：

实现说明：排序算法是Vladimir Yaroslavskiy、Jon Bentley和Joshua Bloch创建的Dual-Pivot Quicksort。对于许多导致其他快速排序降级为二次方性能的数据集，该算法提供了O(n log(n))的性能，并且通常比传统（单枢轴）Quicksort实现更快。

- Bohemian

Answer 4

• 快速排序在随机数据上大约比归并排序快40％，因为它需要更少的数据移动。
• 快速排序只需要O（1）额外空间，而归并排序需要O（n）。

P.S. 经典快速排序和归并排序都没有被用于Java标准库中。

- ZhekaKozlov