比較器comparator，compare函數升序、降序源碼分析

0、前言

　　一直想不明白，compare函數如何通過傳回值，就确定是升序還是降序呢，于是乎決定好好的先看看源碼。

　　下面的代碼實作了對自己寫的Students類按照年齡升序的排序，就是通過對實作comparator接口，重寫compare的方法，實作對排序的升序或者降序的控制：

import java.util.Arrays;
import java.util.Comparator;
public class learn_comparator{
    public  static class Student {
        public int id;
        public String name;
        public int age;
        public Student(String name, int age, int id) {
            this.id = id;
            this.name = name;
            this.age = age;
        }
    }
    //重寫compare方法，實作按照年齡的升序排列
    public static class ageAscendingComparator implements Comparator<Student>{
        @Override
        public int compare(Student o1, Student o2) {
            return o1.age-o2.age;

    }
    public static void printStudent(Student[] stu){
        for (int i = ; i <stu.length ; i++) {
            System.out.print(stu[i].id);
            System.out.print("  ");
            System.out.print(stu[i].name);
            System.out.print("  ");
            System.out.println(stu[i].age);
        }
    }
    public static void main(String[] args) {
        Student s1=new Student("A",,);
        Student s2=new Student("B",,);
        Student s3=new Student("C",,);
        Student s4=new Student("D",,);
        Student s5=new Student("E",,);
        Student s6=new Student("F",,);
        Student[] arr_stu=new Student[]{s1,s2,s3,s4,s5,s6};
        System.out.println("未排序前的輸出如下：");
        printStudent(arr_stu);
        System.out.println("按照年齡升序排列後輸出如下：");
        Arrays.sort(arr_stu,new ageAscendingComparator());
        printStudent(arr_stu);
    }

}
           

輸出結果：

未排序前的輸出如下：
  A  
  B  
  C  
  D  
  E  
  F  
按照年齡升序排列後輸出如下：
  A  
  F  
  B  
  D  
  E  
  C  
           

1、關于comparator接口

Comparator是一個接口，它包含兩種方法

int compare(T o1, T o2);
    boolean equals(Object obj);
           

一個類要實作Comparator接口，可以隻實作compare函數，因為任何類，預設都是已經實作了equals(Object obj)的。 Java中的一切類都是繼承于java.lang.Object，在Object.java中實作了equals(Object obj)函數

public boolean equals(Object obj) {
        return (this == obj);
    }
           

是以，其它所有的類也相當于都實作了該函數

2、運作程式

①

Arrays.sort(arr_stu,new ageAscendingComparator());

當程式走到這的時候調用了

public static <T> void sort(T[] a, Comparator<? super T> c)；

這個函數（IDEA中ctrl+滑鼠左鍵可以檢視函數），代碼如下

參考：這篇文章

public static <T> void sort(T[] a, Comparator<? super T> c) {
        if (c == null) {
            sort(a);
        } else {

            if (LegacyMergeSort.userRequested)
             /*沒看明白userRequested怎麼得到的，沒有走到這裡 */
                legacyMergeSort(a, c);
            else//函數走到了這
                TimSort.sort(a, , a.length, c, null, , );
        }
    }
           

②

TimSort.sort(a, 0, a.length, c, null, 0, 0);

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                         T[] work, int workBase, int workLen) {
     //assert不滿足，就報錯
   assert c != null && a != null && lo >=  && lo <= hi && hi <= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining < )
            return;  // Arrays of size 0 and 1 are always sorted
   //MIN_MERGE為常數32,如果數組長度小于32，則會調用countRunAndMakeAscending()
 　//函數（重點，升序、降序的關鍵在此函數裡），升序或者降序的數最後一個數的下标+1，
   //指派給initRunLen 數組分為一部分有序、一部分無序。
   //然後使用二分查找插入排序，完後所有的排序
        if (nRemaining < MIN_MERGE) {
            int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
            binarySort(a, lo, hi, lo + initRunLen, c);
            return;
        }
    ***************************************************
    ********　　　>=的部分，還未看　　**************
    ***************************************************


    }
           

③

countRunAndMakeAscending(a, lo, hi, c);

這是最重要的的部分了

private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                  Comparator<? super T> c) {
        assert lo < hi;
        //移動runHi來周遊
        int runHi = lo + ;
        if (runHi == hi)
            return ;

        // Find end of run, and reverse range if descending
        if (c.compare(a[runHi++], a[lo]) < ) { // Descending
            //本例中，後面的隻要比前面的小，就一直往後數
            while (runHi < hi && c.compare(a[runHi], a[runHi - ]) < )
                runHi++;
                //把降序反轉
            reverseRange(a, lo, runHi);
        } else {                              // Ascending

            //本例中，後面的隻要比前面的大，就一直往後面數
            while (runHi < hi && c.compare(a[runHi], a[runHi - ]) >= )
                runHi++;
        }
        //傳回升序的邊界
        return runHi - lo;
    }
           

到此為止，程式已經把數組分成了前一部分升序和後一部分無序了。接下來該用二分查找排序完成排序了

對于二分查找排序的了解，可以參考這篇文章

④

binarySort(a, lo, hi, lo + initRunLen, c);

private static <T> void binarySort(T[] a, int lo, int hi, int start,
                                       Comparator<? super T> c) {
      //start=lo + initRunLen就是找到的升序的邊界
        assert lo <= start && start <= hi;
        if (start == lo)
            start++;
        //周遊無序部分的每一個元素
        for ( ; start < hi; start++) {
            T pivot = a[start];

            int left = lo;
            int right = start;
            assert left <= right;

            while (left < right) {
            //右移一位相當于除以二
                int mid = (left + right) >>> ;
                if (c.compare(pivot, a[mid]) < )
                //将範圍向左，縮小一半
                    right = mid;
                else
                //向右縮小一半
                    left = mid + ;
            }
            assert left == right;
            int n = start - left;  // 需要移動的位數

            switch (n) {
                case :  a[left + ] = a[left + ];
                case :  a[left + ] = a[left];
                         break;
                  //要是移動的位數超過2，就用系統提供的方法；
                default: System.arraycopy(a, left, a, left + , n);
            }
            a[left] = pivot;
        }
    }