빠른 정렬은 1962 년 Crahoare가 제안한 일종의 부서 교환 정렬입니다.이 방법의 기본 아이디어는 다음과 같습니다.
1. 먼저 시퀀스에서 숫자를 참조 번호로 가져옵니다.
2. 분할 과정 에서이 숫자보다 큰 숫자를 오른쪽에, 모든 숫자를 왼쪽보다 작거나 동일하게합니다.
3. 각 간격에 숫자가 하나만있을 때까지 왼쪽 및 오른쪽 간격의 두 번째 단계를 반복하십시오.
알고리즘에는 명확한 아이디어가 있지만 인터벌 디비전 프로세스 중에 경계 값이 잘 처리되지 않으면 버그를 쉽게 유발할 수 있습니다. 다음은 Interval Division Code의 쓰기를 안내하는 두 가지 명확한 생각입니다.
첫 번째 사고 유형은 소위 피트 파기 방법 사고입니다. 다음은 예를 분석하여 구덩이 파기 방법의 과정을 분석하는 것입니다.
배열을 예제로 가져 가면 간격으로 첫 번째 숫자를 참조 번호로 사용하십시오.
처음에는 왼쪽 = 0; 오른쪽 = 9; x = a [왼쪽] = 72
[0]의 숫자는 x로 저장되었으므로 배열 A [0]의 구멍을 파는 것으로 이해 될 수 있으며 다른 데이터를 여기에서 채울 수 있습니다.
오른쪽에서 시작하여 여러 <= x를 찾으십시오. 분명히, 오른쪽 = 8이면 조건이 충족되면 [8]를 파고 이전 구덩이 A [왼쪽]에 채 웁니다. 그러한 구덩이 A [0]가 해결되지만 새로운 구덩이 A [8]가 형성된다. 어떻게해야하나요? 간단하고 구덩이를 채우는 숫자를 찾으십시오 [8]. 이번에는 왼쪽에서 시작하여 X보다 큰 숫자를 찾으십시오. 왼쪽 = 3은 조건을 만나고 [3]를 파고 이전 구덩이에 채우고 [오른쪽];
배열은 다음과 같습니다.
위의 단계를 반복하면 최종 배열이 다음 형식이됩니다.
[5] 이전의 숫자는 그보다 작고 [5] 이후의 숫자는 그것보다 큽니다. X를 [5]의 구덩이에 채우면 데이터가됩니다.
그러므로 두 하위 인터벌 a [0… 4]와 [6… 9]에 대해 위의 단계를 반복하십시오.
발굴 된 구멍의 수 요약
1. i = l; J = R; 참조 번호를 파헤쳐 첫 번째 구덩이를 형성하십시오.
2.
3. I ++는 앞뒤로 그보다 더 큰 숫자를 발견하고 그것을 찾은 후이 숫자를 파고 이전 구덩이 A [j]에 채 웁니다.
4. i == j까지 2 단계와 3 단계를 반복하고 참조 번호를 [i]로 채 웁니다.
이 파티션 방법을 따르십시오. Java 코드는 다음과 같이 빠르게 정렬됩니다.
공개 클래스 파티션 { / ** * 기본 부문을 기반으로 작은 것은 왼쪽에 있고 큰 것은 오른쪽에 있으며 전체 시퀀스는 주문할 필요가 없습니다 * @param ary * @param base * / static void sort (int [] ary, int base) {int left = 0; int right = ary.length -1; int leftpoint = 왼쪽, RightPoint = 오른쪽; while (true) {// 왼쪽에서 오른쪽으로 비교하기 위해 동시에 왼쪽과 오른쪽으로 오른쪽으로 나눕니다. // 왼쪽 포인트는 오른쪽 또는 ary [leftpoint]>베이스 중지 루핑 (오른쪽> = left && ary [RightPoint-]> base); // 반대 System.out.println ( "왼쪽에 바꿔야하는 색인 :" + (왼쪽 지점 -1)); System.out.println ( "오른쪽에 교환 해야하는 색인 :"+ (오른쪽+ 1)); // 조건을 충족하지 않는 두 인덱스가 위에서 얻어 져 있습니다. util.printarray (ary); 왼쪽 점 = 왼쪽; RightPoint = 오른쪽; } else {break; }}} private static void swap (int [] ary, int a, int b) {int temp = ary [a]; ary [a] = ary [b]; ary [b] = 온도; } public static void main (String [] args) {int [] ary = util.generateintArray (10); System.out.println ( "원본 시퀀스 :"); util.printarray (ary); 정렬 (Ary, 5); System.out.println ( "정렬 :"); util.printarray (ary); }} 결과:
원래 순서 : [2, 8, 4, 3, 7, 5, 1, 9, 0, 6] 왼쪽에서 교환하기위한 색인 : 1 오른쪽으로의 교환을위한 색인 : 8 [2, 0, 4, 4, 3, 5, 9, 8, 6] 왼쪽에서 교환하기위한 색인 : 4 오른쪽으로의 교환에 대한 인덱스 : 6 : 5]. 분류 : [2, 0, 4, 3, 1, 5, 7, 9, 8, 6]
간격 부서의 또 다른지도 :
배열의 첫 번째 요소를 간격 값으로 사용하여 그림에 표시된 결과가 형성 될 때까지 두 번째 요소에서 분할하십시오.
그런 다음 l <t 간격의 오른쪽 경계 값과 t를 교환하여 다음 결과를 형성합니다.
이러한 방식으로 다음과 같이 빠른 정렬 코드를 작성할 수 있습니다.
public void qsort (int array [], int left, int right) {if (왼쪽 <오른쪽) {int key = 배열 [왼쪽]; int high = 오른쪽; int low = 왼쪽+1; while (true) {while (low <= high && array [low] <= key) low ++; while (low <= high && array [high]> = key) high-; (낮은> 높음) 파손; 스왑 (배열, 낮음, 높음); } 스왑 (배열, 왼쪽, 높음); 프린트 array (배열); QSORT (배열, 왼쪽, High-1); QSORT (배열, 하이+1, 오른쪽); }}