• Java List.sort()的使用 和Comparator转换器的实现原理


    我在使用List.sort()方法的自定义比较器排序的时候,想当然认为(O1,O2)->{} o1是集合中前一个元素,o2是后一个元素,返回-1是交换元素位置,1是不交换元素位置,结果我的排序正好和我想要的相反,百度了一下,发现不少讲解帖子也都是错误的,正确的结论是:

    o2在o1前面,返回-1 表⽰交换o2 和 o1的顺序;
    返回0 和 1都表示不交换o2 和 o1的顺序;

    来看一下list.sort()的源码

    java/util/ArrayList.java:1460
        @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++;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    再点进去

    java/util/Arrays.java:1503
    public static <T> void sort(T[] a, int fromIndex, int toIndex,
                                    Comparator<? super T> c) {
            if (c == null) {
            //没有传比较器的情况,使用默认sort排序
                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);
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    再点进去rangeCheck这个方法

    java/util/Arrays.java:111
    arrayLength--数组长度 fromIndex--开始排序时的索引位置 toIndex--结束排序时的索引位置
    private static void rangeCheck(int arrayLength, int fromIndex, int toIndex) {
            if (fromIndex > toIndex) {
                throw new IllegalArgumentException(
                //开始排序时的索引位置 大于结束排序时的索引位置 抛出参数校验非法异常
                        "fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")");
            }
            if (fromIndex < 0) {
            //数组下标越界异常
                throw new ArrayIndexOutOfBoundsException(fromIndex);
            }
            if (toIndex > arrayLength) {
            //数组下标越界异常
                throw new ArrayIndexOutOfBoundsException(toIndex);
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    再来这个LegacyMergeSort.userRequested 用户可以设置这个为true来启用传统归并排序,我们不用关心这个
    然后看 TimSort.sort(a, fromIndex, toIndex, c, null, 0, 0);
    点进去

    java/util/TimSort.java:210
        static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                             T[] work, int workBase, int workLen) {
                             //断言 当这个返回false是会从这里停止执行代码
                             //
            assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;
    
            int nRemaining  = hi - lo;
            //数组大小为0或者1不需要排序
            if (nRemaining < 2)
                return;  // Arrays of size 0 and 1 are always sorted
    
            // If array is small, do a "mini-TimSort" with no merges
            //32 代表数组长度小于此值的时候使用 mini-TimSort 排序
            if (nRemaining < MIN_MERGE) {
                int initRunLen = countRunAndMakeAscending(a, lo, hi, c);
                binarySort(a, lo, hi, lo + initRunLen, c);
                return;
            }
    
            /**
             * March over the array once, left to right, finding natural runs,
             * extending short natural runs to minRun elements, and merging runs
             * to maintain stack invariant.
             */
            TimSort<T> ts = new TimSort<>(a, c, work, workBase, workLen);
            int minRun = minRunLength(nRemaining);
            do {
                // Identify next run
                int runLen = countRunAndMakeAscending(a, lo, hi, c);
    
                // If run is short, extend to min(minRun, nRemaining)
                if (runLen < minRun) {
                    int force = nRemaining <= minRun ? nRemaining : minRun;
                    binarySort(a, lo, lo + force, lo + runLen, c);
                    runLen = force;
                }
    
                // Push run onto pending-run stack, and maybe merge
                ts.pushRun(lo, runLen);
                ts.mergeCollapse();
    
                // Advance to find next run
                lo += runLen;
                nRemaining -= runLen;
            } while (nRemaining != 0);
    
            // Merge all remaining runs to complete sort
            assert lo == hi;
            ts.mergeForceCollapse();
            assert ts.stackSize == 1;
        }
    
    • 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

    首先看第一个 countRunAndMakeAscending

    java/util/TimSort.java:347
        private static <T> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                        Comparator<? super T> c) {
            assert lo < hi;
            int runHi = lo + 1;
            if (runHi == hi)
                return 1;
    
            // 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++;
            }
    
            return runHi - lo;
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    主要看这里这里就是使用我们传入的比较器的地方了
    c.compare(a[runHi++], a[lo]) ,a[runHi++]这个就是o1, a[lo] 就是o2
    然后看这句int runHi = lo + 1; 既可以得出o1是在o2后的
    再看这个 c.compare(a[runHi++], a[lo]) < 0 这是我们返回-1的时候了
    runHi < hi && c.compare(a[runHi], a[runHi - 1] <0 这是找出到最后比较索引compare结果小于0的连续区间

       private static void reverseRange(Object[] a, int lo, int hi) {
            hi--;
            while (lo < hi) {
                Object t = a[lo];
                a[lo++] = a[hi];
                a[hi--] = t;
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    反转上述找出的区间的元素
    runHi < hi && c.compare(a[runHi], a[runHi - 1]) >= 0 就是不反转了

    看完源码,和我们的结论一致

    这是倒序
    (o1,o2)->
        {
            if (o1 > o2) {
                return -1;
            } else {
                return 1;
            }
        }
    这是正序
    (o1,o2)->
        {
            if (o1 > o2) {
                return 1;
            } else {
                return -1;
            }
        }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
  • 相关阅读:
    【scikit-learn基础】--『监督学习』之 随机森林分类
    武汉轻工大学计算机考研资料汇总
    前端基础建设与架构24 自动化代码检查:剖析 Lint 工具和工程化接入&优化方案
    LeetCode---SQL刷题2
    大三保研夏令营须知及前期准备工作
    电脑桌面日历云便签怎么通过日历查看节假日和农历节气?
    C++:day5
    GB28181安防视频融合汇聚平台EasyCVR如何实现视频画面自定义标签?
    卡方分布和 Zipf 分布模拟及 Seaborn 可视化教程
    mmc子系统分析(二)
  • 原文地址:https://blog.csdn.net/m0_48324758/article/details/126405015