快速排序的排序效率在同为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>

代码

Code