자바 에서 Arrays.sort()의 용법 을 깊이 이해 합 니 다.

7939 단어 자바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<ints.length;i++)
    {
      System.out.print(ints[i]+" ");
    }

    System.out.println("
"); // , , Integer[] integers=new Integer[]{2,324,4,4,6,1}; Arrays.sort(integers, new Comparator<Integer>() { /* * 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<ints2.length;i++) { System.out.print(ints2[i]+" "); } } }
정렬 결 과 는 다음 과 같다.
증차 순 정렬 후 순서
1 2 4 57 324
줄 임 순서 정렬 후 순서
324 6 4 4 2 1
부분 정렬 후 순서
212 43 2 4 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 를 축 으로 선택 합 니 다.예 를 들 어 우 리 는 첫 번 째 요소 와 마지막 요 소 를 사용 할 수 있 습 니 다.
3.P1 은 P2 보다 작 아야 합 니 다.그렇지 않 으 면 이 두 요 소 를 교환 하고 현재 전체 배열 을 네 부분 으로 나 누 어야 합 니 다.
(1)제1 부분:P1 보다 작은 원소.
(2)두 번 째 부분:P1 보다 크 지만 P2 보다 작은 요소.
(3)세 번 째 부분:P2 보다 큰 요소.
(4)네 번 째 부분:비교 되 지 않 은 부분.
비 교 를 시작 하기 전에 축 점 을 제외 하고 나머지 요 소 는 거의 네 번 째 부분 에 있 고 비교 가 끝 난 후에 네 번 째 부분 에는 요소 가 없다.
4.네 번 째 부분 에서 하나의 요소 a[K]를 선택 하여 두 축 과 비교 한 다음 에 하나,둘,셋 째 부분 중 하 나 를 넣는다.
5.L,K,G 방향 이동.
6.네 번 째 부분 에 요소 가 없 을 때 까지 45 단 계 를 반복 합 니 다.
7.P1 과 첫 번 째 부분의 마지막 요 소 를 교환 합 니 다.P2 와 세 번 째 부분의 첫 번 째 원 소 를 교환 합 니 다.
8.재 귀적 으로 제1,2,3 부분 을 정렬 합 니 다.
질문:왜 범 형 을 쓰 지 않 습 니까?
자바 에 있 는 Arrays.sort()의 용법 을 깊이 이해 하 는 이 글 은 여기까지 소개 되 었 습 니 다.자바 Arrays.sort()에 관 한 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!

좋은 웹페이지 즐겨찾기