深入理解Arrays.sort，怼哭面试官
本文例子基于JDK1.8
首先我们来看一个简单的Arrays.sort()的例子
基础知识点：
1.可以直接排的基本数据类型是：int,long,short,char,byte,float,double,其余类型都归于对象类，Object[]；注意是没有boolean的
2.Arrays.sort()默认的是升序排序，降序排序可采用Collection.sort()匿名内部类。
正如上图我们所看到的，对于基本数据类型的排序，基本上都是用到所谓的双基准快排算法：
快速排序使用的是分治思想，将原问题分成若干个子问题进行递归解决。选择一个元素作为轴(pivot)，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比轴元素小，另外一部分的所有数据都比轴元素大，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
双基准快排(DualPivotQuicksort)，顾名思义有两个轴元素pivot1，pivot2，且pivot ≤pivot2，将序列分成三段：x < pivot1、pivot1 ≤ x ≤ pivot2、x >pivot2，然后分别对三段进行递归，这个算法通常会比传统的快排效率更高
下面我们来看看Arrays.sort()具体的实现，大致过程如下图
1.如上图，首先判断数组int[] a的长度是否大于常量QUICKSORT_THRESHOLD, 即286:
286是java设定的一个阈值,当数组长度小于此值时, 系统将不再考虑merge sort, 直接将参数传入本类中的另一个私有sort方法进行排序，执行2
2.如上图，判断长度是否小于47，如果小于，则使用插入排序，否则执行到3；
值得注意的是, 在这里提供了两种不同的插入排序算法, 当传入的参数leftmost真假值不同时, 会使用不同的算法.
leftmost代表的是本次传入的数组是否是从最初的int[] a的最左侧left开始的, 因为本方法在整个排序过程中可能会针对数组的不同部分被多次调用, 因此leftmost有可能为false.
3.如上图，接下来就是双基准快排的开始；
思路上虽然并不复杂, 但为了尽可能的提高效率, 在对这个算法进行实现的过程中增加了非常多的细节；
上图就是最具特色的部分, 就是对Pivot的选取:
在这里, 系统会先通过位运算获取数组长度的1/7的近似值(位运算无法精确表示1/7)
如上图，然后获取本数组中间位置的索引e3；
在中间位置的左右1/7, 2/7处各获取两个索引(e1, e2, e4, e5):
如上图，之后再将这五个索引对应的值用插入算法进行有小到大的排序后, 再放回五个索引的位置
如上图，接下来进行判断, 若这五个索引对应的元素值各不相同, 则选取e2的值作为Pivot1, e4的值作为Pivot2(特别注意基准是值而不是元素), 然后进行双基准快排
如上图，接下来就是移动位置，分成三部分了；
如上图所示，如果这五个值中有相同的存在, 则本轮排序选取e3的值作为Pivot, 进行单基准快排；
从这里分开
接下来我们又回到DualPivotQuicksort的开始那里；
之前说到，小于286走的是上面那条线，那么大于286呢，走的就是下面这条线了；
如上图，当长度大于286时，继续判断该数组是否已经高度结构化(即已经接近排序完成):
这里的基本思路是这样的:
1.定义一个常量MAX_RUN_COUNT = 67;
2.定义一个计数器int count = 0; 定义一个数组int[] run 使之长度为MAX_RUN_COUNT + 1;
3.令run[0] = left, 然后从传入数组的最左侧left开始遍历, 若数组的前n个元素均为升序/降序排列, 而第n + 1个元素的升/降序发生了改变, 则将第n个元素的索引存入run[1], 同时++count, 此时count的值为1;
4.从n + 1开始继续遍历, 直至升/降序再次改变, 再将此处的索引存入run[2], ++count, 此时count的值为2, 以此类推...
......
5.若将整个数组全部遍历完成后, count仍然小于MAX_RUN_COUNT (即整个数组升降序改变的次数低于67次), 证明该数组是高度结构化的, 则使用merge sort进行排序;
若count == MAX_RUN_COUNT时, 还未完成对数组的遍历, 则证明数组并非高度结构化, 则调用前文所述私有sort方法进行quicksort.
如上图，判断该数组是否是是已经排列好的:
若该数组是高度结构化的, 在使用merge sort进行排序之前, 会先检验数组是否本身就是排序好的, 思路很简单, 如果在前面的检测中一次就完成了遍历, 就证明该数组是排序好的, 则直接返回结果:
最后就是进行归并排序了。
Array.sort的基本类型的排序先介绍到这里，如果你有什么不同的看法，欢迎加微信交流哦~我们的微信：miraclesComing