快速排序算法

思路：選擇基準數(shù)末盔，將所有小于基準數(shù)的移動到基準數(shù)的左邊功偿，大于的移動到右邊盆佣，之后采用分治思想，遞歸調(diào)用械荷。

步驟如下：

首先共耍，需要一個待排序的數(shù)組。

待排序數(shù)組

哨兵A和B

哨兵B移動

之后A開始移動，發(fā)現(xiàn)本身位置20大于temp，那么不用繼續(xù)移動了恐锦，直接將20賦值給B所在位置往果，B向前移動一位。（同理）

哨兵A移動

第一次移動的一定是B哨兵而不是哨兵A一铅，讀者可以先自己思考為什么這樣做陕贮，后面會給出答案。

移動到下圖的時候注意潘飘，此時應該是B繼續(xù)向前搜索小于temp的值肮之。

判斷A是否小于B

結果發(fā)現(xiàn)，當B移動到A位置時卜录，發(fā)現(xiàn)也沒有找到小于temp的數(shù)戈擒，這時就需要把temp這個基準數(shù)插入到這個位置，結束一輪尋找艰毒。

插入基準數(shù)

至此我們發(fā)現(xiàn)筐高，8左邊的數(shù)都小于8，右邊的數(shù)都大于8丑瞧，這就完成了一次操作柑土。

之后采用分治法，將8左邊的序列當作一個數(shù)組绊汹，右邊的序列當做一個數(shù)組稽屏，對兩個數(shù)組都進行上面的操作（也就是重新傳入排序方法中，進行遞歸調(diào)用）西乖。

總結

• 主要的判斷條件是A是否小于B狐榔，如果小于B就結束尋找將基準數(shù)插入。
• 為什么一定要從哨兵B先開始呢获雕？其實自己實驗一下就能知道為什么薄腻。

哨兵A移動

這里如果賦值了的話萝玷，那么15就變成20嫁乘，15這個數(shù)就丟失了，你可能會想球碉，我可以拿一個數(shù)先把15記錄下來呀蜓斧，這樣做可以，我們假設用temp1記錄下15睁冬，之后繼續(xù)向下走挎春，我們走到最后看疙，如下圖。

最后

將基準數(shù)8加入到arr[3]這個位置直奋。那么temp1該如何處理呢能庆，賦值到arr[0]位置嗎，如果這樣做脚线，那8的左邊就出現(xiàn)了一個大于8的數(shù)字搁胆，違反了快速排序的條件。

全部代碼如下

/**
 * Created by ShouJingGuo on 2018/3/14.
 * 快速排序
 */
public class QuickSort<T> {
    private Comparator<T> comparator;

    QuickSort(Comparator<T> comparator){
        if(comparator == null){
            throw new NullPointerException("比較器不能為null");
        }
        this.comparator = comparator;
    }

    public void quickSort(T[] arr){
        int i = 0, j = arr.length - 1;
        quickSort(arr, i, j);
    }

    private void quickSort(T[] arr, int left, int right){
        if(left < right) {
            int i = left, j = right;
            T temp = arr[left];
            while (i < j) {
                while ((i < j) && (comparator.compare(temp, arr[j]) < 0)) {
                    j--;
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }

                while ((i < j) && (comparator.compare(temp, arr[i]) > 0)) {
                    i++;
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = temp;
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }

    public static void main(String[] args) {
        Integer arr[] = {10,50,24,11,68,20,41,0,24,25,4,7,94,15,5,44,66};
        QuickSort<Integer> quickSort = new QuickSort<>(new IntegerComparator());
        quickSort.quickSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}