Collections.sort 解析

注：本文涉及到的源码以 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 的值来排的。

这次编译通过了。先执行看一下结果:
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RqvkE99s-1620300950746)(http://note.youdao.com/yws/res/2870/F3B1603116B9448C8171936629F2B97E)]

排序后的结果，是 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;
}

这样包含三种情况，就不会有问题了。

今天的文章Collections.sort 解析分享到此就结束了，感谢您的阅读。