시간 복잡성
평균 : O (NLGN)
최악의 경우 : O (n*n), 데이터가 이미 분류 상태에있을 때 발생합니다.
1. 데이터에서 값 a [i]를 참조로 선택하십시오.
2. [i]를 참조로 취하려면 데이터를 2 부분으로 나눕니다 : P1 및 P2. p1≤a [i]의 모든 데이터, p2> a [i]의 모든 데이터는 {{p1} {a [i]} {p2}}가됩니다.
3. 각 부분에 단 1 개의 데이터 만 남을 때까지 P1 및 P2로 위의 단계를 반복하십시오.
4. 데이터는 오름차순으로 정렬됩니다
기본 예 : 예 :
원시 데이터 :
{3, 9, 8, 5, 2, 1, 6} 1 단계 : 첫 번째 데이터를 선택하십시오 : 3
2 단계 : 데이터를 두 부분으로 나누고 왼쪽은 ≤3이고 오른쪽은> 3보다 큽니다.
{2,1} {3} {9,8,5,6} 3 단계 : 각 부품에 1 개의 데이터 만 남을 때까지 각 부품에 대한 위의 단계를 반복하십시오.
{2,1} => {1} {2} {9, 8, 5, 6} => {8, 5, 6} {9} => {5, 6} {8} {9} => {5} {6} {8} {9} 4 단계 : 데이터는 오름차순 순서로 정렬됩니다.
{1} {2} {3} {5} {6} {8} {9}프로그램의 데이터는 일반적으로 배열에 저장됩니다. 유형의 int 배열을 예로 들어, 위의 단계를 QuickSort 함수 프로토 타입에 쓸 수 있습니다.
QuickSort (int begin, int end) {// 시작은 배열의 첫 번째 데이터의 인덱스 값입니다. 끝은 배열 +1의 마지막 데이터의 인덱스 값입니다. // 데이터가 1 개 또는 0 데이터 만 있으면 프로그램이 if (시작 == end || begin ==) return을 반환합니다. int p = in [begin]; // p는 선택한 참조 데이터입니다. 첫 번째 데이터를 선택하십시오 int a = 시작 +1; // a 2 부분으로 된 데이터의 인덱스 값은 라인 B = a; // b = a; // b로서 (; b <end; b ++) {// 데이터를 기준 데이터와 비교할 데이터의 인덱스 값입니다. ([b] <p) {// <참조 데이터 인 경우 (a == b) {a ++; 계속;} // 데이터가 이미 왼쪽에 있으면 int temp = [a]에서 int temp = 이동하지 않습니다. // 데이터를 왼쪽으로 [a] = in [b]로 이동합니다. [b] = 온도에서; a ++; // [a-1]에서 [begin] = in [a-1]; if (a-1> 시작) {// 왼쪽에 데이터가있는 경우 위의 단계를 반복하십시오 (시작, a); } if (end-1> a) {// 오른쪽에 데이터가 있으면 위의 단계를 반복합니다 (a, end); } 반품; // 데이터가없는 경우} 알고리즘 최적화
위의 빠른 정렬 알고리즘은 입력 데이터를 고려하지 않기 때문에 가장 기본적인 빠른 정렬이라고 할 수 있습니다. 그러나이 알고리즘의 결함을 쉽게 찾을 수 있습니다. 이것은 입력 데이터가 기본적으로 주문되거나 완전히 주문 될 때 알고리즘이 더 이상 O (Nn)가 아니라 O (N^2)로 변성됩니다.
근본 원인은 코드 구현에서 한 번에 첫 번째 배열에서만 시작하기 때문입니다. "3- 헤더", 즉 ARR [LOW], ARR [High], ARR [(Low+High)/2]의 중간 값을 피벗 레코드로 사용하면 최악의 시나리오에서 빠른 정렬의 성능을 크게 향상시킬 수 있습니다. 그러나 배열 주문 케이스에서 성능을 O (N)로 향상시킬 수는 없습니다. 최악의 시나리오에서 빠른 분류의 시간 성능을 개선하는 방법도 있습니다.
또한 빠른 분류에는 재귀 스택이 필요하며, 이는 일반적으로 깊지 않고 로그 (N) 레벨에 있습니다. 그러나 두 배열의 길이가 한 번에 나뉘어지면 심각하게 불균형하면, 최악의 경우 스택의 깊이가 O (n)으로 증가합니다. 현재 스택 공간에 의해 가져온 공간적 복잡성은 무시할 수 없습니다. 추가 변수의 오버 헤드가 추가되면 여기에서 끔찍한 O (n^2) 공간 복잡성에 도달 할 수도 있습니다. 따라서 빠른 분류의 최악의 공간 복잡성은 고정 값이 아니며 같은 수준이 아닐 수도 있습니다.
이 문제를 해결하기 위해 각 구분 후 끝의 길이를 비교하고 짧은 시퀀스를 먼저 정렬 할 수 있습니다 (목적은 먼저이 스택을 먼저 종료하여 공간을 확보하는 것입니다).
다음은 빠른 정렬을위한 세 가지 최적화 아이디어입니다.
작은 배열의 경우 삽입 분류를 사용하여 재귀적인 호출을 피할 수 있습니다. 예를 들어, (hi <= lo + m)이면 정렬 삽입으로 이동할 수 있습니다.
서브 어레이의 중앙값을 사용하여 배열을 슬라이스하십시오. 이로 인해 슬라이싱이 향상되지만 중앙값을 계산하는 데 드는 비용이 발생합니다.
배열에 많은 수의 반복 요소가 포함 된 경우 3 방향 슬라이싱을 사용할 수 있습니다. 배열을 세 부분으로 나누면 각각 슬라이싱 요소보다 작은 배열 요소에 해당합니다. 코드 구현은 다음과 같습니다.
개인 정적 void sort1 (int [] a, int lo, int hi) {if (hi <= lo) return; int lt = lo, i = lo + 1, gt = hi; int v = a [lo]; while (i <= gt) {if (a [i] <v) {swap (a, lt ++, i ++); } else if (a [i]> v) {swap (a, i, gt-); } else {i ++; } sort (a, lo, lt -1); 정렬 (a, gt + 1, hi); }}