概述
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
Java实现
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]) // 在右边找到一个小于key的值
j--;
data[i] = data[j];
while(i < j && key >= data[i]) // 在左边找到一个大于key的值
i++;
data[j] = data[i];
}
data[i] = key;// 放回key,此时key左边的数都比key小,key右边的数字都比key大
printArray(data);
// 对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:
复杂度
时间复杂度: O(nlogn)
