最近在擼快排，發(fā)現(xiàn)網(wǎng)上寫的千篇一律，理論定義的步驟和代碼稍有些區(qū)別，所以按我自己理解的在整理一遍
首先抄一下網(wǎng)上的定義和模擬圖：

• 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）；重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）。
• 在這個分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置。這個稱為分區(qū)（partition）操作；
• 遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。
  
  image.png
  
  從動圖就可以看到開始時候基準(zhǔn)為array[0]，當(dāng)比較比array[0]小時，放到array[0]后面，
  
  image.png
  
  現(xiàn)在有這么個數(shù)組：
  [6,2,9,3,5,1,7]
  如果我們按理論的來應(yīng)該這么做：
  step1：將pivot設(shè)為第一個值6，找到比6小的值2：[6,2,9,3,5,1,7]
  step2：將2放到6前面[2,6,9,3,5,1,7]
  step3：同上將3放到6前面[2,3,6,9,5,1,7]
  ... : [2,3,1,5,6,9,7]
  然后將2，9(6的下一個)作為pivot遞歸繼續(xù)
  這是正常人理解的定義步驟，但卻不是代碼實現(xiàn)步驟...
  因為你會發(fā)現(xiàn)，如果將2放在6前面，需要將2之前的整個數(shù)組往后移一位，增加了復(fù)雜度。

那么實際代碼處理是怎么樣的？
用了一個取巧的方式，增加一個指針，將比pivot小的數(shù)放到pivot后面，指針后移，最后將pivot和最后的指針位置交換下就可以了。
那么我們來看：
step1：相同，將pivot設(shè)為第一個值6，找到比6小的值2：[6,2,9,3,5,1,7]，增加一個指針指向pivot后面的位置(下標(biāo)1)
step2：將2和指針互換位置，由于這里是同一個，不變[6,2,9,3,5,1,7]，指針后移到下標(biāo)2
step3：找到下一個值3，和下標(biāo)2的值9換位，[6,2,3,9,5,1,7]指針后移到下邊3
step4：同上找到5，對列變?yōu)閇6,2,3,5,9,1,7]，指針后移到4
step5：[6,2,3,5,1,9,7],指針到5
step6：將6和最后一個小于6(即是指針之前的一位下標(biāo)5-1=4)的值換位[1,2,3,5,6,9,7]
后面的流程將6作為pivot分左右兩側(cè)繼續(xù)遞歸就一樣了。
這樣比只是在最后循環(huán)結(jié)束后多了一次交換過程。

網(wǎng)上的樣例代碼如下：

//Java 代碼實現(xiàn)
 public class QuickSort implements IArraySort {
 
     @Override
     public int[] sort(int[] sourceArray) throws Exception {
         // 對 arr 進(jìn)行拷貝，不改變參數(shù)內(nèi)容
         int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
 
         return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
       }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 設(shè)定基準(zhǔn)值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}