摘要：快速排序的核心是以基數為中心，將數組分為兩個區間，小于基數的放到基數的左邊，大于基數的放到基數的右邊。快速排序在每次挖坑的過程中，需要個空間存儲基數。而快速排序的大概需要次的處理，所以占用空間也是個。

快速排序是C.R.A.Hoare提出的一種交換排序。它采用分治的策略，所以也稱其為分治排序。

實現快速排序算法的關鍵在于，先在數組中選一個數作為基數，接著以基數為中心將數組中的數字分為兩部分，比基數小的放在數組的左邊，比基數大的放到數組的右邊。接下來我們可以用遞歸的思想分別對基數的左右兩邊進行排序。

整個快速排序可以總結為以下三步：

從數組中取出一個數作為基數

分區，將數組分為兩部分，比基數小的放在數組的左邊，比基數大的放到數組的右邊。

遞歸使左右區間重復第二步，直至各個區間只有一個數。

下面我用博客專家MoreWindows的挖坑填數+分治思想來分析一個實例（使用快速排序將以下數組排序）

首先，取數組中的第一個數字52為第一次分區的基數

初始時，start=0、end=8、base=52（start區間的頭、end區間的尾、base基數）

由于將array[0]中的數據賦給了基數base，我們可以理解為在array[0]處挖了一個坑，當然這個坑是可以用其它數據來填充的。

接著我們從end開始 向前找比base小或者等于base的數據，很快我們就找了19，我們就19這個數據填充到array[0]位置，這樣array[8]位置就又形成了一個新的坑。不怕，我們接著找符合條件的數據來填充這個新坑。
start=0、end=8、base=52

然后我們再從start開始向后找大于或等于base的數據，找到了88，我們用88來填充array[1]，這樣array[1]位置也形成了一個新坑。 Don"t Worry 我們接著從end開始 向前找符合條件的數據來填充這個坑。
start=1、end=8、base=52

{% note success %} 需要注意的是start和end隨著查找的過程是不斷變化的。 {% endnote %}

之后一直重復上面的步驟，先從前向后找，再從后向前找。直至所有小于基數的數據都出現在左邊，大于基數的數據都出現在右邊。

最后將base中的數據填充到數組中即可完成這次分區的過程。

然后遞歸使左右區間重復分區過程，直至各個區間只有一個數，即可完成整個排序過程。

{% note primary %}
快速排序的核心是以基數為中心，將數組分為兩個區間，小于基數的放到基數的左邊，大于基數的放到基數的右邊。

在第一次分區的時候我們以數組中的第一個數據為基數，在array[0]處挖了一個坑，這時我們只能從區間的后面往前找小于基數的數據來填充array[0]這個坑，如果直接從前往后找符合條件的數據，就會造成大于基數的數據留在了數組的左邊。

所以我們只能通過從后往前找小于基數的數據來填充前面的坑，從前往后找大于基數的數據來填充后面的坑。這樣可以保證在只遍歷一遍數組就能將數組分為兩個區間

最后一步我們用基數本身來填充數組的最后一個坑
{% endnote %}

代碼實現：

// 分區
    public static int partition(int[] array, int start, int end) {
        int base = array[start];
        while (start < end) {
            while (start < end && array[end] >= base)
                end --;
            array[start] = array[end];
            while (start < end && array[start] <= base)
                start ++;
            array[end] = array[start];
        }
        array[end] = base;
        return start;
    }
    
    // 快速排序
    public static void quickSort(int[] array,int start, int end) {
        if(start < end) {
            int index = partition(array, start, end);
            quickSort(array, start, index-1);
            quickSort(array, index+1, end);
        }
    }

class QuickSort {
public:

    //快速排序
    int* quickSort(int* A, int n) {
        QSort(A,0,n-1);
        return A;
    }
    //對數組A[low,...,high]
    void QSort(int *A,int low,int high) {
        if(low=key)
                high--;
            A[low]=A[high];
            while(low
算法分析：
當數據有序時，以第一個關鍵字為基準分為兩個子序列，前一個子序列為空，此時執行效率最差。時間復雜度為O(n^2)
而當數據隨機分布時，以第一個關鍵字為基準分為兩個子序列，兩個子序列的元素個數接近相等，此時執行效率最好。時間復雜度為O(nlogn)
所以，數據越隨機分布時，快速排序性能越好；數據越接近有序，快速排序性能越差。
快速排序在每次“挖坑”的過程中，需要 1 個空間存儲基數。而快速排序的大概需要 NlogN次的處理，所以占用空間也是 NlogN 個。
下面我們在來看幾種改進的快排算法
快速排序中元素切分的方式
快速排序中最重要的步驟就是將小于等于中軸元素的整數放到中軸元素的左邊，將大于中軸元素的數據放到中軸元素的右邊，這里我們把該步驟定義為"切分"。以首元素作為中軸元素，下面介紹幾種常見的"切分方式"。
兩端掃描，一端挖坑，另一端填補
這種方法就是我們上面用到的"挖坑填數"，在這再做個簡單的總結。
這種方法的基本思想是：使用兩個變量i和j，i指向最左邊的元素，j指向最右邊的元素，我們將首元素作為中軸，將首元素復制到變量pivot中，這時我們可以將首元素i所在的位置看成一個坑，我們從j的位置從右向左掃描，找一個小于等于中軸的元素A[j]，來填補A[i]這個坑，填補完成后，拿去填坑的元素所在的位置j又可以看做一個坑，這時我們在以i的位置從前往后找一個大于中軸的元素來填補A[j]這個新的坑，如此往復，直到i和j相遇（i == j，此時i和j指向同一個坑）。最后我們將中軸元素放到這個坑中。最后對左半數組和右半數組重復上述操作。
這種方法的代碼實現請參考上面的完整代碼。
從兩端掃描交換
這種方法的基本思想是：使用兩個變量i和j，i指向首元素的元素下一個元素（最左邊的首元素為中軸元素），j指向最后一個元素，我們從前往后找，直到找到一個比中軸元素大的，然后從后往前找，直到找到一個比中軸元素小的，然后交換這兩個元素，直到這兩個變量交錯（i > j）（注意不是相遇 i == j，因為相遇的元素還未和中軸元素比較）。最后對左半數組和右半數組重復上述操作。
public static void QuickSort1(int[] A, int L, int R){
    if(L < R){//遞歸的邊界條件，當 L == R時數組的元素個數為1個
        int pivot = A[L];//最左邊的元素作為中軸，L表示left, R表示right
        int i = L+1, j = R;
        //當i == j時，i和j同時指向的元素還沒有與中軸元素判斷，
        //小于等于中軸元素，i++,大于中軸元素j--,
        //當循環結束時，一定有i = j+1, 且i指向的元素大于中軸，j指向的元素小于等于中軸
        while(i <= j){
            while(i <= j && A[i] <= pivot){
                i++;
            }
            while(i <= j && A[j] > pivot){
                j--;
            }
            //當 i > j 時整個切分過程就應該停止了，不能進行交換操作
            //這個可以改成 i < j， 這里 i 永遠不會等于j， 因為有上述兩個循環的作用
            if(i <= j){
                Swap(A, i, j);
                i++;
                j--;
            }
        }
        //當循環結束時，j指向的元素是最后一個（從左邊算起）小于等于中軸的元素
        Swap(A, L, j);//將中軸元素和j所指的元素互換
        QuickSort1(A, L, j-1);//遞歸左半部分
        QuickSort1(A, j+1, R);//遞歸右半部分
    }
}
從一端掃描
和前面兩種方法一樣，我們選取最左邊的元素作為中軸元素，A[1,i]表示小于等于pivot的部分，i指向中軸元素（i < 1），表示小于等于pivot的元素個數為0，j以后的都是未知元素（即不知道比pivot大，還是比中軸元素小），j初始化指向第一個未知元素。

當A[j]大于pivot時，j繼續向前，此時大于pivot的部分就增加一個元素

當A[j]小于等于pivot時，我們注意i的位置，i的下一個就是大于pivot的元素，我們將i增加1然后交換A[i]和A[j]，交換后小于等于pivot的部分增加1，j增加1，繼續掃描下一個。而i的下一個元素仍然大于pivot，又回到了先前的狀態。

public static void QuickSort3(int[] A, int L, int R){
    if(L < R){
        int pivot = A[L];//最左邊的元素作為中軸元素
        //初始化時小于等于pivot的部分，元素個數為0
        //大于pivot的部分，元素個數也為0
        int i = L, j = L+1;
        while(j <= R){
            if(A[j] <= pivot){
                i++;
                Swap(A, i, j);
                j++;//j繼續向前，掃描下一個
            }else{
                j++;//大于pivot的元素增加一個
            }
        }
        //A[i]及A[i]以前的都小于等于pivot
        //循環結束后A[i+1]及它以后的都大于pivot
        //所以交換A[L]和A[i],這樣我們就將中軸元素放到了適當的位置
        Swap(A, L, i);
        QuickSort3(A, L, i-1);
        QuickSort3(A, i+1, R);
    }
}
快速排序的改進方法
三向切分的快速排序
三向切分快速排序的基本思想，用i，j，k三個將數組切分成四部分，a[0, i-1]表示小于pivot的部分，a[i, k-1]表示等于pivot的部分，a[j+1]之后的表示大于pivot的部分，而a[k, j]表示未進行比較的元素（即不知道比pivot大，還是比pivot元素小）。我們要注意a[i]始終位于等于pivot部分的第一個元素，a[i]的左邊是小于pivot的部分。

我們依舊選取最左邊的元素作為中軸元素，初始化時，i = L，k = L+1，j=R（L表示最左邊元素的索引，R表示最右邊元素的索引）

通過上一段的表述可知，初始化時  j）。
這里我們掃描的目的就是為了逐個減少未知元素，并將每個元素按照和pivot的大小關系放到不同的區間上去。
在k的掃描過程中我們可以對a[k]分為三種情況討論

a[k] < pivot 交換a[i]和a[k]，然后i和k都自增1，k繼續掃描
a[k] = pivot k自增1，k接著繼續掃描

a[k] > pivot 這個時候顯然a[k]應該放到最右端，大于pivot的部分。但是我們不能直接將a[k]與a[j]交換，因為目前a[j]和pivot的關系未知，所以我們這個時候應該從j的位置自右向左掃描。而a[j]與pivot的關系可以繼續分為三種情況討論

a[j] > pivot --- j自減1，j接著繼續掃描
a[j] = pivot --- 交換a[k]和a[j]，k自增1，j自減1，k繼續掃描（注意此時j的掃描就結束了）
a[j] < pivot --- 此時我們注意到a[j] < pivot, a[k] > pivot, a[i] == pivot，那么我們只需要將a[j]放到a[i]上，a[k]放到a[j]上，而a[i]放到a[k]上。然后i和k自增1，j自減1，k繼續掃描（注意此時j的掃描就結束了）



注意，當掃描結束時，i和j的表示了=等于pivot部分的起始位置和結束位置。我們只需要對小于pivot的部分以及大于pivot的部分重復上述操作即可。

public static void QuickSort3Way(int[] A, int L, int R){
    if(L >= R){//遞歸終止條件，少于等于一個元素的數組已有序
        return;
    }
     
    int i,j,k,pivot;
    pivot = A[L]; //首元素作為中軸
    i = L;
    k = L+1;
    j = R;
     
    OUT_LOOP:
    while(k <= j){
        if(A[k] < pivot){
            Swap(A, i, k);
            i++;
            k++;
        }else
        if(A[k] == pivot){
            k++;
        }else{// 遇到A[k]>pivot的情況，j從右向左掃描
            while(A[j] > pivot){//A[j]>pivot的情況,j繼續向左掃描
                j--;
                if(j < k){
                    break OUT_LOOP;
                }
            }
            if(A[j] == pivot){//A[j]==pivot的情況
                Swap(A, k, j);
                k++;
                j--;
            }else{//A[j]
雙軸快速排序
雙軸快速排序算法的思路和上面的三向切分快速排序算法的思路基本一致，雙軸快速排序算法使用兩個軸元素，通常選取最左邊的元素作為pivot1和最右邊的元素作pivot2。首先要比較這兩個軸的大小，如果pivot1 > pivot2，則交換最左邊的元素和最右邊的元素，已保證pivot1 <= pivot2。雙軸快速排序同樣使用i，j，k三個變量將數組分成四部分

A[L+1, i]是小于pivot1的部分，A[i+1, k-1]是大于等于pivot1且小于等于pivot2的部分，A[j, R]是大于pivot2的部分，而A[k, j-1]是未知部分。和三向切分的快速排序算法一樣，初始化i = L，k = L+1，j=R，k自左向右掃描直到k與j相交為止（k == j）。我們掃描的目的就是逐個減少未知元素，并將每個元素按照和pivot1和pivot2的大小關系放到不同的區間上去。
在k的掃描過程中我們可以對a[k]分為三種情況討論（注意我們始終保持最左邊和最右邊的元素，即雙軸，不發生交換）

a[k] < pivot1 i先自增，交換a[i]和a[k]，k自增1，k接著繼續掃描
a[k] >= pivot1 && a[k] <= pivot2 k自增1，k接著繼續掃描

a[k] > pivot2: 這個時候顯然a[k]應該放到最右端大于pivot2的部分。但此時，我們不能直接將a[k]與j的下一個位置a[--j]交換（可以認為A[j]與pivot1和pivot2的大小關系在上一次j自右向左的掃描過程中就已經確定了，這樣做主要是j首次掃描時避免pivot2參與其中），因為目前a[--j]和pivot1以及pivot2的關系未知，所以我們這個時候應該從j的下一個位置（--j）自右向左掃描。而a[--j]與pivot1和pivot2的關系可以繼續分為三種情況討論

a[--j] > pivot2 j接著繼續掃描
a[--j] >= pivot1且a[j] <= pivot2 交換a[k]和a[j]，k自增1，k繼續掃描（注意此時j的掃描就結束了）
a[--j] < pivot1 先將i自增1，此時我們注意到a[j] < pivot1,  a[k] > pivot2,  pivot1 <= a[i] <=pivot2，那么我們只需要將a[j]放到a[i]上，a[k]放到a[j]上，而a[i]放到a[k]上。k自增1，然后k繼續掃描（此時j的掃描就結束了）




注意

pivot1和pivot2在始終不參與k，j掃描過程。
掃描結束時，A[i]表示了小于pivot1部分的最后一個元素，A[j]表示了大于pivot2的第一個元素，這時我們只需要交換pivot1（即A[L]）和A[i]，交換pivot2（即A[R]）與A[j]，同時我們可以確定A[i]和A[j]所在的位置在后續的排序過程中不會發生變化（這一步非常重要，否則可能引起無限遞歸導致的棧溢出），最后我們只需要對A[L, i-1]，A[i+1, j-1]，A[j+1, R]這三個部分繼續遞歸上述操作即可。


public static void QuickSortDualPivot(int[] A, int L, int R){
    if(L >= R){
        return;
    }
     
    if(A[L] > A[R]){
        Swap(A, L, R); //保證pivot1 <= pivot2
    }
     
    int pivot1 = A[L];
    int pivot2 = A[R];
     
    //如果這樣初始化 i = L+1, k = L+1, j = R-1,也可以
    //但代碼中邊界條件, i,j先增減，循環截止條件，遞歸區間的邊界都要發生相應的改變
    int i = L;
    int k = L+1;
    int j = R;
 
    OUT_LOOP:
    while(k < j){
        if(A[k] < pivot1){
            i++;//i先增加，首次運行pivot1就不會發生改變
            Swap(A, i, k);
            k++;
        }else
        if(A[k] >= pivot1 && A[k] <= pivot2){
            k++;
        }else{
            while(A[--j] > pivot2){//j先增減，首次運行pivot2就不會發生改變
                if(j <= k){//當k和j相遇
                    break OUT_LOOP;
                }
            }
            if(A[j] >= pivot1 && A[j] <= pivot2){
                Swap(A, k, j);
                k++;
            }else{
                i++;
                Swap(A, j, k);
                Swap(A, i, k);
                k++;
            }
        }
    }
    Swap(A, L, i);//將pivot1交換到適當位置
    Swap(A, R, j);//將pivot2交換到適當位置
     
    //一次雙軸切分至少確定兩個元素的位置，這兩個元素將整個數組區間分成三份
    QuickSortDualPivot(A, L, i-1);
    QuickSortDualPivot(A, i+1, j-1);
    QuickSortDualPivot(A, j+1, R);
}
下面代碼初始化方式使得邊界條件更加容易確定，在下面代碼的方式中A[L+1]~A[i-1]表示小于pivot1的部分，A[i]~A[j]表示兩軸之間的部分，A[j]~A[R-1]表示大于pivot2的部分。
當排序數組中不存在pivot1~pivot2中的部分時，一趟交換完成后i恰好比j大1；當排序數組中僅僅存在一個元素x使得pivot1 <=x <=pivot2時，一趟交換完成，i和j恰好相等。
public static void QuickSortDualPivot(int[] A, int L, int R){
     
    if(L >= R){
        return;
    }
     
    if(A[L] > A[R]){
        Swap(A, L, R); //保證pivot1 <= pivot2
    }
     
    int pivot1 = A[L];
    int pivot2 = A[R];
     
    int i = L+1;
    int k = L+1;
    int j = R-1;
 
    OUT_LOOP:
    while(k <= j){
        if(A[k] < pivot1){
            Swap(A, i, k);
            k++;
            i++;
        }else
        if(A[k] >= pivot1 && A[k] <= pivot2){
            k++;
        }else{
            while(A[j] > pivot2){
                j--;
                if(j < k){//當k和j錯過
                    break OUT_LOOP;
                }
            }
            if(A[j] >= pivot1 && A[j] <= pivot2){
                Swap(A, k, j);
                k++;
                j--;
            }else{//A[j] < pivot1
                Swap(A, j, k);//注意k不動
                j--;
            }
        }
    }
    i--;
    j++;
    Swap(A, L, i);//將pivot1交換到適當位置
    Swap(A, R, j);//將pivot2交換到適當位置
     
    //一次雙軸切分至少確定兩個元素的位置，這兩個元素將整個數組區間分成三份
    QuickSortDualPivot(A, L, i-1);
    QuickSortDualPivot(A, i+1, j-1);
    QuickSortDualPivot(A, j+1, R);
}