走进java比较器Comparator的底层实现原理

系统管理员 2023-09-28 10:02 19阅读 0赞

### 一、前言 ###

在文章：[Java自定义Comparator实现复杂排序][Java_Comparator] 中我们讨论了如何自定义Comparator实现复杂排序，其中聊到Comparator接口的`compare(T o1, T o2)`方法中：o1 和 o2的在排序前集合中的顺序为：o2在o1前面。为什么是这样的呢？自定义的Comparator是如何使用到的？

本文我们就撸一撸JDK中List.sort()的源码，找一下哪里使用到了我们自定义的Comparator。

### 二、哪里使用了Comparator ###

接着博文[Java自定义Comparator实现复杂排序][Java_Comparator]中的内容，我们打断点做debug；  
![在这里插入图片描述][fc2cc00d40e141eca860a3299115d20c.png]  
我们发现在users.sort()方法出按F7不会进入sort()方法内部，莫方，由于我们实例的List对象是ArrayList，我们进入ArrayList类中找到sort()方法，把断点安排上；  
![在这里插入图片描述][3e7c4e14ed5942e0a913c0d50bb0cc77.png]

再debug，发现可以进入sort()方法了：

![在这里插入图片描述][ceb4d6e259584c08a52a6298f1212877.png]  
接着往里跟，代码执行流程如下：  
![在这里插入图片描述][0f1d3ae8acf84d7591383563ccf33785.png]

最终进入到TimeSort.sort()方法；其中采用快速排序算法对数组进行排序；我们发现只有两处方法实质用到了传入的Comparator，这两个方法是 负责查出数组一直到第几个数为止有序的`countRunAndMakeAscending(a, lo, hi, c)`方法 和 负责对数组进行快速排序的`binarySort(a, lo, hi, lo + initRunLen, c)`方法；即Comparator的底层实现原理就体现在这两个方法中，下面我们分开来讨论一下，Comparator在其中充当什么角色？

#### 1、TimeSort\#countRunAndMakeAscending()方法 ####

private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                        Comparator<? super T> c) {
        
            // lo表示数组的起始位置 即：数组下标0
            assert lo < hi;
            int runHi = lo + 1;
            // hi表示数组长度
            if (runHi == hi)
                return 1;
    
            // c.compare()方法就是我们自定义的
            // 如果按照指定规则数组的前一段是“降序”的，需要反转为正序
            if (c.compare(a[runHi++], a[lo]) < 0) {
         // Descending
                // 从这里可以看到传入到compare(o1, o2)方法的参数，在原数组中 o2 在 o1 前面
                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++;
            }
    
            // 表示 runHi -lo个元素已经按规则“正序”排好序了
            return runHi - lo;
        }

countRunAndMakeAscending()方法 返回 按照指定排序规则（这个排序规则就是我们定义的Comparator中的compare()方法，返回-1表示“降序”，即需要反转的意思。）数组中升序的那一段元素的个数 或 反转后 数组中降序的那一段元素的个数。

#### 2、 TimeSort\#binarySort() ####

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

binarySort()方法逻辑：

> 1.  从start（数组中第一个不遵循“升序”规则的数组下标）开始，pivot=array\[start\]，使用二分查找法对start之前已经有序的数组比对，从start下标开始从后往前找，找到start下标之前第一个大于array\[start\]的元素下标index；
> 2.  将`ndex, start-1`\]范围内的数组值`都向后移动一位`，放在 `[index+1~start]`，再把pivot的值赋予array\[index\]（即`array[index]=pivot`）；
> 3.  start++，然后执行1，2步骤直到`start==array.klength结束`。

在这里，我们定义的Comparator中的compare()方法充当着`排序规则`这个角色，返回-1表示“降序”，即需要反转为“升序”；返回0 和 1表示“升序”，即顺序不变。

### 三、总结 ###

我们自定义的Comparator或者默认的Comparator，都是作为一个排序规则最终传递到TimeSort\#binarySort()方法中：

>  *  返回-1表示“降序”，需要交换两个数据的位置，即反转为“升序”；
>  *  返回0 和 1表示“升序”，即两个数据的位置顺序不变。

[Java_Comparator]: https://blog.csdn.net/Saintmm/article/details/125218362
[fc2cc00d40e141eca860a3299115d20c.png]: https://img-blog.csdnimg.cn/fc2cc00d40e141eca860a3299115d20c.png
[3e7c4e14ed5942e0a913c0d50bb0cc77.png]: https://img-blog.csdnimg.cn/3e7c4e14ed5942e0a913c0d50bb0cc77.png
[ceb4d6e259584c08a52a6298f1212877.png]: https://img-blog.csdnimg.cn/ceb4d6e259584c08a52a6298f1212877.png
[0f1d3ae8acf84d7591383563ccf33785.png]: https://img-blog.csdnimg.cn/0f1d3ae8acf84d7591383563ccf33785.png