溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析

發(fā)布時間：2020-09-27 19:03:37 來源：腳本之家 閱讀：192 作者：一年e度的夏天 欄目：編程語言

1、使用

排序

2、原理

事實上Collections.sort方法底層就是調(diào)用的array.sort方法，而且不論是Collections.sort或者是Arrays.sort方法，

跟蹤下源代碼吧，首先我們寫個demo

public static void main(String[] args) {
         List<String> strings = Arrays.asList("6", "1", "3", "1","2");

         Collections.sort(strings);//sort方法在這里

         for (String string : strings) {

           System.out.println(string);
         }
       }

簡單得不能再簡單的方法了，讓我們一步步跟蹤

OK，往下面看，發(fā)現(xiàn)collections.sort方法調(diào)用的list.sort

Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析

然后跟蹤一下，list里面有個sort方法，但是list是一個接口，肯定是調(diào)用子類里面的實現(xiàn)，這里我們demo使用的是一個Arrays.asList方法，所以事實上我們的子類就是arraylist了。OK，看arraylist里面sort實現(xiàn)，選擇第一個，為什么不選擇第二個呢？（可以看二樓評論，解答得很正確，簡單說就是用Arrays.sort創(chuàng)建的ArrayList對象）

Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析​

OK，發(fā)現(xiàn)里面調(diào)用的Arrays.sort(a, c); a是list,c是一個比較器，我們來看一下這個方法

Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析

我們沒有寫比較器，所以用的第二項，LegacyMergeSort.userRequested這個bool值是什么呢？
跟蹤這個值，我們發(fā)現(xiàn)有這樣的一段定義：

> Old merge sort implementation can be selected (for
> compatibility with broken comparators) using a system property.
> Cannot be a static boolean in the enclosing class due to
> circular dependencies. To be removed in a future release.

反正是一種老的歸并排序，不用管了現(xiàn)在默認(rèn)是關(guān)的

OK，我們走的是sort(a)這個方法，接著進(jìn)入這個

Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析

接著看我們重要的sort方法

static void sort(Object[] a, int lo, int hi, Object[] work, int workBase, int workLen) {
         assert a != null && lo >= 0 && lo <= hi && hi <= a.length;

         int nRemaining = hi - lo;
         if (nRemaining < 2)
           return; // array的大小為0或者1就不用排了

         // 當(dāng)數(shù)組大小小于MIN_MERGE(32)的時候，就用一個"mini-TimSort"的方法排序，jdk1.7新加
         if (nRemaining < MIN_MERGE) {
          //這個方法比較有意思，其實就是將我們最長的遞減序列，找出來，然后倒過來
           int initRunLen = countRunAndMakeAscending(a, lo, hi);
           //長度小于32的時候，是使用binarySort的
           binarySort(a, lo, hi, lo + initRunLen);
           return;
         }
        //先掃描一次array，找到已經(jīng)排好的序列，然后再用剛才的mini-TimSort，然后合并，這就是TimSort的核心思想
         ComparableTimSort ts = new ComparableTimSort(a, work, workBase, workLen);
         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) {
             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);
           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;
     }

回到5，我們可以看到當(dāng)我們寫了比較器的時候就調(diào)用了TimSort.sort方法，源碼如下

static <T> void sort(T[] a, int lo, int hi, Comparator<? super T> c,
                 T[] work, int workBase, int workLen) {
         assert c != null && a != null && lo >= 0 && lo <= hi && hi <= a.length;

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

和上面的sort方法是一樣的，其實也就是TimSort的源代碼

3、總結(jié)

不論是Collections.sort方法或者是Arrays.sort方法，底層實現(xiàn)都是TimSort實現(xiàn)的，這是jdk1.7新增的，以前是歸并排序。TimSort算法就是找到已經(jīng)排好序數(shù)據(jù)的子序列，然后對剩余部分排序，然后合并起來

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手