欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2020年02月19日 10:13:39   作者:一年e度的夏天  
這篇文章主要介紹了Java Arrays.sort和Collections.sort排序?qū)崿F(xiàn)原理解析,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

1、使用

排序

2、原理

事實(shí)上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

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

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

我們沒有寫比較器,所以用的第二項(xiàng),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)入這個

接著看我們重要的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) {
          //這個方法比較有意思,其實(shí)就是將我們最長的遞減序列,找出來,然后倒過來
           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方法是一樣的,其實(shí)也就是TimSort的源代碼

3、總結(jié)

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

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

相關(guān)文章

  • resultMap標(biāo)簽中里的collection標(biāo)簽詳解

    resultMap標(biāo)簽中里的collection標(biāo)簽詳解

    這篇文章主要介紹了resultMap標(biāo)簽中里的collection標(biāo)簽,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2022-02-02
  • Mybatis Log控制臺如何輸出打印SQL語句

    Mybatis Log控制臺如何輸出打印SQL語句

    這篇文章主要介紹了Mybatis Log控制臺如何輸出打印SQL語句,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-07-07
  • Spring Security使用多種加密方式進(jìn)行密碼校驗(yàn)的代碼示例

    Spring Security使用多種加密方式進(jìn)行密碼校驗(yàn)的代碼示例

    在Web應(yīng)用中,密碼的安全存儲和驗(yàn)證是至關(guān)重要的,本文將通過一個具體的代碼示例,介紹和總結(jié)如何在Spring Security中使用多種加密方式進(jìn)行密碼校驗(yàn),文中通過代碼講解得非常詳細(xì),需要的朋友可以參考下
    2024-06-06
  • java實(shí)現(xiàn)學(xué)生成績信息管理系統(tǒng)

    java實(shí)現(xiàn)學(xué)生成績信息管理系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)學(xué)生成績信息管理系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-07-07
  • java 工廠模式的講解及優(yōu)缺點(diǎn)的介紹

    java 工廠模式的講解及優(yōu)缺點(diǎn)的介紹

    這篇文章主要介紹了java 工廠模式的講解及優(yōu)缺點(diǎn)的介紹的相關(guān)資料, 簡單工廠模式,又稱為靜態(tài)工廠方法(Static Factory Method)模式,它屬于類創(chuàng)建型模式,需要的朋友可以參考下
    2017-08-08
  • SpringBoot集成SFTP客戶端實(shí)現(xiàn)文件上傳下載實(shí)例

    SpringBoot集成SFTP客戶端實(shí)現(xiàn)文件上傳下載實(shí)例

    這篇文章主要為大家介紹了SpringBoot集成SFTP客戶端實(shí)現(xiàn)文件上傳下載實(shí)例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-08-08
  • SpringCloud zookeeper作為注冊中心使用介紹

    SpringCloud zookeeper作為注冊中心使用介紹

    ZooKeeper由雅虎研究院開發(fā),是Google Chubby的開源實(shí)現(xiàn),后來托管到Apache,于2010年11月正式成為Apache的頂級項(xiàng)目。ZooKeeper是一個經(jīng)典的分布式數(shù)據(jù)一致性解決方案,致力于為分布式應(yīng)用提供一個高性能、高可用,且具有嚴(yán)格順序訪問控制能力的分布式協(xié)調(diào)服務(wù)
    2022-11-11
  • SpringBoot使用Nacos動態(tài)配置數(shù)據(jù)源的方法

    SpringBoot使用Nacos動態(tài)配置數(shù)據(jù)源的方法

    這篇文章主要介紹了SpringBoot使用Nacos動態(tài)配置數(shù)據(jù)源的方法,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2021-03-03
  • IDEA報錯"Cannot?resolve?symbol"問題的解決辦法

    IDEA報錯"Cannot?resolve?symbol"問題的解決辦法

    早上來了,打開idea發(fā)現(xiàn)注解等都變紅報錯can’t resolvesymbol,由于這個錯之前也報過,所以記錄一下,這篇文章主要給大家介紹了關(guān)于IDEA報錯"Cannot?resolve?symbol"問題的解決辦法,需要的朋友可以參考下
    2023-11-11
  • SpringBoot2實(shí)現(xiàn)MessageQueue消息隊(duì)列

    SpringBoot2實(shí)現(xiàn)MessageQueue消息隊(duì)列

    本文主要介紹了 SpringBoot2實(shí)現(xiàn)MessageQueue消息隊(duì)列,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-04-04

最新評論