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

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

一、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的排序算法,这个算法有兴趣的可以了解一下!

三、总结

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

原文发布于微信公众号 - Java后端技术(JavaITWork)

原文发表时间:2018-03-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏木制robot技术杂谈

谈一谈Python中str()和repr()的区别

前言 在学习BeautifulSoup文档的时候发现了一个以前不常见的Python内建函数repr(),带着好奇对这个内建函数进行了一番搜索和学习。 总结 s...

38140
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

还有一个不错的视频(https://marcus-biel.com/java-comparable-interface-video-tutorial/)。

11850
来自专栏个人随笔

Java 关于接口的那点事儿

接口的应用 接口是一种能力 关键字:interface 语法:  public interface MyInterface{   public void ...

40980
来自专栏java一日一条

5 分钟搞定 Java Comparable 接口

我们应该如何对事物进行比较和排序?这问题听上去有点莫名其妙,但我希望你认真考虑一下。比方说,我们有一组苹果:

6510
来自专栏CSDN技术头条

抽象类和接口的区别

【编者按】本文作者是Sebastian Malaca,是面向对象编程的狂热者,不断深化研究整洁代码和高代码质量。本文中,作者通过多个方面深入剖析抽象类和接口的区...

235100
来自专栏软件开发 -- 分享 互助 成长

简单工厂模式

一、简单工厂模式的相关概念: 1、定义:简单工厂模式是属于创建型模式,又叫做静态工厂方法(Static Factory Method)模式。 其核心思想就是有一...

19290
来自专栏C语言及其他语言

《黄老师问答笔录》之C语言常见易错问题

以下摘自黄老师课堂课堂答疑、与学生交流的真实问题总结,为了便于入学者学习查阅,总结归纳于此。 1、问:我想判断一个数字是否在一个区间里,比如if(90<a<10...

375130
来自专栏Albert陈凯

Scala如何改变了我的编程风格:从命令式到函数式

51CTO编辑推荐: Scala编程语言专题 【51CTO快译】编者前言:这篇文章最初写于2008年底,作者Bill Venners一方面是美国著名开发网站A...

26130
来自专栏CodingToDie

Python学习(八):类和对象 以另一种思维看待世界

第8 章 类和对象 以另一种思维看待世界 对世界万物的状态与行为进行归纳与分类,以此分析个体与个体间的相互作用与影响方法。 Table of Contents ...

39370
来自专栏落影的专栏

leetcode––为求职为生的编程网站

前言 leetcode是一个在线编程网站,题目源于各大公司的面试、有各种解法、多语言和在线测试支持; 我们扫一眼leetcode上的Company:Googl...

413100

扫码关注云+社区

领取腾讯云代金券