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

刺骨的言语ヽ痛彻心扉 2022-05-27 01:17 110阅读 0赞

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

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

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

public static void sort(int[] a) {
    	DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

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

if (right - left < QUICKSORT_THRESHOLD) {
    	sort(a, left, right, true);
    	return;
    }

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

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

/*
      * The array is not highly structured,
      * use Quicksort instead of merge sort.
      */

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

// Use insertion sort on tiny arrays
    if (length < INSERTION_SORT_THRESHOLD) {
    	//。。。。
    }

即如果数组长度小于INSERTION\_SORT\_THRESHOLD(值为47)的话，那么就会用插入排序了，不然再用双轴快速排序！

总结，如果数组长度大于等于286且连续性好的话，就用归并排序，如果大于等于286且连续性不好的话就用双轴快速排序。如果长度小于286且大于等于47的话就用双轴快速排序，如果长度小于47的话就用插入排序。示意图如下：  
![这里写图片描述][20180409110517932]

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

再来看看Collections.sort()，一步步点进去，发现会进到Arrays里：  
![这里写图片描述][20180409110604240]  
会发现如果LegacyMergeSort.userRequested为true的话就会使用归并排序，可以通过下面代码设置为true：  
![这里写图片描述][20180409110649168]  
不过方法legacyMergeSort的注释上有这么一句话，说明以后传统归并可能会被移除了。  
![这里写图片描述][20180409110709805]  
如果不为true的话就会用一个叫TimSort的排序算法，这个算法有兴趣的可以了解一下！

![在这里插入图片描述][20190602133102112.png]

[【视频福利】2T免费学习视频，搜索或扫描上述二维码关注微信公众号：Java后端技术（ID: JavaITWork）回复：**1024**，即可免费获取！内含SSM、Spring全家桶、微服务、MySQL、MyCat、集群、分布式、中间件、Linux、网络、多线程，Jenkins、Nexus、Docker、ELK等等免费学习视频，持续更新！][2T_Java_ID_ JavaITWork_1024_SSM_Spring_MySQL_MyCat_Linux_Jenkins_Nexus_Docker_ELK]

[20180409110517932]: /images/20220527/2fc450eb374a4646b120c62f495c6668.png
[20180409110604240]: /images/20220527/707f094685e14ce19de85d5e2acea0bd.png
[20180409110649168]: /images/20220527/e0c1de9b9ee946aeaa67cb51cfe88cfb.png
[20180409110709805]: /images/20220527/3a3b822e1d314c05bc0adfec4299f983.png
[20190602133102112.png]: /images/20220527/ab4ce5333be742e9a813a9aad0477865.png
[2T_Java_ID_ JavaITWork_1024_SSM_Spring_MySQL_MyCat_Linux_Jenkins_Nexus_Docker_ELK]: http://mp.weixin.qq.com/s?__biz=MzI1NDQ3MjQxNA==&mid=100005643&idx=1&sn=ed08bcf127fc549202ff273abeeb3d1a&chksm=69c5eeba5eb267ac550ed247d72d6c43e11551f25fe80f8ea6a3146682ce2266dad880ce48de#rd