快速排序的排序效率在同为O(N*logN)的几种排序方法中效率较高，所以比较重要，面试也经常遇到。
</br>
</br>
基本思想
- 从数列中挑出一个数，作为“基准” （一般就取数组中第一个元素）
- 把比“基准”小的放到左边，比“基准”大的放到右边
- 对“基准”左右两边递归做上面的操作
这个算法的思想关键在于“分而治之”，通过不断的“部分有序”（基准右总大于基准左），达到最终整体有序。
</br>
</br>
实现方法
实现上的关键点我认为就两点：
- 如何让比“基准”小的数在左，大的数在右
- 递归函数的细节
对于第一点，挖坑填数形容的非常贴切，也能帮助记忆。
对于第二点，找好递归出口即可。
</br>
</br>
实现
public class QuickSort {
public static void sort(int[] arr){
int start = 0;
int end = arr.length - 1;
sortPart(start, end, arr);
}
//负责对 数组arr中， 下标start到end的区间进行排序
private static void sortPart(int start, int end, int[] arr){
//需排序的区间只有一个元素时，那么这个区间已有序,这就是递归出口
if(start >= end){
return;
}
//基准数
int benchMark = arr[start];
//区间头尾下标
int i = start;
int j = end;
//挖坑填数
while(j!=i){
//后往前找比benchMark小的数
while(j!=i){
if(arr[j]<benchMark){
arr[i] = arr[j];
break;
}else{
j--;
}
}
//前往后找比benchMark大的数
while(j!=i){
if(arr[i]>benchMark){
arr[j] = arr[i];
break;
}else{
i++;
}
}
}
//此处i已等于j,把benchMark填入即可
arr[i]=benchMark;
//递归 对左右区间排序
sortPart(start, i-1, arr);
sortPart(i+1, end, arr);
}
}
</br>
</br>
