Collections.sort是java自带的一个排序api，相信绝大多数小伙伴都用过这个api，非常常用。既然这么常用，我觉着有必要研究一下它内部是怎么实现的，避免掉坑。先说点排序算法相关的基本知识。
排序算法有2个非常重要的指标，我们需要关注。
1.是否原地排序
2.是否稳定排序
第一个指标是说算法中是否借助了额外的空间进行排序操作
第二个指标是说算法是否稳定
如何理解 稳定 这个词呢?我们举个例子。
比如说：我们要对一组学生按照出生日期升序排列。相同生日的订单，再按照年龄升序排列。如何实现这个需求呢？
这个需求实现的思路是：要注意先按照生日升序排，然后再按照年龄排（反过来实现，难度会倍增）可以借助Collections.sort实现，伪代码如下：
@Data
@Builder
@NoArgsConstructor
@AllArgsConstructor
public class Student {
private int id;
private String name;
private int age;
private long birthday;
}
//测试方法
public static void main(String[] args) {
Student student1 = Student.builder().id(1).name("测试1").age(100).birthday(12345).build();
Student student2 = Student.builder().id(2).name("测试2").age(100).birthday(12389).build();
Student student3 = Student.builder().id(3).name("测试3").age(100).birthday(12346).build();
Student student4 = Student.builder().id(4).name("测试4").age(77).birthday(12347).build();
Student student5 = Student.builder().id(5).name("测试5").age(66).birthday(12358).build();
Student student6 = Student.builder().id(6).name("测试6").age(66).birthday(12353).build();
Student student7 = Student.builder().id(7).name("开发1").age(31).birthday(12355).build();
Student student8 = Student.builder().id(8).name("开发2").age(76).birthday(1234556).build();
Student student9 = Student.builder().id(9).name("开发3").age(101).birthday(1234509).build();
Student student10 = Student.builder().id(10).name("开发4").age(101).birthday(1234587).build();
Student student11 = Student.builder().id(11).name("开发5").age(31).birthday(12145).build();
Student student12 = Student.builder().id(12).name("开发6").age(102).birthday(10345).build();
List studentList = new ArrayList<>();
studentList.add(student1);
studentList.add(student2);
studentList.add(student3);
studentList.add(student4);
studentList.add(student5);
studentList.add(student6);
studentList.add(student7);
studentList.add(student8);
studentList.add(student9);
studentList.add(student10);
studentList.add(student11);
studentList.add(student12);
Comparator birthdayComparator = (o1, o2) -> {
if (o1.getBirthday() > o2.getBirthday()) {
return 1;
} else if (o1.getBirthday() < o2.getBirthday()) {
return -1;
} else {
return 0;
}
};
Comparator ageComparator = (o1, o2) -> {
if (o1.getAge() > o2.getAge()) {
return 1;
} else if (o1.getAge() < o2.getAge()) {
return -1;
} else {
return 0;
}
};
//either provide a Comparable class type or a Customize Compartor
Collections.sort(studentList,birthdayComparator);
Collections.sort(studentList,ageComparator);
System.out.println(JSON.toJSONString(studentList));
}
这个时候，我们就要思考一个问题，我按照生日升序完毕，再按照年龄排的话，之前按生日排好序的序列会不会发生变化呢？
这个问题，其实就是我今天想聊的话题。直接说结论，Collections.sort是稳定排序，按照生日升序完毕，再按照年龄排。之前按生日排序的序列不会发生变化。
接下来，聊一下Collections.sort的实现。入口是Collections类中的这个方法
public staticvoid sort(List list, Comparator c) { list.sort(c); }
然后进入List接口中的sort方法，如下
default void sort(Comparator c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
注意这是一个default方法，接口的默认实现。这里说一个本地debug的小知识点。我们只知道接口，如果这个接口有很多实现，如何知道接口到底走哪个实现类呢？有一个简单的办法，我们可以直接将断点打在接口上，像下面这样。
Idea可以自动识别到实现类，并进入实现类中
这个小技巧非常的实用，大家记得记在小本本上。下面聊回正题，进入ArrayList的sort方法后，最关键的是Arrays.sort方法，我们看一下这个方法的实现
public staticvoid sort(T[] a, int fromIndex, int toIndex, Comparator c) { if (c == null) { sort(a, fromIndex, toIndex); } else { rangeCheck(a.length, fromIndex, toIndex); if (LegacyMergeSort.userRequested) legacyMergeSort(a, fromIndex, toIndex, c); else TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0); } }
根据当前的条件可知，c不为null，并且LegacyMergeSort.userRequested是false，执行了TimSort排序，这里提一句这个TimSort，这个排序算法是一个叫Tim Peters 在2002年实现的，维基百科定义如下：
Timsort 是一种混合稳定的排序算法，源自合并排序和插入排序，旨在较好地处理真实世界中各种各样的数据。它使用了 Peter Mcllroy 的"乐观排序和信息理论上复杂性"中的技术，参见 第四届年度ACM-SIAM离散算法研讨会论文集，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7[4], Android platform[5], GNU Octave,[6] 谷歌浏览器,[7] 和 Swift[8] 用于对非原始类型的数组排序。
通过以上描述，隐约感觉这个排序算法的来头很大。我想研究一下这个算法是怎么实现的。有部分源码看着有点费劲，没有全部看懂。我就把我看明白的部分简单说一下，剩下不太懂的部分，参考了这篇文章世界上最快的排序算法
staticvoid sort(T[] a, int lo, int hi, Comparator c, T[] work, int workBase, int workLen) { assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length; //计算集合的大小 int nRemaining = hi - lo; if (nRemaining < 2) //集合中的元素数量是0或1说明元素已经有序,无需排序 return; //如果集合元素数量小于32,使用二分查找算法进行排序 if (nRemaining < MIN_MERGE) { //获取集合中有序元素的数量,以该数量为基点对其余元素进行排序 int initRunLen = countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return; } TimSort ts = new TimSort<>(a, c, work, workBase, workLen); int minRun = minRunLength(nRemaining); do { // Identify next run int runLen = countRunAndMakeAscending(a, lo, hi, c); // If run is short, extend to min(minRun, nRemaining) if (runLen < minRun) { int force = nRemaining <= minRun ? nRemaining : minRun; binarySort(a, lo, lo + force, lo + runLen, c); runLen = force; } // Push run onto pending-run stack, and maybe merge ts.pushRun(lo, runLen); ts.mergeCollapse(); // Advance to find next run lo += runLen; nRemaining -= runLen; } while (nRemaining != 0); // Merge all remaining runs to complete sort assert lo == hi; ts.mergeForceCollapse(); assert ts.stackSize == 1; }
//获取集合中有序元素的数量,如果有序数据为逆序,进行反转 private staticint countRunAndMakeAscending(T[] a, int lo, int hi, Comparator c) { assert lo < hi; int runHi = lo + 1; if (runHi == hi) return 1; if (c.compare(a[runHi++], a[lo]) < 0) { // 逆序 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { // 正序 while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++; } return runHi - lo; }
//二分查找法对数据进行排序,该方法的时间复杂度是O(nlogn)，但是因为引入了System.arrayCopy方法，所以最坏情况下，可能会退化为O(n²)。 private staticvoid binarySort(T[] a, int lo, int hi, int start, Comparator c) { assert lo <= start && start <= hi; if (start == lo) start++; for ( ; start < hi; start++) { T pivot = a[start]; int left = lo; int right = start; assert left <= right; //start索引前面的数据都是排好序的,我们需要给pivot这个数据找到它应该放的位置 while (left < right) { int mid = (left + right) >>> 1; if (c.compare(pivot, a[mid]) < 0) right = mid; else left = mid + 1; } assert left == right; int n = start - left; // The number of elements to move // Switch is just an optimization for arraycopy in default case switch (n) { case 2: a[left + 2] = a[left + 1]; case 1: a[left + 1] = a[left]; break; default: System.arraycopy(a, left, a, left + 1, n); } a[left] = pivot; } }
Peter老哥的注释写的已经很清晰了，我觉着不需要我再解释啥了。这个binarySort方法主要就是利用了二分查找算法，找到pivot应该在的位置后，对该位置以后的数据进行搬移，给pivot元素腾位置，最后执行a[left] = pivot，将pivot元素放到腾出来的位置。然后利用该方法对剩余元素继续排序。
以上二分查找排序只能属于一个小优化，很简单。下面才是Collections.sort的核心逻辑
//初始化一个TimSort,a是原始数组,c是比较器。work是null，workBase和workLen都是0
TimSort ts = new TimSort<>(a, c, work, workBase, workLen);
int minRun = minRunLength(nRemaining);
do {
// Identify next run
int runLen = countRunAndMakeAscending(a, lo, hi, c);
// If run is short, extend to min(minRun, nRemaining)
if (runLen < minRun) {
int force = nRemaining <= minRun ? nRemaining : minRun;
binarySort(a, lo, lo + force, lo + runLen, c);
runLen = force;
}
// Push run onto pending-run stack, and maybe merge
ts.pushRun(lo, runLen);
ts.mergeCollapse();
// Advance to find next run
lo += runLen;
nRemaining -= runLen;
} while (nRemaining != 0);
// Merge all remaining runs to complete sort
assert lo == hi;
ts.mergeForceCollapse();
assert ts.stackSize == 1;
minRunLength的实现
private static int minRunLength(int n) {
assert n >= 0;
int r = 0; // Becomes 1 if any 1 bits are shifted off
while (n >= MIN_MERGE) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
这里又用到了位运算，再补点小知识点
|和&是或运算和与运算，这个很简单，不多说。
两个大于号(>>)，这个是右移操作，相当于我们平时用的除2操作，但是性能上要比除操作快得多。右移后，空出的符号位用原来的符号补齐。什么意思呢？
String binaryString = Integer.toBinaryString(-12); System.out.println(binaryString); String binaryStringRightMove = Integer.toBinaryString(-12 >> 3); System.out.println(binaryStringRightMove); 输出： 11111111111111111111111111110100 11111111111111111111111111111110 右移前，左边的符号位上都是1，所以右移后，左边不足32位了，需要用1进行补齐
三个大于号(>>>)，这个是无符号右移，也是除2操作，和上面的>>操作不同的是，右移后，空出的符号位用0补齐。
String binaryString = Integer.toBinaryString(-12); System.out.println(binaryString); String binaryStringRightMove = Integer.toBinaryString(-12 >>> 3); System.out.println(binaryStringRightMove); 输出： 11111111111111111111111111110100 00011111111111111111111111111110
实际上，TimSort算法，就是结合了二分查找插入排序，优化了插入排序。结合了run块的设计优化了归并排序。所以Collections.sort不是原地排序算法，但是是一个稳定的排序算法。
