Arrays. sort () 깊이 이해

자바 의 Arrays. sort () 방법 을 깊이 이해 합 니 다.
자바 의 Arrays 클래스 에는 sort () 방법 이 있 습 니 다. 이 방법 은 Arrays 류 의 정적 방법 으로 배열 을 정렬 해 야 할 때 매우 좋 습 니 다.
그러나 sort () 의 매개 변 수 는 여러 가지 가 있 는데 대체적으로 대동소이 하 다. 다음은 int 형 배열 을 예 로 들 어 Arrays. sort () 의 전형 적 인 용법 이다.

import java.util.Arrays;
import java.util.Comparator;

/**
 * Arrays.sort()  
 */
public class SortTest
{
    public static void main(String []args)
    {
        int[] ints=new int[]{2,324,4,57,1};

        System.out.println("       ");
        Arrays.sort(ints);
        for (int i=0;i" ");
        }


        System.out.println("
       ");
        //       ，         ，          
        Integer[] integers=new Integer[]{2,324,4,4,6,1};
        Arrays.sort(integers, new Comparator()
        {
            /*
            *    c++          
            * c++  bool , Java    int 
            *     >0 
            *     ，   (            )
             */
            public int compare(Integer o1, Integer o2)
            {
                return o2-o1;
            }


            public boolean equals(Object obj)
            {
                return false;
            }
        });
        for (Integer integer:integers)
        {
            System.out.print(integer+" ");
        }



        System.out.println("
        ");
        int[] ints2=new int[]{212,43,2,324,4,4,57,1};
        //    [2,6)     

        Arrays.sort(ints2,2,6);
        for (int i=0;i" ");
        }

    }
}

정렬 결 과 는 다음 과 같다.
증 서 정렬 후 순서 1 2 4 57 324 감 서 정렬 후 순서 324 6 4 2 1 대 부분 정렬 후 순서 212 43 2 4 324 57 1
Arrays. sort () 소스 코드 를 엽 니까? int 형 을 예 로 들 면 다른 유형 도 대동소이 합 니 다.

  public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

  public static void sort(int[] a, int fromIndex, int toIndex) {
        rangeCheck(a.length, fromIndex, toIndex);
        DualPivotQuicksort.sort(a, fromIndex, toIndex - 1, null, 0, 0);
    }

소스 코드 에서 두 가지 매개 변수 유형의 sort 방법 은 모두 DualPivotQuicksort. sort () 방법 으로 소스 코드 를 계속 추적 하 는 것 을 발견 했다.

static void sort(int[] a, int left, int right,
                     int[] work, int workBase, int workLen) {
        // Use Quicksort on small arrays
        if (right - left < QUICKSORT_THRESHOLD) {
            sort(a, left, right, true);
            return;
        }

        /*
         * Index run[i] is the start of i-th run
         * (ascending or descending sequence).
         */
        int[] run = new int[MAX_RUN_COUNT + 1];
        int count = 0; run[0] = left;

        // Check if the array is nearly sorted
        for (int k = left; k < right; run[count] = k) {
            if (a[k] < a[k + 1]) { // ascending
                while (++k <= right && a[k - 1] <= a[k]);
            } else if (a[k] > a[k + 1]) { // descending
                while (++k <= right && a[k - 1] >= a[k]);
                for (int lo = run[count] - 1, hi = k; ++lo < --hi; ) {
                    int t = a[lo]; a[lo] = a[hi]; a[hi] = t;
                }
            } else { // equal
                for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
                    if (--m == 0) {
                        sort(a, left, right, true);
                        return;
                    }
                }
            }

            /*
             * The array is not highly structured,
             * use Quicksort instead of merge sort.
             */
            if (++count == MAX_RUN_COUNT) {
                sort(a, left, right, true);
                return;
            }
        }

        // Check special cases
        // Implementation note: variable "right" is increased by 1.
        if (run[count] == right++) { // The last run contains one element
            run[++count] = right;
        } else if (count == 1) { // The array is already sorted
            return;
        }

        // Determine alternation base for merge
        byte odd = 0;
        for (int n = 1; (n <<= 1) < count; odd ^= 1);

        // Use or create temporary array b for merging
        int[] b;                 // temp array; alternates with a
        int ao, bo;              // array offsets from 'left'
        int blen = right - left; // space needed for b
        if (work == null || workLen < blen || workBase + blen > work.length) {
            work = new int[blen];
            workBase = 0;
        }
        if (odd == 0) {
            System.arraycopy(a, left, work, workBase, blen);
            b = a;
            bo = 0;
            a = work;
            ao = workBase - left;
        } else {
            b = work;
            ao = 0;
            bo = workBase - left;
        }

        // Merging
        for (int last; count > 1; count = last) {
            for (int k = (last = 0) + 2; k <= count; k += 2) {
                int hi = run[k], mi = run[k - 1];
                for (int i = run[k - 2], p = i, q = mi; i < hi; ++i) {
                    if (q >= hi || p < mi && a[p + ao] <= a[q + ao]) {
                        b[i + bo] = a[p++ + ao];
                    } else {
                        b[i + bo] = a[q++ + ao];
                    }
                }
                run[++last] = hi;
            }
            if ((count & 1) != 0) {
                for (int i = right, lo = run[count - 1]; --i >= lo;
                    b[i + bo] = a[i + ao]
                );
                run[++last] = right;
            }
            int[] t = a; a = b; b = t;
            int o = ao; ao = bo; bo = o;
        }
    }

문서 와 소스 코드 를 결합 하면 jdk 의 Arrays. sort () 의 실현 은 이른바 두 축 빠 른 배열 알고리즘 을 통 해 이 루어 진 것 을 알 수 있 습 니 다.

/**
 * This class implements the Dual-Pivot Quicksort algorithm by
 * Vladimir Yaroslavskiy, Jon Bentley, and Josh Bloch. The algorithm
 * offers O(n log(n)) performance on many data sets that cause other
 * quicksorts to degrade to quadratic performance, and is typically
 * faster than traditional (one-pivot) Quicksort implementations.
 *
 * All exposed methods are package-private, designed to be invoked
 * from public methods (in class Arrays) after performing any
 * necessary array bounds checks and expanding parameters into the
 * required forms.
 *
 * @author Vladimir Yaroslavskiy
 * @author Jon Bentley
 * @author Josh Bloch
 *
 * @version 2011.02.11 m765.827.12i:5\7pm
 * @since 1.7
 */

자바 1.8 의 빠 른 배열 은 두 축 빠 른 배열 이다. 말 그대로 두 축 빠 른 배열 은 두 축 을 바탕 으로 비교 하 는 것 이다. 일반적인 한 점 을 선택 하여 축 점 의 빠 른 배열 로 하 는 것 과 큰 차이 가 있다. 두 축 정렬 은 구간 이 인접 한 특성 을 이용 하여 원래 의 빠 른 배열 을 효율 적 으로 향상 시 켰 고 어느 정도 수학의 일부 특성 을 이용 했다.아무튼 되 게 높 고 깊 은 모습 이에 요.
알고리즘 절차
1. 아주 작은 배열 (길이 가 27 보다 작 음) 에 대해 서 는 정렬 을 삽입 합 니 다. 2. 두 개의 점 P1, P2 를 축 으로 선택 합 니 다. 예 를 들 어 우 리 는 첫 번 째 요소 와 마지막 요 소 를 사용 할 수 있 습 니 다. 3P1 은 P2 보다 작 아야 합 니 다. 그렇지 않 으 면 이 두 요 소 를 교환 해 야 합 니 다. 지금 은 전체 배열 을 네 부분 으로 나 눕 니 다. (1) 첫 번 째 부분: P1 보다 작은 요소 입 니 다. (2)두 번 째 부분: P1 보다 크 지만 P2 보다 작은 요소 입 니 다. (3) 세 번 째 부분: P2 보다 큰 요소 입 니 다. (4) 네 번 째 부분: 비교 되 지 않 은 부분 입 니 다. 비 교 를 시작 하기 전에 축 점 을 제외 한 나머지 요 소 는 거의 네 번 째 부분 에 있 습 니 다. 비교 가 끝 난 후에 네 번 째 부분 에는 원소 가 없습니다. 4. 네 번 째 부분 에서 원소 a [K] 를 선택 하 십시오.2 개의 축 과 비교 한 다음 1, 2, 3 부분 중 하나 에 넣 습 니 다. 5. L, K, G 가 가리 키 는 방향 으로 이동 합 니 다. 6. 네 번 째 부분 에 요소 가 없 을 때 까지 45 단 계 를 반복 합 니 다. 7. P1 과 첫 번 째 부분의 마지막 요 소 를 교환 합 니 다. P2 와 세 번 째 부분의 첫 번 째 요 소 를 교환 합 니 다. 8. 재 귀적 으로 1, 2, 3 부분 을 정렬 합 니 다.
질문: 왜 범 형 을 쓰 지 않 습 니까?