Java QuickSort 원리 및 구현 코드

빠른 정렬(QuickSort)은 효율이 높은 정렬 알고리즘으로 면접 과정에서도 자주 언급된다.다음은 그의 원리를 상세하게 설명하고 자바 버전의 실현을 제시한다.
빠른 정렬 생각:
데이터 요소 컬렉션 Rn을 정렬하여 독립적인 두 섹션을 구분합니다.그 중 한 부분의 키워드는 다른 부분의 키워드보다 작다.그리고 독립된 요소가 하나일 때까지 두 부분의 키워드를 정렬합니다. 이때 전체 요소가 질서정연하게 집합됩니다.
빠른 정렬 과정 - 구덩이 채우기법(이것은 매우 형상적인 명칭), 하나의 원소를 집합하는 R[low...high], 우선 하나의 수(일반적으로 R[low])를 참조하여 R[low]를 기준으로 모든 원소를 다시 배열한다.
R[low]보다 작은 것은 앞에 놓고, R[low]보다 큰 것은 뒤에 놓고, R[low]를 경계로 하고, R[low...high]를 두 개의 서브집합과 구분한다.low>=high까지.
예를 들어 R={37, 40, 38, 42, 461, 5, 7, 9, 12}에 대해 빠른 정렬을 하는 과정은 다음과 같다(주: 아래에 기술된 내용 중 요소 아래 표는 0에서 시작).
원본 시퀀스
37
사십
38
42
461



십이
1:high-->low
십이
사십
38
42
461



십이
1: low --> high
십이
사십
38
42
461



사십
2:high-->low
십이

38
42
461



사십
2: low --> high
십이

38
42
461


38
사십
3:high-->low
십이


42
461


38
사십
3:low-->high
십이


42
461

42
38
사십
4: high --> low
십이



461

42
38
사십
4: low --> high
십이



461
461
42
38
사십
정렬 결과
십이



37
461
42
38
사십
데이텀 base = 37, 초기 위치 아래 표 low = 0, high = 8, high = 8부터 R[8] low부터 탐지합니다. low=1, R[low] > base 때문에 R[low]를 R[high], high=high-1에 기록합니다.
low 이때 low=1, high=7, R[high]low부터 탐지, low=2, R[low]>base, 그래서 R[low]를 R[high], high=high-1에 쓴다.
low가 high보다 작음을 계속 검출합니다
이때 low=2, high=6, 동리 R[high]low에서 계속 탐지, low=3, high=6, R[low] > base, R[low]를 R[high]에 쓰기, high=high-1;
low가 높음보다 작음을 계속 탐지합니다
이때 low=3, high=5, 동리 R[high]low에서 계속 탐지, low=4, high=5, R[low]>base로 인해 R[low]를 R[high]에 쓰기, high=high-1;
이때 low===high==4를 탐지합니다.이 위치는 베이스가 있는 위치입니다. 베이스를 이 위치에 기록합니다.
그리고 다시 하위 서열 Rs1 = {12,9,7,5}와 Rs2={461,42,38,40}에 대해 Rsi에 원소가 하나밖에 없거나 없을 때까지 빠른 정렬을 합니다.
(주: 상기 표에서 정렬에 중복된 데이터(원본 데이터에 중복된 데이터가 없음)를 볼 수 있습니다. 이것은 이 위치의 데이터를 제거하지 않았기 때문입니다. 우리는 특정한 시간에 이 메모리 블록의 데이터는 여전히 그것입니다. 다음에 데이터를 이 위치에 쓸 때까지입니다. 이 위치의 데이터는 무의미한 더러운 데이터입니다. 이를'구덩이'라고 합니다.)
빠른 정렬을 위한 Java 구현:

private static boolean isEmpty(int[] n) {
        return n == null || n.length == 0;
    }

    // ///////////////////////////////////////////////////
    /**
     * ―― :
     *
     * @param n
     */
    public static void quickSort(int[] n) {
        if (isEmpty(n))
            return;
        quickSort(n, 0, n.length - 1);
    }

    public static void quickSort(int[] n, int l, int h) {
        if (isEmpty(n))
            return;
        if (l < h) {
            int pivot = partion(n, l, h);
            quickSort(n, l, pivot - 1);
            quickSort(n, pivot + 1, h);
        }
    }

    private static int partion(int[] n, int start, int end) {
        int tmp = n[start];
        while (start < end) {
            while (n[end] >= tmp && start < end)
                end--;
            if (start < end) {
                n[start++] = n[end];
            }
            while (n[start] < tmp && start < end)
                start++;
            if (start < end) {
                n[end--] = n[start];
            }
        }
        n[start] = tmp;
        return start;
    }

코드에는 다음과 같은 함수가 있습니다

 public static void quickSortSwap(int[] n, int l, int h)
이 함수는 원소 집합 중의 특정한 l에서 h 위치 간의 데이터 원소를 정렬할 수 있다.빠른 정렬에 관해서는 여기까지 쓰겠습니다.

좋은 웹페이지 즐겨찾기