• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

Java提供的排序算法是怎么实现的?快排?

技术杂谈 勤劳的小蚂蚁 4个月前 (02-05) 95次浏览 已收录 0个评论 扫描二维码

一、Arrays.sort()的排序算法
先来看看Arrays.sort(),sort方法拥有很多的重载,有十几种,以int查看如下:
可以看到这里有一个DualPivotQuicksort,DualPivotQuicksort翻译过来就是双轴快速排序(关于双轴快速排序我们后期在讨论,可以认为是对我们普通使用的快排的一种改进,另外还有一种改进是三路快排!),再次点进去,可以发现有这么一段代码:
发现如果数组的长度小于QUICKSORT_THRESHOLD的话就会使用这个双轴快速排序,而这个值是286。
那如果大于286呢,它就会判断数组的连续升序和连续降序性好不好,如果好的话就用归并排序,不好的话就用快速排序,看下面这段注释就可以看出
那现在再回到上面的决定用双轴快速排序的方法上,再点进去,发现又会多一条判断:
即如果数组长度小于INSERTION_SORT_THRESHOLD(值为47)的话,那么就会用插入排序了,不然再用双轴快速排序!
总结,如果数组长度大于等于286且连续性好的话,就用归并排序,如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序,如果长度小于47的话就用插入排序。示意图如下:
二、Collections.sort()的排序算法
再来看看Collections.sort(),一步步点进去,发现会进到Arrays里:
会发现如果LegacyMergeSort.userRequested为true的话就会使用归并排序,可以通过下面代码设置为true:
不过方法legacyMergeSort的注释上有这么一句话,说明以后传统归并可能会被移除了。
如果不为true的话就会用一个叫TimSort的排序算法,这个算法有兴趣的可以了解一下!
三、总结
在面试的时候如何秒杀众人,当问到这个问题的时候,我们就不要再脱口而出只是快排而已了!

丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:Java提供的排序算法是怎么实现的?快排?
喜欢 (0)
[247507792@qq.com]
分享 (0)
勤劳的小蚂蚁
关于作者:
温馨提示:本文来源于网络,转载文章皆标明了出处,如果您发现侵权文章,请及时向站长反馈删除。

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00