버블 링 분류 의 일종의 개선은 초기 레코드 시퀀스를 키워드로 주문하거나 기본적으로 주문하면 버블 링 분류로 퇴화한다는 것입니다. 재귀 원리가 사용되며, 평균 성능은 동일한 크기 O (n longn)의 모든 정렬 방법 중에서 가장 좋습니다. 평균 시간 측면에서 현재 최고의 내부 분류 방법으로 간주됩니다.
기본 아이디어는 다음과 같습니다. 데이터를 정렬하여 두 개의 독립적 인 부분으로 분류하고 모든 데이터가 다른 부분의 모든 데이터보다 작고이 방법에 따라 데이터의 두 부분을 신속하게 정렬합니다. 전체 데이터를 순서 시퀀스가되기 위해 전체 분류 프로세스를 재귀 적으로 수행 할 수 있습니다.
세 가지 포인터 : 첫 번째 포인터는 피벗 키 포인터 (Pivot)라고하며, 두 번째 포인터 및 세 번째 포인터는 각각 왼쪽 포인터와 오른쪽 포인터이며, 가장 왼쪽 값과 가장 오른쪽 값을 가리 킵니다. 왼쪽 포인터와 오른쪽 포인터 접근은 근사 과정에서 동시에 양쪽에서 중간으로 접근합니다. 피벗과 끊임없이 비교하고 피벗보다 작은 요소를 움직입니다. 선회 후에는 절대 선택 후에도 바뀌지 않을 것이며, 결국 중간에 있으며, 앞면은 뒷면에 있습니다.
두 가지 기능이 필요합니다.
① 재귀 기능 공개 정적 무효 QuickSort (int [] n, int left, int right)
② 세그먼트 함수 (하나의 빠른 정렬 함수) 공개 정적 int 파티션 (int [] n, int left, int right)
Java 소스 코드 (성공적으로 실행) :
코드 사본은 다음과 같습니다.
패키지 테스트 조종법;
공개 클래스 QuickSort {
public static void main (String [] args) {
int [] array = {49,38,65,97,76,13,27};
QuickSort (Array, 0, Array.Length -1);
for (int i = 0; i <array.length; i ++) {
System.out.println (배열 [i]);
}
}
/*먼저 알고리즘을 배열에 따라 데이터 프로토 타입으로 작성한 다음 확장 성 알고리즘을 작성하십시오. 배열 {49,38,65,97,76,13,27}
* */
public static void quicksort (int [] n, int left, int right) {
int pivot;
if (왼쪽 <오른쪽) {
// 피벗으로 피벗, 작은 요소는 왼쪽에 있고 더 큰 요소는 오른쪽에 있습니다.
pivot = 파티션 (n, 왼쪽, 오른쪽);
// 순서가 완전히 정확할 때까지 왼쪽 및 오른쪽 배열에서 빠른 정렬을 재귀 적으로 호출
QuickSort (n, 왼쪽, 피벗 -1);
QuickSort (n, pivot + 1, 오른쪽);
}
}
public static int partition (int [] n, int left, int right) {
int pivotkey = n [왼쪽];
// 피벗은 선택한 후에는 절대 변하지 않을 것이며, 전면이 작고 큰 등으로 가운데에있을 것입니다.
while (왼쪽 <오른쪽) {
while (왼쪽 <right && n [오른쪽]> = pivotkey) -권리;
// 요소를 피벗보다 작게 이동하면이 시점에서 올바른 위치는 비어 있고 피벗 키보다 큰 숫자가 낮은 위치를 채우십시오.
n [왼쪽] = n [오른쪽];
while (왼쪽 <오른쪽 && n [왼쪽] <= pivotkey) ++ 왼쪽;
// 요소를 피벗보다 크게 이동하면이 시점에서 왼쪽 위치는 비어 있고 피벗 키보다 작은 숫자가 높은 위치를 채우십시오.
n [오른쪽] = n [왼쪽];
}
// 왼쪽 == 오른쪽이면 빠른 정렬 트립을 완료하면 왼쪽 비트가 비어 있습니다.
n [왼쪽] = pivotkey;
왼쪽으로 돌아갑니다.
}
}