Arrays.sort()和Collections.sort()都是java为我们提供的排序算法，它们的内部原理到底是什么样的呢？
Arrays.sort()
int[] a = new int[10];
Object[] o = new Object[10];
1、基本类型数据
当Arrays.sort()是排序基本类型数组时,Arrays.sort(a),采用的是快速排序，我们看源码可以发现，其采用的是DualPivotQuicksort的排序。
什么是DualPivotQuicksort呢？
我们知道对于快速排序，是有一个基准pivot，每次排序后，左边的数据都比基准小，右边的数据都比基准大，然后在进行递归。
具体可以看这篇博客：快速排序
DualPivotQuicksort是jdk1.7之后出现的，在jdk1.7之前采用的简单快排。
DualPivotQuicksort使用了两个pivot加速，P1、P2且P1<P2，可简单理解为：每次排序将数组分为三部分，第一部分小于P1，第二部分大于P1小于P2,第三部分大于P2，然后在递归排序。
为什么DualPivotQuicksort比简单快排效率高呢？
1、对于很小的数组（长度小于27），会使用插入排序。
2、对于较大数组，则采用上面所说的双轴排序。
2、对象数组
当Arrays.sort()是排序对象数组时,Arrays.sort(o),采用的是归并排序，我们看源码可以发现，其采用的是legacyMergeSort的排序。
其底层使用的还是归并排序。
Collections.sort()
Collections.sort()常用来对集合进行排序，其底层是归并排序。
ArrayList<String> list = new ArrayList<String>();
Collections.sort(list);
我们看源码发现：它调用了list.sort()，然后我们看list.sort的源码发现其调用了Arrays.sort(),其中a是list，c是比较器，嗯哼？怎么和上面的一样了？？然后我们接着看这里的Arrays.sort()，这里我们没有使用比较器，故我们只需看上面的sort()方法即可，其使用的还是归并排序。
若我们定义了比较器，则要使用下面else块中的代码，我们发现一个已经出现两次的TimSort()，在未使用比较器的时候，其中有一个ComparableTimSort，
若我们定义了比较器，则要使用下面else块中的代码，我们发现一个已经出现两次的TimSort()，在未使用比较器的时候，其中有一个ComparableTimSort，在这里则是TimSort。
TimSort是结合了归并排序和插入排序而得出的排序算法，该算法找到数据中已经排好序的块 - 分区，每一个分区叫一个run，然后按规则合并这些run。
TimSort算法为了减少对升序部分的回馈和对降序部分的性能倒退，将输入按其升序和降序特点进行了分区。每次合并会将两个运行合并成一个运行。合并的结果保存到栈中。合并直到消耗掉所有的运行，这时将栈上剩余的跑合并到只剩一个跑为止。这时这个仅剩的跑便是排好序的结果。
综上述过程，Timsort算法的过程包括
（0）如何数组长度小于某个值，直接用二分插入排序算法
（1）找到各个运行，并入栈
（2）按规则合并运行
网友评论