자바 Arrays.sort 와 Collections.sort 정렬 실현 원리 분석

1.사용
정렬
2.원리
사실 Collections.sort 방법의 밑바닥 은 호출 된 array.sort 방법 이 며,Collections.sort 또는 Arrays.sort 방법 이 든,
소스 코드 를 추적 해 보 세 요.우선 데모 를 쓰 겠 습 니 다.

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,아래 를 보 니 collections.sort 방법 으로 호출 된 list.sort 가 발견 되 었 습 니 다.

그리고 추적 해 보 세 요.list 안에 sort 방법 이 있 습 니 다.그러나 list 는 인터페이스 입 니 다.분명히 하위 클래스 의 실현 을 호출 하 는 것 입 니 다.여기 서 우리 demo 는 Arrays.asList 방법 을 사용 하기 때문에 사실은 우리 의 하위 클래스 는 arraylist 입 니 다.OK,array list 에서 sort 가 실현 되 는 것 을 보고 첫 번 째 를 선택 하 세 요.왜 두 번 째 를 선택 하지 않 습 니까?2 층 댓 글 을 볼 수 있 습 니 다.정확하게 답 했 습 니 다.쉽게 말 하면 Arrays.sort 로 만 든 ArrayList 대상 입 니 다)
​
OK,안에 호출 된 Arrays.sort(a,c)발견;a 는 list 이 고 c 는 비교 기 입 니 다.이 방법 을 살 펴 보 겠 습 니 다.

우 리 는 비교 기 를 쓰 지 않 았 기 때문에 두 번 째 항목 을 사용 합 니 다.Legacy Merge Sort.userrequired 이 bool 값 은 무엇 입 니까?
이 값 을 추적 하면 다음 과 같은 정의 가 있 습 니 다.
> 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.
어차피 오래된 병합 정렬 이 니 상관 하지 마 세 요.지금 은 기본적으로 꺼 져 있 습 니 다.
OK,우리 가 가 는 것 은 sort(a)라 는 방법 입 니 다.이어서 이것 에 들 어 갑 니 다.

이어서 저희 의 중요 한 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     

         //        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，         ，       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 로 돌아 가면 우 리 는 우리 가 비교 기 를 썼 을 때 사용 한 것 을 볼 수 있다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 방법 과 같 습 니 다.사실은 Timsert 의 소스 코드 입 니 다.
3.총화
Collections.sort 방법 이 든 Arrays.sort 방법 이 든 바 텀 실현 은 모두 Timsert 에서 이 루어 진 것 입 니 다.이것 은 jdk 1.7 에 추 가 된 것 이 고 예전 에는 병합 순 서 였 습 니 다.Timsert 알고리즘 은 정렬 된 데이터 의 하위 서열 을 찾 은 다음 나머지 부분 을 정렬 한 다음 합 친 것 입 니 다.
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.