Java List中的sort方法怎么用

這篇文章主要講解了“Java List中的sort方法怎么用”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“Java List中的sort方法怎么用”吧！

先來看看List中的sort是怎么寫的：

    @SuppressWarnings({"unchecked", "rawtypes"})
    default void sort(Comparator<!--? super E--> c) {
        Object[] a = this.toArray();
        Arrays.sort(a, (Comparator) c);
        ListIterator<e> i = this.listIterator();
        for (Object e : a) {
            i.next();
            i.set((E) e);
        }
    }

首先，你需要傳入一個比較器作為參數，這個好理解，畢竟你肯定要定一個比較標準。然后就是將list轉換成一個數組，再對這個數組進行排序，排序完之后，再利用iterator重新改變list。

接著，我們再來看看Arrays.sort：

    public static <t> void sort(T[] a, Comparator<!--? super T--> c) {
        if (c == null) {
            sort(a);
        } else {
            if (LegacyMergeSort.userRequested)
                legacyMergeSort(a, c);
            else
                TimSort.sort(a, 0, a.length, c, null, 0, 0);
        }
    }

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

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

這樣可以看出，其實排序的核心就是TimSort，LegacyMergeSort大致意思是表明如果版本很舊的話，就用這個，新版本是不會采用這種排序方式的。

我們再來看看TimSort的實現：

    private static final int MIN_MERGE = 32;
    static <t> void sort(T[] a, int lo, int hi, Comparator<!--? super T--> c,
                         T[] work, int workBase, int workLen) {
        assert c != null &amp;&amp; a != null &amp;&amp; lo &gt;= 0 &amp;&amp; lo &lt;= hi &amp;&amp; hi &lt;= a.length;

        int nRemaining  = hi - lo;
        if (nRemaining &lt; 2)
            return;  // Arrays of size 0 and 1 are always sorted

        // If array is small, do a "mini-TimSort" with no merges
        if (nRemaining &lt; 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&lt;&gt;(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 &lt; minRun) {
                int force = nRemaining &lt;= 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;
    }

如果小于2個，代表不再不需要排序；如果小于32個，則采用優化的二分排序。怎么優化的呢？首先獲得最長的遞增序列：

    private static <t> int countRunAndMakeAscending(T[] a, int lo, int hi,
                                                    Comparator<!--? super T--> c) {
        assert lo &lt; 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]) &lt; 0) { // Descending
            // 一開始是遞減序列，就找出最長遞減序列的最后一個下標
            while (runHi &lt; hi &amp;&amp; c.compare(a[runHi], a[runHi - 1]) &lt; 0)
                runHi++;
            // 逆轉前面的遞減序列
            reverseRange(a, lo, runHi);
        } else {                              // Ascending
            while (runHi &lt; hi &amp;&amp; c.compare(a[runHi], a[runHi - 1]) &gt;= 0)
                runHi++;
        }

        return runHi - lo;
    }

接著進行二分排序：

    private static <t> void binarySort(T[] a, int lo, int hi, int start,
                                       Comparator<!--? super T--> c) {
        assert lo &lt;= start &amp;&amp; start &lt;= hi;
        if (start == lo)
            start++;
        for ( ; start &lt; 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 &lt;= right;
            /*
             * Invariants:
             *   pivot &gt;= all in [lo, left).
             *   pivot &lt;  all in [right, start).
             */
            // start位置是遞增序列后的第一個數的位置
            // 從前面的遞增序列中找出start位置的數應該處于的位置
            while (left &lt; right) {
                // &gt;&gt;&gt; 無符號右移
                int mid = (left + right) &gt;&gt;&gt; 1;
                if (c.compare(pivot, a[mid]) &lt; 0)
                    right = mid;
                else
                    left = mid + 1;
            }
            assert left == right;

            /*
             * The invariants still hold: pivot &gt;= all in [lo, left) and
             * pivot &lt; 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
            // 比pivot大的數往后移動一位
            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;
        }
    }

好了，待排序數量小于32個的講完了，現在來說說大于等于32個情況。首先，獲得一個叫minRun的東西，這是個啥含義呢：

    int minRun = minRunLength(nRemaining);
    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) {
            // 這里我沒搞懂的是為什么不直接將(n & 1)賦值給r，而要做一次邏輯或。
            r |= (n & 1);
            n >>= 1;
        }
        return n + r;
    }

各種位運算符，MIN_MERGE默認為32，如果n小于此值，那么返回n本身。否則會將n不斷地右移，直到小于MIN_MERGE，同時記錄一個r值，r代表最后一次移位n時，n最低位是0還是1。 其實看注釋比較容易理解：

Returns the minimum acceptable run length for an array of the specified length. Natural runs shorter than this will be extended with binarySort.
Roughly speaking, the computation is: If n < MIN_MERGE, return n (it's too small to bother with fancy stuff).
Else if n is an exact power of 2, return MIN_MERGE/2.
Else return an int k, MIN_MERGE/2 <= k <= MIN_MERGE, such that n/k is close to, but strictly less than, an exact power of 2. For the rationale, see listsort.txt.

返回結果其實就是用于接下來的合并排序中。

接下來就是一個while循環

        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
            // lo——runLen為將要被歸并的范圍
            ts.pushRun(lo, runLen);
            // 歸并
            ts.mergeCollapse();

            // Advance to find next run
            lo += runLen;
            nRemaining -= runLen;
        } while (nRemaining != 0);

這樣，假設你的每次歸并排序的兩個序列為r1和r2，r1肯定是有序的，r2也已經被排成遞增序列了，因此這樣的歸并排序就比較特殊了。

為什么要用歸并排序呢，因為歸并排序的時間復雜度永遠為O(nlogn)，空間復雜度為O(n)，以空間換取時間。

感謝各位的閱讀，以上就是“Java List中的sort方法怎么用”的內容了，經過本文的學習后，相信大家對Java List中的sort方法怎么用這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！