最近Algorithms 4 课上提到了排序。趁着这个机会，梳理一下。

1. 介绍

Comparable<T>接口和Comparator<T>接口都是JDK中提供的和比较相关的接口。使用它们可以对对象进行比较大小，排序等操作。这算是之后排序的先导知识吧。
Comparable，字面意思是“可以比较的”，所以实现它的类的多个实例应该可以相互比较“大小”或者“高低”等等。
Comparator，字面意思是“比较仪，比较器”，它应该是专门用来比较用的“工具”。

2. Comparable

Comparable<T>接口

public interface Comparable<T> {

    public int compareTo(T o);
}

首先看看JDK中怎么说的：

This interface imposes a total ordering on the objects of each class that implements it. This ordering is referred to as the class’s natural ordering, and the class’s compareTo method is referred to as its natural comparison method.

大意是: 任何实现这个接口的类，其多个实例能以固定的次序进行排列。次序具体由接口中的方法compareTo方法决定。

Lists (and arrays) of objects that implement this interface can be sorted automatically by {@link Collections#sort(List) Collections.sort} (and {@link Arrays#sort(Object[]) Arrays.sort}).

如果某个类实现了这个接口，则它的List或数组都能使用Collections.sort()或Arrays.sort()进行排序。
常见的类如Integer, Double, String都实现了此类。一会儿会结合源码进行分析。

2.1 Integer类中Comparable接口的实现

我们先来看Integer中的实现：

public final class Integer extends Number implements Comparable<Integer> {

    private final int value;
    
    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);
    }
    public static int compareUnsigned(int x, int y) {
        return compare(x + MIN_VALUE, y + MIN_VALUE);
    }

我们只贴出了和比较相关的方法。
可以看到，compareTo方法其中调用了compare方法，这是JDK1.7增加的方法。在Integer中新增这个方法是为了减少不必要的自动装箱拆箱。传入compare方法的是两个Integer的值x和y。
如果x < y，返回-1；如果x = y，返回0；如果x > y，返回1。
顺便一说，JDK中的实现非常简洁，只有一行代码，当判断情况有三种时，使用这种嵌套的判断 x ? a : b 可以简洁不少，这是该学习的。

后面的compareUnsigned是JDK1.8新加入的方法, 用来比较无符号数。这里的无符号数意思是默认二进制最高位不再作为符号位，而是计入数的大小。
其实现是

1
2
3

public static int compareUnsigned(int x, int y) {
    return compare(x + MIN_VALUE, y + MIN_VALUE);
}

直接为每个值加了Integer的最小值 -2³¹。我们知道Java中int类型为4个字节，共32位。符号位占用一位的话，则其范围为-2³¹ 到2³¹ - 1。
使用此方法时，所有正数都比负数小。最大值为 -1，因为 -1的二进制所有位均为 1。
也就是1111 1111 1111 1111 1111 1111 1111 1111 > 其它任何32位数。

关于编码可参考此篇博文计算机编码简介

2.2 String类型的compareTo方法

看完Integer后，我们再来看String中compareTo的实现方式：

public final class String
    implements java.io.Serializable, Comparable<String>, CharSequence {
    /** The value is used for character storage. */
    private final char value[];     // String的值
  
    public int compareTo(String anotherString) {
        int len1 = value.length;
        int len2 = anotherString.value.length;
        int lim = Math.min(len1, len2);     // limit， 表示两个String中长度较小的String长度
        char v1[] = value;
        char v2[] = anotherString.value;

        int k = 0;
        while (k < lim) {
            char c1 = v1[k];
            char c2 = v2[k];
            if (c1 != c2) {
                return c1 - c2;     // 如果char不相同，则取其差值
            }
            k++;    // 如果char值相同，则继续往后比较
        }
        return len1 - len2;     // 如果所有0 ~ (lim - 1)的char均相同，则比较两个String的长短
    }
  // 字面意思是对大小写不敏感的比较器
    public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();
    private static class CaseInsensitiveComparator
            implements Comparator<String>, java.io.Serializable {
        private static final long serialVersionUID = 8575799808933029326L;

        public int compare(String s1, String s2) {  
            int n1 = s1.length();
            int n2 = s2.length();
            int min = Math.min(n1, n2);     // 和上面类似，均是取两个String间的最短长度
            for (int i = 0; i < min; i++) {
                char c1 = s1.charAt(i);
                char c2 = s2.charAt(i);
                if (c1 != c2) {
                    c1 = Character.toUpperCase(c1); // 统一换成大写
                    c2 = Character.toUpperCase(c2); // 统一换成大写
                    if (c1 != c2) {     // 大写如果不相等则再换为小写试试
                        c1 = Character.toLowerCase(c1);
                        c2 = Character.toLowerCase(c2);
                        if (c1 != c2) {     // 到此处则确定不相等
                            // No overflow because of numeric promotion
                            return c1 - c2;
                        }
                    }
                }
            }
            return n1 - n2;
        }

        /** Replaces the de-serialized object. */
        private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
    }
    // String的方法，可以直接使用这个方法和其它String进行比较，
    // 内部实现是调用内部比较器的compare方法
    public int compareToIgnoreCase(String str) {
        return CASE_INSENSITIVE_ORDER.compare(this, str);
    }   
}

String中的关于compare的方法相对复杂一点，但还是比较简单。我们先不看其他的代码，只重点关注compareTo方法。

public int compareTo(String anotherString) {
    int len1 = value.length;
    int len2 = anotherString.value.length;
    int lim = Math.min(len1, len2);     // limit， 表示两个String中长度较小的String长度
    char v1[] = value;
    char v2[] = anotherString.value;

    int k = 0;
    while (k < lim) {
        char c1 = v1[k];
        char c2 = v2[k];
        if (c1 != c2) {
            return c1 - c2;     // 如果char不相同，则取其差值
        }
        k++;    // 如果char值相同，则继续往后比较
    }
    return len1 - len2;     // 如果所有0 ~ (lim - 1)的char均相同，则比较两个String的长短
}

内容很简洁，就是取两个String的长度中较小的，作为限定值(lim)。之后对数组下标为从0到lim - 1的char变量进行遍历比较，如果遇到不相同的值，返回其差值。一般我们只用其正负性，如果返回负数则说明第一个对象比第二个对象“小”。
例如比较 "abc"和"bcd"，当对各自第一个字符'a'和 'b'进行比较时，发现 'a' != 'b'，则返回 'a' - 'b' ，这个值是负数， char类型的-1，Java会自动将其类型强转为int型。最后得出结论"abc"比"bcd"小。

3. Comparator

Comparator<T>接口

1
2
3

public interface Comparator<T> {
    int compare(T o1, T o2);
}

这是一个外部排序接口，它的功能是规定“比较大小”的方式。实现它的类可以作为参数传入Collections.sort()或Arrays.sort()，使用它的比较方式进行排序。
它可以为没有实现Comparable接口的类提供排序方式。
String类中以及Array类等都有实现此接口的内部类。

在上面String的源码中就有一个内部的自定义Comparator类CaseInsensitiveComparator，我们看看它的源码。

    public static final Comparator<String> CASE_INSENSITIVE_ORDER
                                         = new CaseInsensitiveComparator();
    private static class CaseInsensitiveComparator
            implements Comparator<String>, java.io.Serializable {
        private static final long serialVersionUID = 8575799808933029326L;

        public int compare(String s1, String s2) {  
            int n1 = s1.length();
            int n2 = s2.length();
            int min = Math.min(n1, n2);     // 和上面类似，均是取两个String间的最短长度
            for (int i = 0; i < min; i++) {
                char c1 = s1.charAt(i);
                char c2 = s2.charAt(i);
                if (c1 != c2) {
                    c1 = Character.toUpperCase(c1); // 统一换成大写
                    c2 = Character.toUpperCase(c2); // 统一换成大写
                    if (c1 != c2) {     // 大写如果不相等则再换为小写试试
                        c1 = Character.toLowerCase(c1);
                        c2 = Character.toLowerCase(c2);
                        if (c1 != c2) {     // 到此处则确定不相等
                            // No overflow because of numeric promotion
                            return c1 - c2;
                        }
                    }
                }
            }
            return n1 - n2;
        }

        /** Replaces the de-serialized object. */
        private Object readResolve() { return CASE_INSENSITIVE_ORDER; }
    }
    // String的方法，可以直接使用这个方法和其它String进行比较，
    // 内部实现是调用内部比较器的compare方法
    public int compareToIgnoreCase(String str) {
        return CASE_INSENSITIVE_ORDER.compare(this, str);
    }   
}

CaseInsensitiveComparator, 字面意思是对大小写不敏感的比较器。
我们观察它的compare方法，可以发现，它和上面的compareTo方法实现类似，都是取两个String中长度较小的，作为限定值min，之后对数组下标为从0到min - 1的char变量进行遍历比较。和上面稍有不同的是，此处先将char字符统一换成大写（upper case），如果仍然不相等，再将其换为小写（lower case）比较。一个字母只有大写或者小写两种情形，如果这两种情况都不想等则确定不相等，返回其差值。如果限定值内所有的char都相等的话，再去比较两个String类型的长度。

例如比较 "abC"和"ABc"，compareTo会直接返回 'a' - 'A'，而compareToIgnoreCase方法由于使用了CaseInsensitiveComparator，比较结果最终会返回true。

参考文章

【1】Java源码学习之Integer类（二）——1.8新增的几个函数和变量

Steve's Blog

Java中的Comparable接口和Comparator接口