0°

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

内容预览:
  • 那如果大于286呢,它就会判断数组的连续升序和连续降序性好不好,如果好...~
  • 如果长度小于286且大于等于47的话就用双轴快速排序,如果长度小于47的话...~
  • 示意图如下: 二、Collections.sort()的排序算法 再来看看Collections.s...~

始发于微信公众号: Java后端技术

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

前几天整理的一套面试题,其中有一个问题就是Java的JDK中我们见到的Collections.sort()和Arrays.sort()这两个排序算法的实现方式是什么,很多小伙伴心里边默认的应该是快排,但是不全对或者理解的不够深刻,以下我们从源码的层次一点点解释一下这个问题:

一、Arrays.sort()的排序算法

先来看看Arrays.sort(),sort方法拥有很多的重载,有十几种,以int查看如下:

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

可以看到这里有一个DualPivotQuicksort,DualPivotQuicksort翻译过来就是双轴快速排序(关于双轴快速排序我们后期在讨论,可以认为是对我们普通使用的快排的一种改进,另外还有一种改进是三路快排!),再次点进去,可以发现有这么一段代码:

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

发现如果数组的长度小于QUICKSORT_THRESHOLD的话就会使用这个双轴快速排序,而这个值是286。

那如果大于286呢,它就会判断数组的连续升序和连续降序性好不好,如果好的话就用归并排序,不好的话就用快速排序,看下面这段注释就可以看出

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

那现在再回到上面的决定用双轴快速排序的方法上,再点进去,发现又会多一条判断:

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

即如果数组长度小于INSERTION_SORT_THRESHOLD(值为47)的话,那么就会用插入排序了,不然再用双轴快速排序!

总结,如果数组长度大于等于286且连续性好的话,就用归并排序,如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序,如果长度小于47的话就用插入排序。示意图如下:

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

二、Collections.sort()的排序算法

再来看看Collections.sort(),一步步点进去,发现会进到Arrays里:

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

会发现如果LegacyMergeSort.userRequested为true的话就会使用归并排序,可以通过下面代码设置为true:

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

不过方法legacyMergeSort的注释上有这么一句话,说明以后传统归并可能会被移除了。

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

如果不为true的话就会用一个叫TimSort的排序算法,这个算法有兴趣的可以了解一下!

三、总结

在面试的时候如何秒杀众人,当问到这个问题的时候,我们就不要再脱口而出只是快排而已了!

点击图片查看更多推荐内容

↓↓↓

不谈面试题,谈谈面试官喜欢见到的特质!

【面试题】2018年最全Java面试通关秘籍第二套!

从分布式一致性谈到CAP理论、BASE理论!

为什么你创建的数据库索引没有生效?

和大佬一起学习网络安全知识

以上就是:Java提供的排序算法是怎么实现的?快排? 的全部内容

本站部分内容来源于互联网和用户投稿,如有侵权请联系我们删除,谢谢^^
Email:[email protected]


0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论