Java QuickSort 원칙 및 구현 코드

QuickSort는 일반적으로 사용되는보다 효율적인 정렬 알고리즘이며 인터뷰 과정에서 종종 언급됩니다. 원리를 자세히 설명하고 Java 버전 구현을 제공 해 봅시다.

빠른 분류 아이디어 :

한 번의 트립에서 데이터 요소 세트 RN을 정렬하여 두 개의 독립적 인 부품을 나눈 값입니다. 키워드의 한 부분은 다른 부분보다 작습니다. 그런 다음 독립 요소가 하나만있을 때까지 두 부분의 키워드를 하나씩 정렬하면 전체 요소 컬렉션이 순서대로 정렬됩니다.

빠른 분류 프로세스 - 구멍을 파고 숫자를 채우는 방법 (이것은 매우 생생한 이름), 요소 세트 r [낮음 ... 높음]의 경우 먼저 참조로 숫자 (일반적으로 r [낮음])를 가져옵니다. 및 r [낮은] 모든 요소를 ​​벤치 마크로 재 배열합니다.

r보다 작은 모든 것이 전면에 배치되고 R [낮은]보다 큰 것은 뒷면에 배치되고 R [낮은]은 경계로 사용되고 R [낮은 ... High]는 다음과 같습니다. 두 개의 서브 세트로 나눈 다음 분할. 낮게> = 높음까지.

예를 들면 : r = {37, 40, 38, 42, 461, 5, 7, 9, 12}의 빠른 정렬을 수행하는 과정은 다음과 같습니다 (참고 : 아래 설명 된 요소 표는 0부터 시작됩니다).

기본베이스를 선택하기 시작하십시오 = 37, 아래 표는 높음 = 8, r [8] <베이스 인 경우 높은 = 8에서 시작하여 낮은 = 0, High = 8입니다. 높은 위치에있는 내용을 R [낮음]에 씁니다. 위치는 비어 있고 낮은 = 낮은 +1;

낮은 = 1, r [낮은]>베이스, r [낮음], r [High], High = High -1;

Low <High가 감지되므로 첫 번째 빠른 정렬은 계속 필요합니다.

R [High] <Base, R [High]는 r [Low], Low = Low + 1에 기록되기 때문에이 시간에 LOW = 1, High = 7;

Low, Low = 2, R [Low]> Base에서 시작하여 R [Low]가 R [High], High = High-1에 기록됩니다.

낮은 수치가 높습니다

이 시점에서 낮은 = 2, 높음 = 6, 유사하게, r [높음] <베이스, r [높음]을 r [낮음], 낮은 = 낮은+1으로 쓰기;

낮음, 낮음 = 3, 높이 = 6, r [낮은]>베이스, R [낮음], R [High], High = High-1에서 계속 검출하십시오.

낮은 수가 높다는 것을 계속 감지합니다.

이 시간에 낮은 = 3, 높음 = 5, 유사하게, r [높음] <베이스, r [높음]을 r [낮음], 낮음 = 낮은 +1로 씁니다.

r [낮은]>베이스, r [낮은]를 r [높이], 높이 = 높이 -1로 작성하기 때문에 낮은, 낮음 = 4, 높이 = 5에서 계속 조사하십시오.

현재, Low == High == 4가 감지되며,이 위치는 기지가 위치한 위치이며,이 위치에 기록됩니다.

그런 다음 후속 시퀀스의 빠른 정렬 RS1 = {12,9,7,5} 및 RS2 = {461,42,38,40}을 RSI에 하나의 요소 만 있거나 요소가 없을 때까지 수행하십시오.

(참고 : 위의 형식에서는 정렬에 일부 중복 데이터가 있음을 알 수 있습니다 (원래 데이터의 중복 데이터 없음). 해당 위치의 데이터가 지워지지 않기 때문입니다. 메모리의 데이터를 살펴 봅니다. 특정 시간에 차단하십시오. 다음에 데이터가 위치에 기록 될 때까지는 여전히 IT입니다.이 위치의 데이터는 "PIT"라고 불리는 더러운 데이터입니다).

빠른 정렬 Java 구현 :

코드 사본은 다음과 같습니다.

개인 정적 부울 isempty (int [] n) {

n == null ||.

}

////////////////////////////////////////////////////////////////////////////////////////////////4 ///

/**

* 빠른 정렬 알고리즘 아이디어 - 구멍을 파고 채우는 방법 :

*

* @param n 배열 정렬

*/

public static void QuickSort (int [] n) {

if (isempty (n))

반품;

QuickSort (n, 0, n.length -1);

}

public static void quicksort (int [] n, int l, int h) {

if (isempty (n))

반품;

if (l <h) {

int pivot = 파티션 (n, l, h);

QuickSort (n, l, pivot -1);

QuickSort (n, pivot + 1, h);

}

}

개인 정적 int 파티션 (int [] n, int start, int end) {

int tmp = n [시작];

while (start <end) {

while (n [end]> = tmp && start <end)

끝--;

if (start <end) {

n [start ++] = n [end];

}

while (n [start] <tmp && start <end)

시작 ++;

if (start <end) {

n [end--] = n [시작];

}

}

n [start] = tmp;

리턴 시작;

}

코드에는 다음과 같은 기능이 있습니다.

코드 사본은 다음과 같습니다.

public static void QuickSortSwap (int [] n, int l, int h)

이 기능은 특정 L과 H 위치 사이의 요소에서 데이터 요소를 정렬하기 위해 구현 될 수 있습니다.

그게 빠른 정렬을위한 것입니다.