快速排序演算法，C語言快速排序演算法詳解

本節介紹一個非常優秀且最常用的排序演算法，快速排序演算法。這個演算法極其重要，初學者一定要掌握。

快速排序尤其適用於對巨量資料的排序，它的高速和高效無愧於“快速”兩個字。雖然說它是“最常用”的，可對於初學者而言，用它的人卻非常少。因為雖然很快，但它也是邏輯最複雜、最難理解的演算法，因為快速排序要用到遞回和函數呼叫。

快速排序所採用的思想是分治的思想。所謂分治，就是指以一個數為基準，將序列中的其他數往它兩邊“扔”。以從小到大排序為例，比它小的都“扔”到它的左邊，比它大的都“扔”到它的右邊，然後左右兩邊再分別重複這個操作，不停地分，直至分到每一個分割區的基準數的左邊或者右邊都只剩一個數為止。這時排序也就完成了。

所以快速排序的核心思想就是將小的往左“扔”，將大的往右“扔”，只要能實現這個，就與快速排序的思想吻合。從初學者的角度，“小的往左扔大的往右扔”首先能想到的往往是小的往前插，大的往後插。這確實是一個思路，但我們知道，陣列是不擅長插入的。這種思路雖然能吻合快速排序的思想，但實現起來就不是“快速”排序，而是“慢速”排序了。所以這種方法是不可行的。於是就有了下面的“舞動演算法”。

“舞動演算法”的思想是用交換取代插入，大大提高了排序的速度。下面首先詳細地講解一下陣列快速排序的過程。

假設序列中有 n 個數，將這 n 個數放到陣列 A 中。“舞動演算法”中一趟快速排序的演算法是：

1. 設定兩個變數 i、j，排序開始的時候：i=0，j=n–1。
2. 以陣列第一個元素為關鍵資料，賦給變數 key，即 key=A[0]。
3. 從 j 開始向前搜尋，即由後開始向前搜尋（j--），找到第一個小於 key 的值 A[j]，將 A[j] 和 A[i] 互換。
4. 然後再從 i 開始向後搜尋，即由前開始向後搜尋（++i），找到第一個大於 key 的 A[i]，將 A[i] 和 A[j] 互換。
5. 重複第 3、4 步，直到 i=j。此時就能確保序列中所有元素都與 key 比較過了，且 key 的左邊全部是比 key 小的，key 的右邊全部是比 key 大的。

第一輪比較後序列就以 key 為中心分成了左右兩部分，然後分別對左右兩部分分別遞回執行上面幾個步驟，直到排序結束。

下面列舉一個簡單的例子，比如對如下陣列 a 中的元素使用快速排序實現從小到大排序：

35  12  37  -58  54  76  22

1) 首先分別定義 low 和 high 用於儲存陣列第一個元素的下標和最後一個元素的下標，即 low=0，high=6。

2) 然後定義 key 用於存放基準數，理論上該基準數可以取序列中的任何一個數。此處就取陣列的第一個元素，即把 a[low] 賦給 key。

3) 然後 key 和 a[high] 比較，即 35 和 22 比較，35>22，則它們互換位置：

22  12  37  -58  54  76  35

4) 然後 low++==1，key 和 a[low] 比較，即 35 和 12 比較，12<35，則不用互換位置；繼續 low++==2，然後 key 和 a[low] 比較，即 35 和 37 比較，37>35，則它們互換位置：

22  12  35  -58  54  76  37

5) 然後 high--==5，key 和 a[high] 比較，即 35 和 76 比較，35<76，則不用互換位置；繼續 high--==4，然後 key 和 a[high] 比較，即 35 和 54 比較，35<54，則不用互換位置；繼續 high--==3，然後 key 和 a[high] 比較，即 35 和 -58 比較，35>–58，則它們互換位置：

22  12  -58  35  54  76  37

6) 然後 low++==3，此時 low==high，第一輪比較結束。從最後得到的序列可以看出，35 左邊的都比 35 小，35 右邊的都比 35 大。這樣就以 35 為中心，把原序列分成了左右兩個部分。接下來只需要分別對左右兩個部分分別重複上述操作就行了。

對於人類而言，這個過程確實比前面的排序演算法複雜。但對於計算機而言，這個過程卻沒那麼複雜。下面來寫一個程式:

# include <stdio.h>
void Swap(int *, int *);  //函數宣告, 交換兩個變數的值
void QuickSort(int *, int, int);  //函數宣告, 快速排序
int main(void)
{
    int i;  //迴圈變數
    int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
    QuickSort(a, 0, 20);  /*參照起來很簡單, 0為第一個元素的下標, 20為最後一個元素的下標*/
    printf("最終排序結果為:n");
    for (i=0; i<21; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("n");
    return 0;
}
void Swap(int *p, int *q)
{
    int buf;
    buf = *p;
    *p = *q;
    *q = buf;
    return;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high)  //如果low >= high說明排序結束了
    {
        return ;
    }
    while (low < high)  //該while迴圈結束一次表示比較了一輪
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前尋找
        }
        if (key > a[high])
        {
            Swap(&a[low], &a[high]);
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向後尋找
        }
        if (key < a[low])
        {
            Swap(&a[low], &a[high]);
            --high;
        }
    }
    QuickSort(a, i, low-1);  //用同樣的方式對分出來的左邊的部分進行同上的做法
    QuickSort(a, low+1, j);  //用同樣的方式對分出來的右邊的部分進行同上的做法
}

輸出結果是：
最終排序結果為:
-234 -70 -58 1 2 3 4 5 7 8 9 32 34 43 56 76 532 543 635 900 2500

這個程式就是按上面講的過程寫的。實際上還可以對這個程式進行優化。在快速排序演算法中，每輪比較有且僅有一個 key 值，但是 key 值的位置是不斷變化的，只有比較完一輪後 key 值的位置才固定。上面這個程式中每次執行 swap 時實際上交換的是 key 和 a[low] 或 key 和 a[high]，而 key 的位置每次都是不一樣的。所以既然 key 的位置是“動來動去”的，所以就不必將它賦到陣列中了，等最後一輪比較結束後，它的位置“不動”了，再將它賦到陣列中。

比如，陣列 a 中元素為：3142。如果按從小到大排序，那麼 key=3，按上面這個程式就是 3 和 2 互換。2 賦給 a[0] 是必需的，但 key 就沒有必要賦給 a[3] 了。但你可以想象 key 是在 a[3] 這個位置，這個很重要。即此時序列變成 2142（key）。

然後 key 和 1 比較，不用換；key 和 4 比較，將 4 賦給 a[3]，然後想象 key 在 4 的位置，即此時序列變成 214（key）4。此時 key 左邊全是比 key 小的，key 的右邊全是比 key 大的。這時 key 的位置就固定了，再將它賦到陣列中，即 2134。

# include <stdio.h>
void QuickSort(int *, int, int);  /*現在只需要定義一個函數, 不用交換還省了一個函數, 減少了程式碼量*/
int main(void)
{
    int i;  //迴圈變數
    int a[] = {900, 2, -58, 3, 34, 5, 76, 7, 32, 4, 43, 9, 1, 56, 8,-70, 635, -234, 532, 543, 2500};
    QuickSort(a, 0, 20);  /*參照起來很簡單, 0為第一個元素的下標, 20為最後一個元素的下標*/
    printf("最終排序結果為:n");
    for (i=0; i<21; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("n");
    return 0;
}
void QuickSort(int *a, int low, int high)
{
    int i = low;
    int j = high;
    int key = a[low];
    if (low >= high)  //如果low >= high說明排序結束了
    {
        return ;
    }
    while (low < high)  //該while迴圈結束一次表示比較了一輪
    {
        while (low < high && key <= a[high])
        {
            --high;  //向前尋找
        }
        if (key > a[high])
        {
            a[low] = a[high];  //直接賦值, 不用交換
            ++low;
        }
        while (low < high && key >= a[low])
        {
            ++low;  //向後尋找
        }
        if (key < a[low])
        {
            a[high] = a[low];  //直接賦值, 不用交換
            --high;
        }
    }
    a[low] = key;  //查詢完一輪後key值歸位, 不用比較一次就互換一次。此時key值將序列分成左右兩部分
    QuickSort(a, i, low-1);  //用同樣的方式對分出來的左邊的部分進行同上的做法
    QuickSort(a, low+1, j);  //用同樣的方式對分出來的右邊的部分進行同上的做法
}

輸出結果是：
最終排序結果為:
-234 -70 -58 1 2 3 4 5 7 8 9 32 34 43 56 76 532 543 635 900 2500

總結

快速排序的基本思想是通過一趟快速排序，將要排序的資料分割成獨立的兩部分，其中一部分的所有資料比另外一部分的所有資料都要小，然後再按此方法遞回地對這兩部分資料分別進行快速排序。如此一直進行下去，直到排序完成。

快速排序實際上是氣泡排序的一種改進，是氣泡排序的升級版。這種改進就體現在根據分割序列的基準數，跨越式地進行交換。正是由於這種跨越式，使得元素每次移動的間距變大了，而不像氣泡排序那樣一格一格地“爬”。快速排序是一次跨多格，所以總的移動次數就比氣泡排序少很多。

但是快速排序也有一個問題，就是遞迴深度的問題。呼叫函數要消耗資源，遞回需要系統堆疊，所以遞回的空間消耗要比非遞回的空間消耗大很多。而且如果遞回太深的話會導致堆疊溢位，系統會“撐”不住。快速排序遞迴的深度取決於基準數的選擇，比如下面這個序列：

5  1  9  3  7  4  8  6  2

5 正好處於 1~9 的中間，選擇 5 作基準數可以平衡兩邊的遞迴深度。可如果是：

1  5  9  3  7  4  8  6  2

選擇 1 作為基準數，那麼遞迴深度就全部都加到右邊了。如果右邊有幾萬個數的話則系統直接就崩潰了。所以需要對遞迴深度進行優化。怎麼優化呢？就是任意取三個數，一般是取序列的第一個數、中間數和最後一個數，然後選擇這三個數中大小排在中間的那個數作為基準數，這樣起碼能確保獲取的基準數不是兩個極端。

前面講過，快速排序一般用於巨量資料排序，即資料的個數很多的時候（不是指數的值很大）。如果是小規模的排序，就用前面講的幾種簡單排序方式就行了，不必使用快速排序。

四種排序演算法的比較

氣泡排序是最慢的排序演算法。在實際運用中它是效率最低的演算法。它通過一趟又一趟地比較陣列中的每一個元素，使較大的資料下沉，較小的資料上升。

插入排序通過將序列中的值插入一個已經排好序的序列中，直到該序列結束。插入排序是對氣泡排序的改進。它比氣泡排序快兩倍。一般不用在資料的值大於 1000 的場合，或資料的個數超過 200 的序列。

選擇排序在實際應用中處於與氣泡排序基本相同的地位。它們只是排序演算法發展的初級階段，在實際中使用較少。但是它們最好理解。

快速排序是大規模遞回的演算法，它比大部分排序演算法都要快。一般用於資料個數比較多的情況。儘管可以在某些特殊的情況下寫出比快速排序快的演算法，但是就通常情況而言，沒有比它更快的了。快速排序是遞迴的，對於記憶體非常有限的機器來說，它不是一個好的選擇。

---