专栏首页刘晓杰源码阅读--Collections.sort

源码阅读--Collections.sort

Collections.sort源代码

    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        Object[] a = list.toArray();
        Arrays.sort(a);//
        ListIterator<T> i = list.listIterator();
        for (int j=0; j<a.length; j++) {
            i.next();
            i.set((T)a[j]);
        }
    }

跟踪Arrays.sort

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a);
    }

LegacyMergeSort.userRequested指的啥呢?

    static final class LegacyMergeSort {
        private static final boolean userRequested =
            java.security.AccessController.doPrivileged(
                new sun.security.action.GetBooleanAction(
                    "java.util.Arrays.useLegacyMergeSort")).booleanValue();
    }

这是一个boolean值。说白了就是,如果用户指定归并排序那就归并排序,否则就是ComparableTimSort。归并排序比较常见,就不讲了。贴一下ComparableTimSort

    static void sort(Object[] a, int lo, int hi) {
        rangeCheck(a.length, lo, hi);
        int nRemaining  = hi - lo;
        if (nRemaining < 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining < MIN_MERGE) {//***********************************如果长度小于MIN_MERGE(32),那就用二分排序算法
            int initRunLen = countRunAndMakeAscending(a, lo, hi);
            binarySort(a, lo, hi, lo + initRunLen);
            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.
         */
        ComparableTimSort ts = new ComparableTimSort(a);
        int minRun = minRunLength(nRemaining);
        do {
            // Identify next run
            int runLen = countRunAndMakeAscending(a, lo, hi);

            // If run is short, extend to min(minRun, nRemaining)
            if (runLen < minRun) {  
                //如果拐点小于minRun,就对整个minRun二分排序
                int force = nRemaining <= minRun ? nRemaining : minRun;
                binarySort(a, lo, lo + force, lo + runLen);
                runLen = force;
            }

            // Push run onto pending-run stack, and maybe merge
            ts.pushRun(lo, runLen);//**********************这里的runLen>=minRun
            ts.mergeCollapse();//*************调用mergeAt

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);
        // Merge all remaining runs to complete sort
        assert lo == hi;
        ts.mergeForceCollapse();//*************也会调用mergeAt
        assert ts.stackSize == 1;
    }

    //minRunLength------一直取二分之一,直到小于MIN_MERGE(32)
    // n=奇数,return (n-1)/2+1。n=偶数,return n/2
    private static int minRunLength(int n) {
        assert n >= 0;
        int r = 0;      // Becomes 1 if any 1 bits are shifted off
        while (n >= MIN_MERGE) {
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

    //countRunAndMakeAscending
    // 全是升序,那就返回high
    // 全是降序,那就返回high,并且要翻转
    // 先升后降,返回最高点
    // 先降后升,返回最低点,并且之前的翻转
    // 说白了就是返回拐点
    private static int countRunAndMakeAscending(Object[] a, int lo, int hi) {
        assert lo < hi;
        int runHi = lo + 1;
        if (runHi == hi)
            return 1;

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

        return runHi - lo;
    }

    // ********************理解gallopRight和gallopLeft
    private void mergeAt(int i) {
        int base1 = runBase[i];
        int len1 = runLen[i];
        int base2 = runBase[i + 1];
        int len2 = runLen[i + 1];

        /*
         * Record the length of the combined runs; if i is the 3rd-last
         * run now, also slide over the last run (which isn't involved
         * in this merge).  The current run (i+1) goes away in any case.
         */
        runLen[i] = len1 + len2;
        if (i == stackSize - 3) {
            runBase[i + 1] = runBase[i + 2];
            runLen[i + 1] = runLen[i + 2];
        }
        stackSize--;

        /*
         * Find where the first element of run2 goes in run1. Prior elements
         * in run1 can be ignored (because they're already in place).
         */
        int k = gallopRight((Comparable<Object>) a[base2], a, base1, len1, 0);
        assert k >= 0;
        base1 += k;
        len1 -= k;
        if (len1 == 0)
            return;

        /*
         * Find where the last element of run1 goes in run2. Subsequent elements
         * in run2 can be ignored (because they're already in place).
         */
        len2 = gallopLeft((Comparable<Object>) a[base1 + len1 - 1], a,
                base2, len2, len2 - 1);
        assert len2 >= 0;
        if (len2 == 0)
            return;

        // Merge remaining runs, using tmp array with min(len1, len2) elements
        if (len1 <= len2)
            mergeLo(base1, len1, base2, len2);
        else
            mergeHi(base1, len1, base2, len2);
    }

算法思想如下: 1.构造minRun,值等于长度的一直除以2,直到小于MIN_MERGE 2.(这一步会无限循环) (1)寻找第一个拐点,记为index。如果index小于minRun,那就对整个minRun数据二分排序。 (2)将起始位置和拐点位置push进去,然后对当前的各区块进行merge。 由于要合并的两个 run 是已经排序的,所以合并的时候,有会特别的技巧。 假设两个 run 是 run1,run2 ,先用 gallopRight在 run1里使用 binarySearch 查找run2 首元素 的位置k, 那么 run1 中 k 前面的元素就是合并后最小的那些元素。然后,在run2 中查找run1 尾元素 的位置 len2 ,那么run2 中 len2 后面的那些元素就是合并后最大的那些元素。最后,根据len1 与len2 大小,调用mergeLo或者 mergeHi 将剩余元素合并。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • View的事件体系

    2.MotionEvent 手指触摸屏幕后的一系列事件,包括ACTION_DOWN,ACTION_MOVE,ACTION_UP

    提莫队长
  • 嵌套滑动机制详解

    提莫队长
  • ImageLoader

    这次做一个图片加载器,里面涉及到线程池,bitmap的高效加载,LruCache,DiskLruCache。接下来我先介绍这四个知识点

    提莫队长
  • 洛谷P1439 最长公共子序列(LCS问题)

    题目描述 给出1-n的两个排列P1和P2,求它们的最长公共子序列。 输入输出格式 输入格式: 第一行是一个数n, 接下来两行,每行为n个数,为自然数1-n的一个...

    attack
  • 解决Scrollview 嵌套recyclerview不能显示,高度不正常的问题

    我们先看一个效果,问题说的就是中间的Grid效果在Scrollview 嵌套recyclerview显示问题,在Android Api 24是好的,不过在5,1...

    xiangzhihong
  • 【剑指offer】31.整数中1出现的次数

    求出1 ~ 13的整数中1出现的次数,并算出100 ~ 1300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共...

    AI那点小事
  • HDU 1525 Euclid's Game

    ShenduCC
  • 云时代数据容灾的正确姿势

    2、确保应用高可用性,消除计划外的停机时间,减少计划外的停机时间,提高业务连续性。

    嘉为科技
  • 1043 方格取数 2000年NOIP全国联赛提高组

    1043 方格取数 2000年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

    attack
  • Spring Boot REST国际化

    正如你看到:响应会根据请求中传递的“ Accept-Language ”标头的值而有所不同。这样,我们不需要检查每个控制器方法中请求中传递的内容,然后将其进一步...

    lyb-geek

扫码关注云+社区

领取腾讯云代金券