java comparator 升序、降序、倒序从源码角度理解

环境

jdk:1.7+

前言

之前我写过关于comparator的理解，但是都理解错了。

java 自定义排序【Comparator升序降序的记法】

特别是 上面这篇，完全理解错了，排序的真正的意思。

最近通过查看源码，打断点的方式，一步步的查看、演算。算是明白了！

真正正确的理解：
① jdk官方默认是升序，是基于：

< return -1 = return 0 > return 1

如果要降序就必须完全相反：

< return 1 = return 0 > return -1

为什么呢？这个只能通过源码的方式去看了。

测试代码

首先，我写了如下的测试代码:

public static void main(String[] args) { List 
  
    re = 
   new ArrayList<>(); re.add( 
   1); re.add( 
   2); re.add( 
   6); re.add( 
   5); re.add( 
   8); re.add( 
   8); re.add( 
   4); Collections.sort(re, 
   new Comparator 
   
     () { 
    @Override 
    public 
    int 
    compare(Integer o1, Integer o2) { 
    //下面这么写，结果是降序 
    if(o1 < o2){ 
    return 
    1; } 
    else 
    if(o1 > o2){ 
    return - 
    1; } 
    return 
    0; } }); System.out.println(re); } 
    
  

降序

开始debug测试：

第一步： 程序先调用如下方法：

 @SuppressWarnings({ 
  "unchecked", "rawtypes"}) public static 
   
   void 
   sort(List 
   
     list, Comparator 
    super T> c) { list.sort(c); } 
    
  

第二步： 而list.sort(c)源码：
这里调用的是ArrayList类的方法：

@SuppressWarnings({ 
  "unchecked", "rawtypes"}) default void sort(Comparator 
   c) { Object[] a = this.toArray(); // 主要看到这里 Arrays.sort(a, (Comparator) c); ListIterator 
  
    i = 
   this.listIterator(); 
   for ( 
   Object e : a) { i.next(); i. 
   set((E) e); } } 
  

第三步：调用Arrays.sort(a, (Comparator) c);方法：

public static 
   
   void 
   sort(T[] a, Comparator 
   super T> c) { 
   if (c == 
   null) { sort(a); } 
   else { 
   if (LegacyMergeSort.userRequested) legacyMergeSort(a, c); 
   else 
   //接下来会走这个方法，上面不会走； 
   //未来jdk会弃用legacyMergeSort方法。 TimSort.sort(a, 
   0, a.length, c, 
   null, 
   0, 
   0); } } 
  

第四步：TimSort.sort(a, 0, a.length, c, null, 0, 0);这个方法很长，我先贴出主要核心的：

if (nRemaining < MIN_MERGE) { int initRunLen = //这个方法就大致决定是顺序 countRunAndMakeAscending(a, lo, hi, c); binarySort(a, lo, hi, lo + initRunLen, c); return; }

第五步：countRunAndMakeAscending方法：

private static 
   
   int 
   countRunAndMakeAscending(T[] a, 
   int lo, 
   int hi, Comparator 
   super T> c) { 
   // lo 是数组起始位置 也就是 0  
   assert lo < hi; 
   // runHi = 1，这个值会随着循环而改变，表示当前元素的位置 
   int runHi = lo + 
   1; 
   // hi是数组长度 
   if (runHi == hi) 
   return 
   1; 
   // Find end of run, and reverse range if descending 
   //这里c.compare()调用就是我们重写的方法 
   if (c.compare(a[runHi++], a[lo]) < 
   0) { 
   // Descending 
   while (runHi < hi && c.compare(a[runHi], a[runHi - 
   1]) < 
   0) runHi++; reverseRange(a, lo, runHi); } 
   else { 
   // Ascending -- 英文的注释，默认是升序；不用管这个注释 
   while (runHi < hi && c.compare(a[runHi], a[runHi - 
   1]) >= 
   0) runHi++; } 
   return runHi - lo; } 
  

这个方法就是关键；

我上面创建了一个数组：

1 2 6 5 8 8 4 //其中 < 1 = 0 > -1

if (c.compare(a[runHi++], a[lo]) < 0) — 这句代码，对我的测试代码而言：if (c.compare(2, 1) < 0)中c.compare(2,1)得到的就是-1。接着就是执行：

while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi);

while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0)中c.compare(a[runHi], a[runHi - 1]) < 0)就是c.compare(6, 2) < 0)，而c.compare(6, 2)返回的是-1，所以会接着循环执行，runHi++后,此时runHi=2。就我的测试代码就会去判断c.compare(5, 6)，其返回的是1，循环结束，接着执行reverseRange(a, lo, runHi);。这个是个反转方法。
效果就是：

数组：1 2 6 5 8 8 4 反转后：6 2 1 5 8 8 4

可以看出，前面三个数字顺序已经好了，后面的5 8 8 4，会在执行binarySort(a, lo, hi, lo + initRunLen, c);这个方法时来进行二分插入排序。

第六步：执行binarySort(a, lo, hi, lo + initRunLen, c);方法：

private static 
   
   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) { 
   //这里相当于除以2 
   int mid = (left + right) >>> 
   1; 
   if (c.compare(pivot, a[mid]) < 
   0) right = mid; 
   else left = mid + 
   1; } 
   //当left等于right时，就说明找到位置了。 
   //assert是断言，要是为false会直接报错 
   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; 
   //要是移动的位数大于2，就执行如下方法； 
   default: System.arraycopy(a, left, a, left + 
   1, n); } a[left] = pivot; } } 
  

例子中的数组：

6 2 1 5 8 8 4 //循环执行binarySort方法后， //会依次把 5 8 8 4 插入到相应的位置 //最终的结果为： // 8 8 6 5 4 2 1

升序

这是，jdk默认的顺序，例子：

< -1 > 1 =0 1 2 6 5 8 8 4

执行步骤和上面降序是一样的，我就直接分析核心部分了：

// Find end of run, and reverse range if descending if (c.compare(a[runHi++], a[lo]) < 0) { // Descending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { // Ascending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++; }

当执行到这里时，c.compare(a[runHi++], a[lo]) < 0就是c.compare(2, 1) < 0，而`c.compare(2, 1)返回的是1，那么程序就会进入else的部分：

while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++;

代码c.compare(a[runHi], a[runHi - 1])就是c.compare(6, 2)返回的是1符合条件（大于0），
runHi++,此时runHi=3。c.compare(a[runHi], a[runHi - 1])就是c.compare(5, 6)，其返回的是-1，不符合条件。循环结束，数组结果为：

//可以看出什么都没有变 1 2 6 5 8 8 4 //但是方法的`return runHi - lo;`这个返回的结果就是3 //这个返回值，会在`binarySort(a, lo, hi, lo + initRunLen, c);`中用到。

下一步：执行binarySort(a, lo, hi, lo + initRunLen, c);其中initRunLen = 3；
在执行二分插入时，就会从数组下标为3开始；

1 2 6 5 8 8 4 //从下标为3，开始二分插入排序；即从5开始。 1 2 5 6 8 8 4 接着是8 1 2 5 6 8 8 4 接着是第二个8 1 2 5 6 8 8 4 接着是4 1 2 4 5 6 8 8

通过升序和降序，我们基本可以知道排序步骤：
①countRunAndMakeAscending这个方法确定是顺序还是降序，并且将数组的一部分排列好。并返回未排列的起始位置
②将未排列的起始位置传递给binarySort进行二分插入排序。

倒序

我们先来看看倒序的结果：

1 2 6 5 8 8 4 倒序后： 4 8 8 5 6 2 1 //怎么做到呢？ //不管大于、小于和等于 都返回 -1

从源码上看countRunAndMakeAscending方法：

f (c.compare(a[runHi++], a[lo]) < 0) { // Descending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { // Ascending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++; }

c.compare()得到的永远都是-1，所以其会将下面这段代码执行完毕：

while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++;

循环完毕后，此时runHi就是数组的长度7。
接着执行reverseRange(a, lo, runHi);，将整个数组进行倒序。
该方法完全执行完成后，返回值就是数组长度。
此时再执行binarySort方法时，for ( ; start < hi; start++)中的start是刚刚传进来的值，也就是数组长度，而hi也是数组长度，所以二分插入方法什么都没有做，只是调用了下。

0 到底是什么作用

假设不管大于、小于、等于，我们都返回0 ，会发现顺序没有变；而且你会发现，要是都返回1的话，顺序也是没有变的！

从countRunAndMakeAscending方法中可以得出结论：

// Find end of run, and reverse range if descending if (c.compare(a[runHi++], a[lo]) < 0) { // Descending while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) < 0) runHi++; reverseRange(a, lo, runHi); } else { //走这个循环  while (runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0) runHi++; }

当不管大于、小于、等于时，我们都返回一个值时，0和1效果是一样的，就是不排序；-1就是倒序。

可以要是 是如下写法：

public int compare(Integer o1, Integer o2) { if(o1 < o2){ return 1; }/*else if(o1 > o2){ return 1; }*/ return -1; }

也就是 我们把等于和大于都返回-1，小于返回1。发现也是可以降序的，或者反过来，就是升序。视乎觉得0好像是多余的。

其实0表示的是，相同元素不排序，要是我们把等于返回为-1，那么两个相同的元素会交互顺序；

1 2 6 5 8 8 4 //也就是这里面两个8 会交换顺序

对数字而言交换顺序没有关系，但是里面要是是Map对象的话，那就有关系，因为有时我们是希望相同元素不进行顺序调整的。

要是我们把等于返回为1效果和0是一样的都是不排序。

总结

排序其实是由三个数字同时决定的；

升序（默认，即官方定义，毕竟代码实现就是基于这个写的）：

< -1 = 0 //或者 1效果是一样的；-1相同元素会发生位置调整 > 1

降序：

< 1 = 0 //或者 1效果是一样的；-1相同元素会发生顺序调整 > -1

倒序：

//直接  return -1;

不改变顺序：

//直接 return 0或者1;

底层做法是：先确定局部顺序，再利用二分查找法，进行后续排序：

数组：1 2 6 5 8 8 4 反转后：6 2 1 5 8 8 4

这里先确定了6 2 1的顺序，后面5 8 8 4的位置就是利用二分查找法来确定的！