为什么Java的Arrays.sort方法对不同类型使用两种不同的排序算法?

2020/11/25 02:22 · java ·  · 0评论

Java 6的Arrays.sort方法对基元数组使用Quicksort,对对象数组使用merge sort。我相信大多数时候Quicksort比合并排序要快,而且占用的内存更少。我的实验支持这一点,尽管两种算法都是O(n log(n))。那么为什么对不同类型使用不同的算法呢?

最可能的原因是:快速排序不稳定,即相等的条目可以在排序过程中更改其相对位置;除其他外,这意味着如果您对已排序的数组进行排序,则它可能不会保持不变。

由于基本类型没有身份(无法区分具有相同值的两个int),因此这对它们无关紧要。但是对于引用类型,它可能会在某些应用程序中引起问题。因此,对于那些使用稳定的合并排序。

OTOH,不对原始类型使用(保证的n * log(n))稳定合并排序的原因可能是它需要克隆该数组。对于引用类型,引用的对象通常比引用数组占用更多的内存,这通常没有关系。但是对于原始类型,完全克隆数组会使内存使用量增加一倍。

根据此答案中引用的Java 7 API文档Arrays#Sort()对于对象数组,现在使用TimSort,它是MergeSort和InsertionSort的混合体。另一方面,Arrays#sort()对于原始数组,现在使用Dual-Pivot QuickSort这些更改是从Java SE 7开始实现的。

我能想到的一个原因是,快速排序的最坏情况时间复杂度为O(n ^ 2),而合并排序保留的最坏情况时间为O(n log n)。对于对象数组,有一个公平的期望,即会有多个重复的对象引用,这是quicksort最差的一种情况。

各种算法都有不错的视觉比较,请特别注意不同算法的最右图。

我正在上Coursera算法课程,并在Bob Bo Bedgewick教授的讲座之一中提到对Java系统排序的评估:

“如果程序员正在使用对象,那么空间可能不是至关重要的考虑因素,合并排序所使用的额外空间可能不是问题。而且,如果程序员正在使用原始类型,那么性能是最重要的,因此他们使用快速排序。”

java.util.Arrays中的用途快速排序为原始类型如int和归并为实现对象可比或使用比较器使用两种不同方法的想法是,如果程序员使用对象的空间可能不是至关重要的考虑因素,那么mergesort所使用的额外空间可能就不是问题,并且如果程序员使用的是原始类型,那么性能可能是最重要的考虑因素。在快速排序

例如:这是排序稳定性很重要的示例。

在此处输入图片说明

这就是为什么稳定排序对对象类型有意义,尤其是可变对象类型和具有比排序键更多的数据的对象类型的原因,而mergesort就是这样的排序。但是对于原始类型,稳定性不仅无关紧要。没有意义的

资料来源:INFO

Java的Arrays.sort方法使用快速排序,插入排序和合并排序。OpenJDK代码中甚至实现了单轴和双轴快速排序。最快的排序算法取决于情况,而优胜者是:小数组的插入排序(当前选择47个),大多数排序的数组的mergesort和其余数组的快速排序,因此Java的Array.sort()尝试选择最佳算法来根据这些标准申请。

本文地址:http://java.askforanswer.com/weishenmejavadearrays-sortfangfaduibutongleixingshiyongliangzhongbutongdepaixusuanfa.html
文章标签: ,   ,   ,  
版权声明:本文为原创文章,版权归 admin 所有,欢迎分享本文,转载请保留出处!

文件下载

老薛主机终身7折优惠码boke112

上一篇:
下一篇:

评论已关闭!