버블 분류, 선택 분류 등과 같은 알고리즘과 비교하여 특정 알고리즘 원칙 및 빠른 분류 구현은 어렵습니다. 빠른 정렬을 더 잘 이해하기 위해, 우리는 여전히 빠른 분류의 알고리즘 원리를 예제 형태로 자세히 설명합니다. 이전 정렬 알고리즘에서는 5 명의 선수의 높이 분류 문제를 예로 들어 설명합니다. 빠른 분류의 특성을 더 잘 반영하기 위해 여기에 3 명의 선수가 추가됩니다. 예제의 8 명의 운동 선수와 높이 정보는 다음과 같습니다 (F, G, H는 새로운 운동 선수) : A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182)
이전 정렬 알고리즘에서 이러한 분류는 모두 코치가 수행했습니다. 선수의 수가 증가 했으므로 코치는 휴식을 취하기 위해 기회를 잡기를 원했기 때문에 코치는 두 조수에게 전화를 걸어 8 명의 선수의 높이를 왼쪽에서 오른쪽으로, 낮은 정렬 방식으로 분류하도록 요청했습니다.
빠른 분류 방법의 알고리즘 원리에 따르면, 두 조수는 아래 그림과 같이 선수 배열의 양쪽에 서 있습니다.
먼저, 어시스턴트 1은 배치에서 선수를 선택합니다 (일반적으로 왼쪽 또는 중간 선수의 첫 번째 선수를 선택). 여기에서 선수 A (181)를 선택합니다. 정렬은 왼쪽에서 오른쪽에서 오른쪽에서 낮은 곳에서 높을 수 있으므로 조수 1은 (181)보다 높이가 작은 운동 선수를 요구합니다 (선택된 A (181)는 비교를위한 벤치 마크로 사용됩니다.이 라운드의 모든 비교는 처음 선택한 선수 A (181))와 비교됩니다.
빠른 분류의 첫 번째 라운드의 상세한 다이어그램을 계속 참조해 봅시다.
분류 및 검색 과정에서 두 조수가 만나면 현재 라운드의 비교가 중지되고 처음 선택된 선수 A (181)는 두 조수가 만나는 빈 공간에 배치됩니다.
빠른 정렬로,이 라운드의 라운드는 두 조수가 만날 때 끝납니다. 현재, 우리는 두 선수가 디비전 지점으로 만난 위치 A (181)를 사용하여 왼쪽에있는 선수는 A (181)보다 작은 운동 선수이며, 오른쪽에있는 선수는 (181)보다 큰 운동 선수라는 것을 발견했습니다. 이 시점에서, 우리는 (181)의 왼쪽과 오른쪽에있는 두 종류를 분리합니다. 위의 두 조수의 분류 방법을 사용하여 양쪽에 배열을 계속 정렬하면 여러 배열 후에 마침내 필요한 분류 결과를 얻을 수 있습니다.
위는 빠른 정렬의 전체 분류 구현 프로세스입니다. 빠른 정렬은 위의 분류 규칙을 사용하여 배열을 두 가지 배열로 나누고, 두 가지 배열이 나뉘어 질 배열이 없을 때까지 4 개의 배열로 나누어주는 것입니다. 마지막으로 필요한 분류 결과를 얻습니다.
이제 우리는 여전히 빠른 정렬을 사용하여 위의 8 명의 선수의 높이를 정렬하도록 Java 코드를 프로그램합니다.
/*** 지정된 배열에서 시작부터 끝까지 요소의 빠른 정렬** @param 배열 지정된 배열* @param 신속하게 정렬 해야하는 배열 문의의 결과 지점을 빠르게 정렬해야합니다* @param* @param 종료*/public static final void quicksort (int array, int start, int int) {/i in the its it it the the its its it is the its its its its it it a e -public static void quicksort*/public static void Quicksort (int int int it). 조수 2 int i = start, j = end; int pivot = 배열 [i]; // 첫 번째 요소를 참조 요소로 취합니다 int emptyIndex = i; // 빈 공간의 위치 색인이 표시되고 기본값은 참조 요소의 위치가 검색되는 경우 // 정렬 할 요소가 둘 이상인 경우 빠른 정렬을 입력하면 (I와 J가 다르면, 적어도 2 개의 배열 요소가 정렬되어야한다는 것을 의미합니다. if (i <j) {// 어시스턴트 2가 조수 1을 만나기 전에 해당 요소를 찾으면 어시스턴트 1의 "공석"에 요소를 제공합니다. } // 어시스턴트 1은 왼쪽에서 오른쪽으로 참조 요소보다 큰 요소를 찾기 시작합니다 (i <j && array [i] <= pivot) i ++; if (i <j) {// 어시스턴트 1이 어시스턴트 2를 만나기 전에 해당 요소를 찾으면 어시스턴트 2의 "공석"에 요소를 제공하고, 비어있는 배열이됩니다 [emplyindex] = array [empallindex = i]; }} // 어시스턴트 1 및 어시스턴트 2가 발생한 후 루프가 중지되고 초기 참조 값은 마지막 빈 배열 [empallindex] = 피벗으로 가져옵니다. // =====이 빠른 정렬 라운드가 완료됩니다 ===== // 분할 지점 I의 왼쪽에 2 개 이상의 요소가있는 경우, 재귀 호출은 (i -start> 1) {Quicksort (Array, 0, i -1); } // 분할 지점 j의 오른쪽에 2 개가 넘는 요소가있는 경우, 재귀 호출은 (end -j> 1) {QuickSort (Array, J + 1, End); }} // 메인 방법 공개 정적 무효 메인 (문자열 [] args) {// ===== 8 명의 운동 선수의 높이를 사용하여 빠른 정렬 메소드 ===== // a (181), b (169), c (187), d (172), e (163), f (191), g (189), h (182) int int = int int = 189) 187, 172, 163, 191, 189, 182}; // Quick Sort 메소드를 호출 QuickSort (높이, 0, heights.length -1); // (int height : heights) {system.out.println (높이); }}위의 Java 코드 실행 결과는 다음과 같이 출력입니다.
16316917218182187189191
참고 : 현지 사고 차이로 인해 위의 빠른 정렬 코드 구현에는 여러 가지 변형이있을 수 있습니다. 그러나 변형이 무엇이든간에 빠른 정렬의 핵심 아이디어는 변하지 않습니다.
다른 구현 : 일원 스캔
빠른 정렬 배열 슬라이싱을위한 또 다른 편도 스캔 버전이 있습니다. 특정 단계는 배열의 마지막 요소를 슬라이싱 요소로 선택하고 두 개의 포인터를 설정하는 것입니다. 포인터 I은 배열의 첫 번째 요소 앞의 위치를 가리키고 J는 배열의 첫 번째 요소를 가리 킵니다. J 전면에서 오른쪽으로 스캔합니다. 슬라이싱 요소가 적거나 동일하게 발생하면 I를 하나에 추가 한 다음 I 및 J로 가리키는 요소를 교환하십시오. 마지막으로, 위치 I+1 및 슬라이싱 요소에서 요소를 교환하여 배열 분할을 완료하십시오. 코드 구현은 다음과 같습니다.
int partition (int [] a, int lo, int hi) {int i = lo -1, j = lo; int v = a [hi]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } j ++; } swap (a, i + 1, hi); 반환 i + 1;}