注：本文涉及到的源码以 Android 为准，是从 Android Studio 中 copy 出来，与标准 java 源码略有出入（区别主要体现在部分逻辑在 Android 中被注释掉不会执行，所以不在本文分析中）。
下面是正文了
Collections 是一个工具类，Collections.sort 是常见的用来排序的方法，虽常见，但是其排序原理不是很容易理解，特别是其中涉及到的 compareTo() 和 compare() 两个方法，着实有些绕，本文的初衷就是为了解释这两个方法如何生效。
回归正题，Collections.sort() 有两个重载方法：
1、第一个方法
public static <T> void sort(List<T> list, Comparator<? super T> c) {}
2、第二个方法
public static <T extends Comparable<? super T>> void sort(List<T> list) {
// Android-changed: Call sort(list, null) here to be consistent
// with that method's (Android changed) behavior.
// list.sort(null);
sort(list, null);
}
先总结一下两个方法的关系或者说区别：
- 方法二内部还是调用了方法一，只是第二个参数传了 null
- 方法一可以传入任意类型的 list，方法二传入的list 的数据类型必须实现 Comparable 接口
- 方法一排序规则在于 Comparator 接口中 compare() 方法的实现；而方法二排序规则在于 Comparable 接口中 compareTo() 方法的实现。其实异曲同工，本文就以第二个方法为例分析一下如何实现的排序。
一、举例说明
这个方法是一个泛型方法，<T extends Comparable<? super T>> 告诉我们这个类型需要实现 Comparable 接口，至于为什么是 T extends Comparable 而不是 T implements Comparable，是因为泛型方法的命名规则，无论是继承某个类还是实现某个接口，都是用 extends。
这是 Comparable 接口：
public interface Comparable<T> {
/**
* @param o the object to be compared.
* @return a negative integer, zero, or a positive integer as this object
* is less than, equal to, or greater than the specified object.
*/
public int compareTo(T o);
}
接口里只有一个 compareTo 一个方法，它的返回值决定了 sort 方法的排序方式，官方注释也容易理解，意思是：
- 返回值小于 0 代表当前对象比参数 less
- 返回值等于 0 代表当前对象与参数 equal
- 返回值大于 0 代表当前对象比参数 greater
之所以用 less、equal、greater 是因为不限于数值的大或小，它的大小取决于我们给它定的规则。
先用一个栗子来看看用法：
TestBean 类
public class TestBean{
int num;
String name;
TestBean(int num,String name){
this.num = num;
this.name = name;
}
@Override
public String toString() {
return "TestBean{" +
"num=" + num +
", name='" + name + '\'' +
'}';
}
}
Main 函数:
可以看到此时无法编译通过，原因就是当前的 bean 类并没有实现 Comparable 接口。接下来修改 TestBean 类，改后如下
public class TestBean implements Comparable<TestBean> {
int num;
String name;
TestBean(int num,String name){
this.num = num;
this.name = name;
}
@Override
public int compareTo(TestBean o) {
return num - o.num;
}
@Override
public String toString() {
return "TestBean{" +
"num=" + num +
", name='" + name + '\'' +
'}';
}
}
改后的 bean 实现了 Comparable 接口，并实现了 compareTo() 方法，返回值为 num - o.num，目前至少可以明白，接下来的排序，是根据 num 的值来排的。
这次编译通过了。先执行看一下结果:
[图片上传失败...(image-cd01bf-1620354103427)]
排序后的结果，是 num 由小到大排序的，这也是 Integer 类型的默认排序方式。既然说到这，就顺便贴一下 Integer 类的 compareTo 方法：
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
对比一下 TestBean 和 Integer 的compareTo 的返回值:
- TestBean : return num - o.num;
- Integer : return (x < y) ? -1 : ((x == y) ? 0 : 1);
前面说过，这个方法的返回值，只跟大于0 还是小于 0 有关系，至于是 100 还是 1，都是一样的，所以两个类的返回值其实意义相同，都是返回 (x - y) 的值。
二、源码解析
主要讲排序相关的关键逻辑，部分不重要的部分会略过。
先贴源码：
public static <T> void sort(List<T> list, Comparator<? super T> c) {
// BEGIN Android-changed: Compat behavior for apps targeting APIs <= 25.
// list.sort(c);
int targetSdkVersion = VMRuntime.getRuntime().getTargetSdkVersion();
if (targetSdkVersion > 25) {
list.sort(c);
} else {
// Compatibility behavior for API <= 25. http://b/33482884
if (list.getClass() == ArrayList.class) {
Arrays.sort((T[]) ((ArrayList) list).elementData, 0, list.size(), c);
return;
}
Object[] a = list.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<T> i = list.listIterator();
for (int j = 0; j < a.length; j++) {
i.next();
i.set((T) a[j]);
}
}
// END Android-changed: Compat behavior for apps targeting APIs <= 25.
}
以 targetSdkVersion > 25 为例，其中的关键代码就是 if 中的 list.sort(c)，点进去是这样的：
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
我们只关注 Arrays.sort(a, (Comparator) c) ，再点进去：
public static <T> void sort(T[] a, Comparator<? super T> c) {
if (c == null) {
sort(a);
} else {
// Android-changed: LegacyMergeSort is no longer supported
// if (LegacyMergeSort.userRequested)
// legacyMergeSort(a, c);
// else
TimSort.sort(a, 0, a.length, c, null, 0, 0);
}
}
这里 if 的两个分支，就是最开始提到的两个重载方法的区别，如果调用的是方法一，传入了自定义的 Comparator ，就会走到 else 中，最终生效的是 compare() 方法；如果调用的是方法二，传入的 Comparator 是 null，就会走到 if 中，最终生效的 compareTo() 方法；我们传入的 Comparator 是 null，就以此为例。
继续点进去，最终执行到 ComparableTimSort.sort 方法，源码如下：
static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
assert a != null && lo >= 0 && lo <= hi && hi <= a.length;
//需要排序的长度
int nRemaining = hi - lo;
if (nRemaining < 2)
return; // Arrays of size 0 and 1 are always sorted
// If array is small, do a "mini-TimSort" with no merges
if (nRemaining < MIN_MERGE) {
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
return;
}
/**
* 后面还有排序长度大于32的情况的处理，这里就不详细分析了，
* 大概逻辑是对数组 分段排序最后整合
*/
}
看到方法的形参名字，lo 、hi 大概已经有数了，二分法。往下看，果然看到了 binarySort() 这个方法。
这里有个判断 nRemaining < MIN_MERGE ，MIN_MERGE 的值为 32，就是说数组中需要排序的这一段的长度小于32，才会走进这个方法。我们就以长度小于 32 的情况为例，因为大于 32 的时候的关键逻辑是一致的，主要就是下面两行代码：
int initRunLen = countRunAndMakeAscending(a, lo, hi);
binarySort(a, lo, hi, lo + initRunLen);
先看第一行 int initRunLen = countRunAndMakeAscending(a, lo, hi)，这个 initRunLen 是什么东西呢，看一下 countRunAndMakeAscending() 方法的源码：
/**
* Returns the length of the run beginning at the specified position in
* the specified array and reverses the run if it is descending (ensuring
* that the run will always be ascending when the method returns).
*
* A run is the longest ascending sequence with:
*
* a[lo] <= a[lo + 1] <= a[lo + 2] <= ...
*
* or the longest descending sequence with:
*
* a[lo] > a[lo + 1] > a[lo + 2] > ...
*
* @return the length of the run beginning at the specified position in
* the specified array
*/
private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
assert lo < hi;
int runHi = lo + 1;
if (runHi == hi)
return 1;
// Find end of run, and reverse range if descending
//这里 compareTo 的结果根据我们自己的实现决定
if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // Descending
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
runHi++;
//翻转
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
runHi++;
}
return runHi - lo;
}
因篇幅问题，删了部分注释。这个方法简单来说，就是：从下标 lo 开始往后数，截取一段有序的数组，如果截取到的数组是倒序，那么就翻转这一段有序数组，使它变成正序，最后 return 这个数组的长度，或者可以换个说法：获取 a[] 中的第一个无序的数的下标，如果这个数之前的一段是倒序，就将这一段翻转。
这一步操作后的结果，就是将 a[] 中的第一段有序数组变成正序，带上数据看一下，还是之前的数据：
int a[] = { 4, 5, 7, 9, 8},
lo = 0,
hi = 4,
runHi = 1
//走到 if 语句:
if ((a[runHi++]).compareTo(a[lo]) < 0) { // Descending
while (runHi < hi && ( a[runHi]).compareTo(a[runHi - 1]) < 0)
runHi++;
reverseRange(a, lo, runHi);
} else { // Ascending
while (runHi < hi && ( a[runHi]).compareTo(a[runHi - 1]) >= 0)
runHi++;
}
这其中有一个关键点，就是 compareTo() 方法，回忆一下我们 TestBean 中实现的这个方法：
@Override
public int compareTo(TestBean o) {
return num -o.num;
}
这里的 compareTo 其实就相当于减号 “-”，在此基础上，再来看上面的判断：
a[runHi++]).compareTo(a[lo]) < 0 这个条件 意思是 a[1] 比 a[0] 小，也就是倒序；
那么 else 就是a[1]比a[0]大，那么执行 runHi ++,找到a[2] 也就是 7 ，a[2] 仍然比 a[1] 大，那么继续往后一直找到 a[4] 也就是 8，发现 a[4] 小于 a[3] ，while 循环结束，此时 a[] 的前4位已经是正序排列，并且 return 这个 4。
假如这个数组 a[] = { 9, 7, 5, 4, 8}，也就是第一种 倒序的情况，那么找到 a[4]后，while 循环结束，会多一步 reverseRange(a,0,4) 的操作，同样会将 a变为 {4, 5, 7, 9, 8}，然后 return 4。
假如我们实现的 compareTo() 的返回值变为 return o.num - num，即交换减数和被减数位置，那么得到的结果自然会与之前相反，就会变成倒序。如果返回值变为固定值，如果大于等于0，则a[] 不会有改动，直接返回原数据；如果小于 0，则会翻转整个 a[]。
只剩最后一行关键代码 binarySort(a, lo, hi, lo + initRunLen)，看名字就知道是二分法排序，看一下源码：
private static void binarySort(Object[] a, int lo, int hi, int start) {
// 断言是为了调试用的，如果未开启断言功能，会被忽略；如果开启了断言功能，并且 assert 后面的语句为 false，则会抛出错误
assert lo <= start && start <= hi;
if (start == lo)
start++;
for ( ; start < hi; start++) {
Comparable pivot = (Comparable) a[start];
// Set left (and right) to the index where a[start] (pivot) belongs
int left = lo;
int right = start;
assert left <= right;
/*
* Invariants:
* pivot >= all in [lo, left).
* pivot < all in [right, start).
* 即通过二分法找到 pivot 应插入的位置
*/
while (left < right) {
//无符号移位，就是 (left + right)/2
int mid = (left + right) >>> 1;
/*
* 与标准的二分法唯一的区别，就是这里是用compareTo() 来比较“大小”，
* 这个“大小”如何来判定就由我们对这个方法的具体实现而定，
* compareTo()的返回值大于0，那前者就大于后者；等于0就两者等同；
* 小于0就前者小于后者
*/
if (pivot.compareTo(a[mid]) < 0)
right = mid;
else
left = mid + 1;
}
assert left == right;
/*
* The invariants still hold: pivot >= all in [lo, left) and
* pivot < all in [left, start), so pivot belongs at left. Note
* that if there are elements equal to pivot, left points to the
* first slot after them -- that's why this sort is stable.
* Slide elements over to make room for pivot.
*/
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;
}
}
二分法排序，是从前到后将数组的元素逐个插入到前面已排序的数组中，该插入哪个位置，是用二分法去查找的。
对照源码还是很容易理解的，在网上查的话基本代码也是跟源码一样，这里就不赘述了。
到此正文就结束了，另外有一个需要注意的点：实现 compare 或者 compareTo 接口的时候，返回值 1 、 0 、 -1 三种情况一定要包含全，否则可能会抛出下面异常：
java.lang.IllegalArgumentException: Comparison method violates its general contract!
打个比方，如果我想对 Date 类型的 data1 和 date2 排序，如下：
if (date1.before(date2)) {
return 1;
}
return -1;
这样少了 return 0 的情况，万一 date1 和 date2 的值相同，那么 date1.before(date2) 和 date2.before(date1) 都是 return 1，从结果上看就会是两种不同的排序，这样就可能导致上述的异常。改一下代码，变成这样：
if (date1.before(date2)) {
return 1;
} else if(date1.after(date2)){
return -1;
} else {
//jdk 7 后这里必须判断 return 0 的情况,否则会提示 "Comparison method violates its general contract!"
return 0;
}
这样包含三种情况，就不会有问题了。
