为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法?
Java 6 的 Arrays.sort 方法对基元数组使用快速排序,对对象数组使用合并排序。我相信大多数时候快速排序比合并排序更快并且消耗更少的内存。我的实验支持这一点,尽管两种算法都是 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?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(6)
根据 这个答案中引用的 Java 7 API 文档,对象数组的 Arrays#Sort()
现在使用 TimSort,它是归并排序和插入排序的混合体。另一方面,原始数组的 Arrays#sort() 现在使用 双枢轴快速排序。这些更改从 Java SE 7 开始实施。
java.util.Arrays 对基本类型(例如 int)使用 quicksort,对实现 Comparable 或使用的对象使用 mergesort一个比较器。使用两种不同方法的想法是,如果程序员使用对象,空间可能不是一个至关重要的考虑因素,因此 mergesort 使用的额外空间可能不是问题,如果程序员使用基本类型可能会影响性能是最重要的,所以使用快速排序。
例如:
这是排序稳定性很重要的例子。
就是为什么稳定排序对于对象类型有意义,尤其是可变对象类型和具有比排序键更多数据的对象类型,而归并排序就是这样一种排序。但对于原始类型来说,稳定性不仅无关紧要。这是没有意义的。
资料来源: 信息
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
最可能的原因:快速排序不稳定,即相等的条目在排序过程中可能会改变它们的相对位置;除此之外,这意味着如果对已经排序的数组进行排序,它可能不会保持不变。
由于原始类型没有标识(无法区分具有相同值的两个 int),因此这对它们来说并不重要。但对于引用类型,它可能会给某些应用程序带来问题。因此,对于这些,使用稳定的合并排序。
OTOH,不对原始类型使用(保证 n*log(n))稳定合并排序的一个原因可能是它需要对数组进行克隆。对于引用类型,引用的对象通常比引用数组占用更多的内存,这通常并不重要。但对于原始类型,直接克隆数组会使内存使用量增加一倍。
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, 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.