比较器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;
        }
    }