快速排序的排序效率在同為O(N*logN)的幾種排序方法中效率較高线梗，所以比較重要绵疲，面試也經(jīng)常遇到答毫。
</br>
</br>
基本思想
- 從數(shù)列中挑出一個數(shù)呛伴，作為“基準(zhǔn)” （一般就取數(shù)組中第一個元素）
- 把比“基準(zhǔn)”小的放到左邊，比“基準(zhǔn)”大的放到右邊
- 對“基準(zhǔn)”左右兩邊遞歸做上面的操作
這個算法的思想關(guān)鍵在于“分而治之”谒所，通過不斷的“部分有序”（基準(zhǔn)右總大于基準(zhǔn)左）热康，達到最終整體有序。
</br>
</br>
實現(xiàn)方法
實現(xiàn)上的關(guān)鍵點我認(rèn)為就兩點：
- 如何讓比“基準(zhǔn)”小的數(shù)在左劣领，大的數(shù)在右
- 遞歸函數(shù)的細節(jié)
對于第一點姐军，挖坑填數(shù)形容的非常貼切，也能幫助記憶尖淘。
對于第二點奕锌，找好遞歸出口即可。
</br>
</br>
實現(xiàn)
public class QuickSort {
public static void sort(int[] arr){
int start = 0;
int end = arr.length - 1;
sortPart(start, end, arr);
}
//負(fù)責(zé)對 數(shù)組arr中村生， 下標(biāo)start到end的區(qū)間進行排序
private static void sortPart(int start, int end, int[] arr){
//需排序的區(qū)間只有一個元素時惊暴，那么這個區(qū)間已有序,這就是遞歸出口
if(start >= end){
return;
}
//基準(zhǔn)數(shù)
int benchMark = arr[start];
//區(qū)間頭尾下標(biāo)
int i = start;
int j = end;
//挖坑填數(shù)
while(j!=i){
//后往前找比benchMark小的數(shù)
while(j!=i){
if(arr[j]<benchMark){
arr[i] = arr[j];
break;
}else{
j--;
}
}
//前往后找比benchMark大的數(shù)
while(j!=i){
if(arr[i]>benchMark){
arr[j] = arr[i];
break;
}else{
i++;
}
}
}
//此處i已等于j,把benchMark填入即可
arr[i]=benchMark;
//遞歸 對左右區(qū)間排序
sortPart(start, i-1, arr);
sortPart(i+1, end, arr);
}
}
</br>
</br>
