Q-R*_*IUS 8 java arrays sorting mergesort quicksort
我知道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) 算法都具有相同的常数因子。在 99.9% 需要 n log n 时间的情况下，快速排序的运行速度比归并排序快得多。我不知道确切的乘数——它会因系统而异——但是，比如说，快速排序的平均运行速度可以是合并排序的两倍，并且理论上仍然具有最坏情况 n^2 的性能。
此外，快速排序首先不需要克隆数组，而归并排序不可避免。但是如果你想要一个稳定的排序，你就没有选择引用类型，所以你必须接受副本，但你不需要接受原语的成本。