在学习过程中观察到Arrays.sort(arr)算法可以直接进行排序，但不清楚底层的代码逻辑是什么样子，记得自己之前在面试题里面也有面试官问这个问题，只能说研究之后发现还是比较复杂的
|
在学习过程中观察到Arrays.sort(arr)算法可以直接进行排序，但不清楚底层的代码逻辑是什么样子，记得自己之前在面试题里面也有面试官问这个问题，只能说研究之后发现还是比较复杂的，并不是网上说的快排或者二分插入之类的。 首先看源码：
它调用了DualPivotQuicksort的sort方法，乍一看以为是快排，这是很多网上的博主的说法，继续点开向下看（代码太长，没耐心看可以直接跳过该段代码QWQ）：
代码很长，简要翻译过来，这里分了好几种情况： 1.数组长度小于286 这里又会调用一个sort方法，点开该sort()，又会划分情况： 数组长度小于47， 当leftmost（导入的一个布尔参数）为true，则使用直接插入排序； 否则会调用另一种插入办法，这里可以观察到一个注释：
大致意思是：相邻部分的每个元素都扮演着哨兵的角色，因此这允许我们避免在每次迭代中进行左范围检查。此外，我们使用了更优化的算法，即所谓的成对插入排序，它比插入排序的传统实现更快（在快速排序的上下文中）。 不过注意到，原函数参数传参在这里leftmost为true，所以一定是直接插入排序，以上作为了解。 数组长度大于47，采用一种快速排序的办法，这里因为代码太长，学艺不精，参考了一下https://www.jb51.net/article/236440.htm:
当数组长度大于286时 此时回到那段很长很长的代码段，在判断小于286的长度数组之后，从注解中：
这里是指检查数组元素是不是快要排列好了，或者书面一点说，是不是有一定结构了，然后看后面的for循环，注意到一段代码：
这里的sort和我们上面在数组长度小于286时的那个sort方法是同一个方法，而针对这个count，是用来记录逆序组的，打个比方： 此时有一个数组为1 5 6 9 8 7 2 3 当数组认定我们的顺序应该为升序时，从第一个数开始数，此时9 8 7 2为降序，这就是逆序，将这四个数组合成一个组称为逆序组，然后再从3开始往后看。 当统计到一个逆序组时，count++，所以可以看出，count是用来记逆序组的，那么逆序组越多，这个结构就越混乱 MAX_RUN_COUNT == 67 ，因此当count一直加到67时，就说明已经在一个混乱的临界值了，此时执行sort()方法 通过这一段分析，我们理一下思路： ?如果数组能运行到这里，说明数组的长度大于等于286。符合该条件时，我们要判断这个数组是否有一定的结构： （1）count<67，说明不是那么混乱，有一定结构，跳过； （2）count>=67，说明已经混乱了，没有结构，执行sort方法，而已知数组长度大于等于286，那么必然大于47，一定执行快速排序。 跳过之后，经过代码的一大堆前置操作，最后看见下面的代码里面一行注释：
显然，这里后面用到归并排序了，不详细赘述。 好了，最后总结：
参考资料： 《Java的Arrays.sort()方法到底用的什么排序算法》https://www.cnblogs.com/baichunyu/p/11935995.html作者：白春雨 |
2021-06-05
2021-05-27
2021-05-26
2021-06-05
2021-05-16
