快捷導(dǎo)航

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

更新時(shí)間：2020年02月19日 10:13:39 作者：一年e度的夏天

這篇文章主要介紹了Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

1、使用

排序

2、原理

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

跟蹤下源代碼吧，首先我們寫(xiě)個(gè)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);
         }
       }

簡(jiǎn)單得不能再簡(jiǎn)單的方法了，讓我們一步步跟蹤

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

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

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

我們沒(méi)有寫(xiě)比較器，所以用的第二項(xiàng)，LegacyMergeSort.userRequested這個(gè)bool值是什么呢？
跟蹤這個(gè)值，我們發(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)這個(gè)方法，接著進(jìn)入這個(gè)

接著看我們重要的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)的時(shí)候，就用一個(gè)"mini-TimSort"的方法排序，jdk1.7新加
         if (nRemaining < MIN_MERGE) {
          //這個(gè)方法比較有意思，其實(shí)就是將我們最長(zhǎng)的遞減序列，找出來(lái)，然后倒過(guò)來(lái)
           int initRunLen = countRunAndMakeAscending(a, lo, hi);
           //長(zhǎng)度小于32的時(shí)候，是使用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)我們寫(xiě)了比較器的時(shí)候就調(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方法是一樣的，其實(shí)也就是TimSort的源代碼

3、總結(jié)

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

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: