빠른 정렬은 참조 (피벗)로 요소 (원래 하나를 찾을 수 있음)를 찾은 다음, 기준 왼쪽의 요소 값이 참조 값과 값보다 크지 않도록 배열을 분할하는 것입니다. 참조의 오른쪽에있는 요소는 참조 값 이상이 아니며, 벤치 마크로 사용되는 요소는 정렬 후 올바른 위치로 조정됩니다. 재귀 적으로 빠르게 정렬하면 정렬 후 다른 N-1 요소를 올바른 위치로 조정하십시오. 마지막으로, 각 요소는 정렬 후 올바른 위치에 있고 정렬이 완료됩니다. 따라서 빠른 정렬 알고리즘의 핵심 알고리즘은 분할 작업, 즉 벤치 마크의 위치를 조정하고 재귀를 나누고 정복하기 위해 리턴 벤치 마크의 최종 위치를 조정하는 방법입니다.
빠른 정렬을위한 알고리즘은 다음과 같습니다.
1) 분류가 시작될 때 두 변수 i와 j를 설정하십시오. i = 0, j = n-1;
2) 첫 번째 배열 요소를 키 데이터로 사용하여 키에 할당합니다. 즉, key = a [0];
3) J에서 시작하여 앞으로 시작하십시오. 즉, 뒤에서 시작하여 앞으로 (j-), 키보다 작은 첫 번째 값 A [j]를 찾은 다음 [j]와 [i]를 교환합니다.
4) i에서 뒤로 검색하기 시작합니다. 즉, 앞쪽에서 뒤로 (i ++)를 시작하고 키보다 첫 번째 A [i]를 찾아서 A [i]와 [j]를 교환합니다.
5) I = J까지 3 단계와 4 단계를 반복하십시오 (3 단계, 4 단계에서는 조건을 충족하지 않습니다. 4는 핵심 변화보다 크지 않습니다. 또한 변경되지 않은 상태로 유지됩니다. 또한 I == j 프로세스는 I+ 또는 J-가 완료 될 때 정확히 이루어져야하며 루프는 현재로 끝납니다).
예를 들어, 이해하기 쉽지 않을 수 있습니다. 분류 될 순서가 있다고 가정합니다
코드 사본은 다음과 같습니다.
패키지 com.zc.manythread;
java.util.random import;
/**
* 빠른 정렬
* @Author 관리자
*
*/
공개 클래스 Qsort {
int [] 날짜;
public qsort (int [] date) {
this.date = 날짜;
}
/**
* 교환 기능
* @param a
* @param i
* @param j
*/
private void swap (int a [], int i, int j) {
int t;
t = a [i];
a [i] = a [j];
a [j] = t;
}
/***************************
* 정렬 함수
* @param a
* @param lo0
* @param hi0
* @반품
*/
int [] QuickSort (int a [], int lo0, int hi0) {// 분할 및 처리 방법은 배열을 [lo0..q-1] 및 [q+1..hi0]로 나누는 것입니다.
int lo = lo0;
int hi = hi0;
int Mid;
if (hi0> lo0) {
mid = a [(Hi0+LO0)/2];
while (lo <= hi) {
while ((lo <hi0) && (a [lo] <mid)) ++ lo;
while ((hi> lo0) && (a [hi]> mid) --hi;
if (lo <= hi) {
스왑 (a, lo, hi);
++ lo;
--안녕;
}
}
if (lo0 <hi) {
QuickSort (A, LO0, HI);
}
if (lo <hi0) {
QuickSort (a, lo, hi0);
}
}
반환 a;
}
/******************
*
* 중복 배열 데이터를 만듭니다
**********************/
private static int [] createate (int count) {
int [] data = new int [count];
for (int i = 0; i <data.length; i ++) {
데이터 [i] = (int) (math.random ()*count);
}
반환 데이터;
}
/**
* 중복 배열 데이터가 없습니다
* @param 수
* @반품
*/
private static int [] createate1 (int count) {
int [] data = new int [count];
랜덤 rand = 새로운 랜덤 ();
부울 [] bool = 새로운 부울 [100];
int num = 0;
for (int i = 0; i <count; i ++) {
하다 {
// 생성 된 숫자가 동일하면 계속 루프
num = rand.nextint (100);
} while (bool [num]);
bool [num] = true;
데이터 [i] = num;
}
반환 데이터;
}
/************ 메인 기능 *******************/
public static void main (String [] args) {
최종 int count = 10;
int [] data = createate1 (count);
for (int n : data) {
System.out.print (n+"/t");
}
QSORT DATA1 = 새로운 QSORT (데이터);
System.out.println ();
int [] a = data1.quicksort (data, 0, count-1);
for (int n : a) {
System.out.print (n+"/t");
}
}
}
결과는 다음과 같습니다.
위는이 기사에 설명 된 모든 내용입니다.