Java中基元数组的QuickSort vs MergeSort
我知道Java的Arrays.sort方法使用MergeSort对对象数组（或对象集合）进行排序，因为它是稳定的，而且Java使用QuickSort用于基元数组，因为我们不需要稳定性，因为两个相等的整数是不可区分的，即它们的身份无关紧要。
我的问题是，在基元的情况下，为什么Java不使用MergeSort保证的O（n log n）时间，而是使用QuickSort的平均O（n log n）时间？ 在这里相关答案的最后一段中，解释说：
对于引用类型，通常引用的对象比引用数组占用的内存要多得多，这通常不重要。 但对于原始类型，彻底克隆该阵列会使内存使用量翻番。
这是什么意思？ 克隆引用仍然至少与克隆基元一样昂贵。 在基元数组上使用QuickSort（平均O（n log n））而不是MergeSort（保证O（n log n）时间）是否还有其他原因？
并非所有的O（n log n）算法都具有相同的常数因子。 Quicksort在99.9％的情况下需要n log n时间，比mergesort运行速度快得多。 我不知道确切的乘数 - 它会根据系统而改变系统 - 但是，比方说，quicksort平均运行速度是合并排序的两倍，仍然存在理论上最坏的n ^ 2性能。
另外，Quicksort不需要首先克隆数组，合并排序不可避免。 但是如果你想要一个稳定的排序，你就没有选择引用类型的选择，所以你必须接受这个副本，但是你不需要接受基元的成本。
Arrays#sort(primitive array)不使用传统的快速排序; 它使用Dual-Pivot Quicksort，它比快速排序更快，而快速排序又快于合并排序，部分原因是它不必稳定。
从javadoc：
实现注释：排序算法是由Vladimir Yaroslavskiy，Jon Bentley和Joshua Bloch编写的Dual-Pivot Quicksort。 该算法在许多数据集上提供O（n log（n））性能，这些数据集导致其他快速排序降级为二次性能，并且通常比传统的（单枢纽）Quicksort实现更快。
克隆引用仍然至少与克隆基元一样昂贵。
Java的大多数（或全部）实现都将对象数组实现为对象的指针（引用）数组。 因此，如果对象的大小大于指针（引用），那么克隆指针数组（指针）会比克隆对象本身占用的空间更少。
我不知道为什么使用“克隆”这个词。 合并排序分配第二个临时数组，但该数组不是原始的“克隆”。 取而代之的是一种适当的合并排序方式，将合并的方向从原始方式转换为温度方式，或者从温度方式转换为原始方式，具体取决于自下而上的迭代，还是取决于自上而下的递归级别。
双枢轴快速排序
根据我所能做的网页搜索，Java的双枢轴快速排序跟踪“递归”，并在递归深度过大时切换到堆排序，以维持O（n log（n））的时间复杂度，但在更高成本因素。
快速排序与合并排序
除了稳定性之外，合并排序可以更快地将指向数组的指针（引用）排序为对象。 合并排序可以执行更多的（指针的）移动，但比通过快速排序更少的比较（通过取消引用指针访问的对象）。
在具有16个寄存器（大部分用作指针）的系统上，如64位模式下的X86，4路合并排序的速度与普通快速排序速度一样快，但我不记得看到4路合并在一个共同的图书馆里排序，至少不能用于个人电脑。
链接地址: http://www.djcxy.com/p/31587.html