MasterYangBlog
首页
时间轴
标签
分类
友链
留言板
关于
avatar
文章
72
标签
51
分类
27
首页
时间轴
标签
分类
友链
留言板
关于
目录
  1. 1. 1. Comparable源码分析
    1. 1.1. 1.1创建Java工程，实现Comparable接口
    2. 1.2. 1.2 编写测试类
    3. 1.3. 1.3 Collections类中的泛型方法sort()
    4. 1.4. 1.4 List接口中的默认方法sort()
    5. 1.5. 1.5 ArrayList集合中的方法sort()
    6. 1.6. 1.6 Arrays类中的sort()方法
    7. 1.7. 1.7 ComparableTimSort类中的sort()方法
  2. 2. 2. Comparator源码分析
    1. 2.1. 2.1 创建JavaBean
    2. 2.2. 2.2 创建外部比较器
    3. 2.3. 2.3 创建测试类
    4. 2.4. 2.4 Collections类中的泛型方法sort()
    5. 2.5. 2.5 ArrayList集合中的方法sort()
    6. 2.6. 2.6 Arrays类中的sort()方法
    7. 2.7. 2.7 TimSort类下的sort()方法
  3. 3. 3. 总结
Comparable和Comparator底层源码分析
|Java基础知识
阅读量:

1. Comparable源码分析

1.1创建Java工程，实现Comparable接口

java
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.io.Serializable;

//实现Serializable，标识该类可被序列化
//实现Comparable接口，让此类可以利用Collections.sort()进行排序

public class User<T extends User> implements Serializable,Comparable<T>{
    private String name;
    private int age;
    private transient String address;//transient修饰，标识该类序列化时此字段不需要进行存储
    public User(String name){
        this.name = name;
    }

    public User(String name,int age,String address){
        this(name);
        this.age = age;
        this.address = address;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public String getAddress() {
        return address;
    }

    @Override
    public int compareTo(T o) {
        //在此处打上断点，方便进行调试
        int returnInt = 0;
        if(age>o.getAge()){
            returnInt=1;
        }else if(age==o.getAge()){
            returnInt=0;
        }else if(age<o.getAge()){
            returnInt=-1;
        }
        return returnInt;
    }
}

1.2 编写测试类

java
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
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestComparable {
    public static void main(String[] args) {
        User u1 = new User("caililiang1",20,"hubei1");
        User u2 = new User("caililiang2",30,"hubei2");
        User u3 = new User("caililiang3",25,"hubei3");
        User u4 = new User("caililiang4",28,"hubei4");
        User u5 = new User("caililiang5",23,"hubei5");

        List<User> list = new ArrayList<User>();
        list.add(u1);
        list.add(u2);
        list.add(u3);
        list.add(u4);
        list.add(u5);

        for(int i=0;i<list.size();i++){
            User u =list.get(i);
            System.out.println(u.getName()+"--->"+u.getAge());
        }
        System.out.println("排序后---------------------");
        
        //在此处打上断点，方便进行调试
        Collections.sort(list);
        for(int i=0;i<list.size();i++){
            User u =list.get(i);
            System.out.println(u.getName()+"--->"+u.getAge());
        }
    }
}

1.3 Collections类中的泛型方法sort()

java
1
2
3
4
5
6
7
// 此处 <T extends Comparable<? super T>> 的意思是：
// 1.<T extends Comparable>表示比较对象的类必须是Comparable 的子类。
// 2.Comparable<? super T>表示是Comparable实现类及以上。
public static <T extends Comparable<? super T>> void sort(List<T> list) {
       //调用List接口中的sort()方法
       list.sort(null);
   }

1.4 List接口中的默认方法sort()

java
1
2
3
4
5
6
7
8
9
10
11
// 由于本例中采用的是ArrayList集合，ArrayList集合对List接口中的sort()方法进行了重写，
// 因此实际在DeBug的过程中会执行ArrayLIst类中的sort()方法    
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);
        }
    }

1.5 ArrayList集合中的方法sort()

java
1
2
3
4
5
6
7
8
9
10
11
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    //此方法直接调用Arrays类中sort()方法
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

1.6 Arrays类中的sort()方法

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> c) {
    //在1.3中传入的 c值为null,所以调用sort(a, fromIndex, toIndex)方法
    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);
    }
}

public static void sort(Object[] a, int fromIndex, int toIndex) {
    rangeCheck(a.length, fromIndex, toIndex);
    if (LegacyMergeSort.userRequested)
        //归并排序
        legacyMergeSort(a, fromIndex, toIndex);
    else
        //二进制插入排序
        ComparableTimSort.sort(a, fromIndex, toIndex, null, 0, 0);
}

解析：源码里首先判断是否采用传统的排序方法,LegacyMergeSort.userRequested属性默认为false,也就是说默认选中 ComparableTimSort.sort(a)方法(传统归并排序在1.5及之前是默认排序方法，1.5之后默认执行ComparableTimSort.sort()方法。除非程序中强制要求使用传统归并排序,语句如下：System.setProperty(“java.util.Arrays.useLegacyMergeSort”, “true”))
继续看 ComparableTimSort.sort(a)源码

1.7 ComparableTimSort类中的sort()方法

java
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
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;
       
       //nRemaining表示没有排序的对象个数，方法执行前，如果这个数小于2，就不需要排序了。
       //如果2<= nRemaining <=32,即MIN_MERGE的初始值，表示需要排序的数组是小数组
       //可以使用mini-TimSort方法进行排序，否则需要使用归并排序。
       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) {
           //调用重写的compareTo()方法
           int initRunLen = countRunAndMakeAscending(a, lo, hi);
           //只看这一句
           binarySort(a, lo, hi, lo + initRunLen);
           return;
       }
    ......
   }


//这里才是真正的调用compareTo()方法对当前对象进行比较
   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
       if (((Comparable) a[runHi++]).compareTo(a[lo]) < 0) { // 降序排列
           while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) < 0)
               runHi++;
           reverseRange(a, lo, runHi);
       } else {// 升序排列
           while (runHi < hi && ((Comparable) a[runHi]).compareTo(a[runHi - 1]) >= 0)
               runHi++;
       }

       return runHi - lo;
   }


//这里才是真正的进行排序。
   private static void binarySort(Object[] a, int lo, int hi, int start) {
       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).
            */
           while (left < right) {
               int mid = (left + right) >>> 1;
               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;
       }
   }

2. Comparator源码分析

2.1 创建JavaBean

java
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
import java.io.Serializable;


public class People implements Serializable {
    private String name;
    private int age;
    private transient String address;//transient修饰，标识该类序列化时此字段不需要进行存储

    public People(String name){
        this.name = name;
    }

    public People(String name,int age,String address){
        this(name);
        this.age = age;
        this.address = address;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    public String getAddress() {
        return address;
    }
}

2.2 创建外部比较器

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.Comparator;

public class PeopleComparator<T extends People> implements Comparator<T> {
    public int compare(T o1, T o2) {
        int returnInt = 0;
        if(o1.getAge()>o2.getAge()){
            returnInt = 1;
        }else if(o1.getAge()==o2.getAge()){
            returnInt = 0;
        }else if(o1.getAge()<o2.getAge()){
            returnInt = -1;
        }
        return returnInt;
    }
}

2.3 创建测试类

java
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
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TestComparator {
    public static void main(String[] args) {
        People u1 = new People("caililiang1",20,"hubei1");
        People u2 = new People("caililiang2",30,"hubei2");
        People u3 = new People("caililiang3",25,"hubei3");
        People u4 = new People("caililiang4",28,"hubei4");
        People u5 = new People("caililiang5",23,"hubei5");

        List<People> list = new ArrayList<People>();
        list.add(u1);
        list.add(u2);
        list.add(u3);
        list.add(u4);
        list.add(u5);

        for(int i=0;i<list.size();i++){
            People u =list.get(i);
            System.out.println(u.getName()+"--->"+u.getAge());
        }

        System.out.println("排序后---------------------");

        Collections.sort(list,new PeopleComparator());

        for(int i=0;i<list.size();i++){
            People u =list.get(i);
            System.out.println(u.getName()+"--->"+u.getAge());
        }
    }
}

2.4 Collections类中的泛型方法sort()

java
1
2
3
4
5
   @SuppressWarnings({"unchecked", "rawtypes"})
//此处调用的是sort方法的重载方法，与案例一中不同
   public static <T> void sort(List<T> list, Comparator<? super T> c) {
       list.sort(c);
   }

2.5 ArrayList集合中的方法sort()

java
1
2
3
4
5
6
7
8
9
10
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

2.6 Arrays类中的sort()方法

java
1
2
3
4
5
6
7
8
9
10
11
12
public static <T> void sort(T[] a, int fromIndex, int toIndex, Comparator<? super T> 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);
    }
}

2.7 TimSort类下的sort()方法

java
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
static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> 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)
        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, c);
        binarySort(a, lo, hi, lo + initRunLen, c);
        return;
    }
    
    
 private static <T> void binarySort(T[] a, int lo, int hi, int start, Comparator<? super T> c) {
    assert lo <= start && start <= hi;
    if (start == lo)
        start++;
    for ( ; start < hi; start++) {
        T pivot = 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).
         */
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (c.compare(pivot, 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;
    }
}

3. 总结

  1. Comparable 此接口强行对实现它的每个类的对象进行整体排序。这种排序被称为类的自然排序，类的compareTo()方法被称为它的自然比较方法。 实现此接口的对象列表（集合和数组）可以通过 Collections.sort和 Arrays.sort 进行自动排序。实现此接口的对象可以用作有序映射中的键或有序集合中的元素，无需指定比较器。

    Arrays.sort(people)

  2. Comparator 是比较器，排序时，需要新建比较器对象，将比较器和对象一起传递过去就可以比大小，可称为“外部排序”。比较器是定义在要比较对象的外部的, 必须要重写compare()方法，而需要比较的类的结构不需要有任何变化。并且在Comparator 里面用户可以自己实现复杂的可以通用的逻辑,使其可以匹配一些比较简单的对象,那样就可以节省很多重复劳动了。

    Arrays.sort(people,new PersonCompartor());

  3. 关于两个类的具体应用场景可以理解为，自己在创建一个工程时可以使用Comparable进行排序，当工程创建完毕时添加新的排序功能时，可以使用Comparator，无需改变类的结构。

文章作者: Yang4
文章链接: https://masteryang4.github.io/2020/03/15/Comparable%E5%92%8CComparator%E5%BA%95%E5%B1%82%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 MasterYangBlog！
源码 易错点 Java
打赏
  • 微信
    微信
  • 支付宝
    支付宝
相关推荐
2020-03-16
HashMap底层实现源码分析
2020-03-12
ArrayList底层实现源码分析(JDK1.8)
2020-05-12
JUnit常用注解
2020-04-30
HashMap文章推荐
2020-04-29
Java IO相关总结归纳
2020-04-18
Java空指针问题的本质
评论
简