Java 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가 high보다 작음을 계속 검출합니다
이때 low=2, high=6, 동리 R[high]
low가 높음보다 작음을 계속 탐지합니다
이때 low=3, high=5, 동리 R[high]
이때 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 위치 간의 데이터 원소를 정렬할 수 있다.빠른 정렬에 관해서는 여기까지 쓰겠습니다.이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JAVA 버전 정렬 알고리즘의 빠른 정렬 예본고는 JAVA의 빠른 정렬 실현 방법을 실례로 다루고 있다.다음과 같이 여러분에게 참고할 수 있도록 공유합니다. 본고에서 기술한 것이 여러분의 자바 프로그램 설계에 도움이 되기를 바랍니다....
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.