为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？ [英] Why does Java's Arrays.sort method use two different sorting algorithms for different types?

问题描述

Java 6的 Arrays.sort 方法使用Quicksort作为基元数组，并对对象数组进行合并排序。我相信Quicksort的大部分时间都比合并排序更快，内存成本更低。我的实验支持这一点，尽管两种算法都是O（n log（n））。那么为什么不同的算法用于不同类型？

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

推荐答案

最可能的原因：快速排序不是稳定，即相等的条目可以在排序期间改变它们的相对位置;除此之外，这意味着如果你对已排序的数组进行排序，它可能不会保持不变。

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.

因为原始类型没有标识（没有办法区分两个具有相同值的整数），这对他们来说无关紧要。但对于参考类型，它可能会导致某些应用程序出现问题。因此，对那些使用稳定的合并排序。

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，不使用原始类型的（保证n * log（n））稳定合并排序的原因可能因为它需要克隆数组。对于引用类型，引用对象通常占用的内存比引用数组多得多，这通常无关紧要。但对于原始类型，克隆数组会使内存使用量翻倍。

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.

这篇关于为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！