概述
通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小章姓，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序秃殉，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列咪笑。
Java實(shí)現(xiàn)
public class QuickSort {
public static void main(String[] args) {
int[] array = {32,5,66,48,99,21,55};
System.out.print("QuickSort \n");
printArray(array);
System.out.print("start:\n");
quickSort(array,0,array.length-1);
// printArray(array);
System.out.print("end:\n");
}
static void quickSort(int[] data, int left, int right){
if(left>=right)return;
int i = left,j = right,key = data[left];
while (i < j){
while(i < j && key <= data[j]) // 在右邊找到一個(gè)小于key的值
j--;
data[i] = data[j];
while(i < j && key >= data[i]) // 在左邊找到一個(gè)大于key的值
i++;
data[j] = data[i];
}
data[i] = key;// 放回key,此時(shí)key左邊的數(shù)都比key小,key右邊的數(shù)字都比key大
printArray(data);
// 對(duì)key的左右兩邊遞歸
quickSort(data,left,i-1);
quickSort(data,i+1,right);
}
static void printArray(int[] arr){
for(int i=0;i<arr.length;i++){
System.out.print(arr[i]+" ");
}
System.out.print("\n");
}
}
排序效果
QuickSort
32 5 66 48 99 21 55
start:
21 5 32 48 99 66 55
5 21 32 48 99 66 55
5 21 32 48 99 66 55
5 21 32 48 55 66 99
5 21 32 48 55 66 99
end:
復(fù)雜度
時(shí)間復(fù)雜度: O(nlogn)
