Comparable和Comparator对比

Java

描述

自定义的类要按照一定的方式进行排序，比如一个Person类要按照年龄进行从小到大排序，比如一个Student类要按照成绩进行由高到低排序。

这里我们采用两种方式。

使用Comparable接口

让待排序对象所在的类实现Comparable接口，并重写Comparable接口中的compareTo()方法，缺点是只能按照一种规则排序。

1
2
3
public interface Comparable<T> {
    public int compareTo(T o);
}

若在调用Arrays.sort()时，Comparator的参数值为空(如下)，直接调用sort():

1
2
3
4
5
6
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

legacyMergeSort()中调用compareTo()，这也是为什么我们要重写Comparable接口中的compareTo()方法的原因:

1
2
3
4
private static void legacyMergeSort(Object[] a) {
    Object[] aux = a.clone();
    mergeSort(aux, a, 0, a.length, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private static void mergeSort(Object[] src,
                              Object[] dest,
                              int low,
                              int high,
                              int off) {
    int length = high - low;

    // Insertion sort on smallest arrays
    if (length < INSERTIONSORT_THRESHOLD) {
        for (int i=low; i<high; i++)
            for (int j=i; j>low &&
                     ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                swap(dest, j, j-1);
        return;
    }

    // Recursively sort halves of dest into src
    int destLow  = low;
    int destHigh = high;
    low  += off;
    high += off;
    int mid = (low + high) >>> 1;
    mergeSort(dest, src, low, mid, -off);
    mergeSort(dest, src, mid, high, -off);

    // If list is already sorted, just copy from src to dest.  This is an
    // optimization that results in faster sorts for nearly ordered lists.
    if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
        System.arraycopy(src, low, dest, destLow, length);
        return;
    }

    // Merge sorted halves (now in src) into dest
    for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
        if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
            dest[i] = src[p++];
        else
            dest[i] = src[q++];
    }
}

使用Comparator接口

编写多个排序方式类实现Comparator接口，并重写新Comparator接口中的compare()方法，在调用Arrays的sort()时将排序类对象作为参数传入:

1
2
3
4
5
6
7
8
9
10
11
// Arrays.sort()
public static <T> void sort(T[] a, Comparator<? super T> c) {
    if (c == null) {
        sort(a);
    } else {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a, c);
        else
            TimSort.sort(a, 0, a.length, c, null, 0, 0);
    }
}

根据指定比较器产生的顺序对指定对象数组进行排序。数组中的所有元素都必须是通过指定比较器可相互比较的(也就是说，对于数组中的任何e1和e2元素而言，c.compare(e1, e2)不得抛出ClassCastException)。

优点是可以按照多种方式排序，你要按照什么方式排序，就创建一个实现Comparator接口的排序方式类，然后将该排序类的对象传入到Arrays.sort(待排序对象，该排序方式类的对象)。

示例

使用Comparable接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Arrays;  
/** 
 * 使用Comparable接口：让待排序对象所在的类实现Comparable接口，并重写Comparable接口中的compareTo()方法 
 * 缺点是只能按照一种规则排序 
 * 
 */  
public class ObjectSort {  
  
    public static void main(String[] args) {  
        Person[] persons = new Person[5];  
        persons[0] =new Person("tom",45);  
        persons[1] =new Person("jack",12);  
        persons[2] =new Person("bill",21);  
        persons[3] =new Person("kandy",34);  
        persons[4] =new Person();  
        Arrays.sort(persons);  
        for (Person person : persons) {  
            System.out.println(person);  
        }  
    }  
}  

class Person implements Comparable<Person>{  
    private String name;  
    private int age;  
      
    public Person(String name, int age){  
        this.name = name;  
        this.age = age;  
    }  
    public Person(){  
        this("unknown", 0);  
    }  
    //重写该类的compareTo()方法，使其按照从小到大顺序排序  
    @Override  
    public int compareTo(Person o) {  
         return age - o.age;  
          
    }  
    //重写Student类的toString()方法，在输入对象时按照以下方式输出  
    @Override  
    public String toString() {        
        return "Person[name:"+name+",age:"+age+"]";  
    }  
}

使用Comparator接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
import java.util.Arrays;  
import java.util.Comparator;  
  
/** 
 * 使用Comparator接口：编写多个排序方式类实现Comparator接口，并重写新Comparator接口中的compare()方法 
 * public static <T> void sort(T[] a,Comparator<? super T> c),根据指定比较器产生的顺序对指定对象数组进行排序。数组中的所有元素都必须是通过指定比较器可相互比较的 
 * （也就是说，对于数组中的任何 e1 和 e2 元素而言，c.compare(e1, e2) 不得抛出 ClassCastException）。 
 * 优点是可以按照多种方式排序，你要按照什么方式排序，就创建一个实现Comparator接口的排序方式类，然后将该排序类的对象传入到Arrays.sort(待排序对象，该排序方式类的对象) 
 * 
 */  
  
public class ComparatorUse {  
    public static void main(String[] args) {  
        Student[] persons = new Student[5];  
        persons[0] =new Student("tom",1,88,45);  
        persons[1] =new Student("jack",6,80,12);  
        persons[2] =new Student("bill",4,68,21);  
        persons[3] =new Student("kandy",2,98,34);  
        persons[4] =new Student("lily",5,94,20);  
        System.out.println("排序前的数据：");  
        for (Student student : persons) {  
            System.out.println(student);  
        }  
        
        //创建SortByNumber对象，将其作为参数传入Arrays.sort(persons, sortByNumber)方法中  
        SortByNumber sortByNumber = new SortByNumber();  
        Arrays.sort(persons, sortByNumber);  
        System.out.println("根据学生编号由低到高排序：");  
        for (Student student : persons) {  
            System.out.println(student);  
        }  
        
        SortByScore sortByScore = new SortByScore();  
        Arrays.sort(persons, sortByScore);  
        System.out.println("根据学生成绩由高到低排序：");  
        for (Student student : persons) {  
            System.out.println(student);  
        }  
    }  
}  
  
class Student {  
    private String name;  
    private int number;  
    private int score;  
    private int age;  
      
    public Student(String name, int number, int score, int age){  
        this.name = name;  
        this.number = number;  
        this.score = score;  
        this.age = age;  
    }  
    //重写Student类的toString()方法，在输入对象时按照以下方式输出  
    @Override  
    public String toString() {        
        return "Student[name:"+name+",age:"+age+",number:"+number+",score:"+score+"]";  
    }  
  
    public String getName() {  
        return name;  
    }  
  
    public void setName(String name) {  
        this.name = name;  
    }  
  
    public int getNumber() {  
        return number;  
    }  
  
    public void setNumber(int number) {  
        this.number = number;  
    }  
  
    public int getScore() {  
        return score;  
    }  
  
    public void setScore(int score) {  
        this.score = score;  
    }  
  
    public int getAge() {  
        return age;  
    }  
  
    public void setAge(int age) {  
        this.age = age;  
    }  
}  

//按照学号由低到高排列,创建SortByNumber类，该类实现Comparator，重写该接口的compare()  
class SortByNumber implements Comparator<Student>{  
    //重写该接口的compare()使其按照学号由小到大排序（前者减去后者）  
    @Override  
    public int compare(Student o1, Student o2) {  
        return o1.getNumber() - o2.getNumber();  
    }  
}  

//按照分数由高到低排列，创建SortByScore类，该类实现Comparator，重写该接口的compare()  
class SortByScore implements Comparator<Student>{  
    //重写该接口的compare()使其按照分数由高到低排序（后者减去前者）  
    @Override  
    public int compare(Student o1, Student o2) {  
        return o2.getScore() - o1.getScore();  
    }  
}

Arrays.sort()实现原理

既然说了这么多，还是分析一下Arrays.sort()的实现原理吧。java中Arrays.sort()使用了两种排序方法，快速排序和优化的归并排序。快速排序主要是对那些基本类型数据(int, short, long等)排序，而归并排序用于对对象类型进行排序。

使用不同类型的排序算法主要是由于快速排序是不稳定的，而归并排序是稳定的。这里的稳定是指比较相等的数据在排序之后仍然按照排序之前的前后顺序排列。对于基本数据类型，稳定性没有意义，而对于对象类型，稳定性是比较重要的，因为对象相等的判断可能只是判断关键属性，最好保持相等对象的非关键属性的顺序与排序前一致；另外一个原因是由于归并排序相对而言比较次数比快速排序少，移动（对象引用的移动）次数比快速排序多，而对于对象来说，比较一般比移动耗时。

归并排序的时间复杂度是n*logn, 快速排序的平均时间复杂度也是n*logn，但是归并排序的需要额外的n个引用的空间。

我们注意到在上面提到的sort(T[] a, Comparator<? super T> c)。sort的第2个参数里面的<? super T>意味着比较器所接受的类型可以是T或者它的超类. 为什么是超类呢? 答案是这允许使用同一个比较器对不同的子类对象进行比较。

基本类型源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
     * Sorts the specified array into ascending numerical order.
     *
     * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
     * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
     * offers O(n log(n)) performance on many data sets that cause other
     * quicksorts to degrade to quadratic performance, and is typically
     * faster than traditional (one-pivot) Quicksort implementations.
     *
     * @param a the array to be sorted
     */
    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

从名字可见确实是快排。

对象类型源码

1
2
3
4
5
6
public static void sort(Object[] a) {
    if (LegacyMergeSort.userRequested)
        legacyMergeSort(a);
    else
        ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
}

ComparableTimSort.sort:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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;
    }

    /**
     * March over the array once, left to right, finding natural runs,
     * extending short natural runs to minRun elements, and merging runs
     * to maintain stack invariant.
     */
    ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
    int minRun = minRunLength(nRemaining);
    do {
        // Identify next run
        int runLen = countRunAndMakeAscending(a, lo, hi);

        // 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);
            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;
}

这里发现如果元素少于MIN_MERGE == 32采用binarySort(二分排序)；后面还有些判断bla bla，最后采用mergeForceCollapse(归并排序)。

我们之后会看到Java.util.Collections#sort(List<T> list, Comparator<? super T> c)与Arrays.sort()使用类似的思想。

BTW，有些东西还是要看源码才清楚的。