以 n 代表資料筆數，選擇、插入、氣泡排序在最壞情況下，比較次數都會隨資料筆數呈平方成長，因此時間是 O(n²)。

換個方式想：老師要全班依身高排隊，可以先請一位同學當「基準」，比他矮的站左邊，比他高的站右邊。基準同學的位置就確定了，左右兩群之間也不用再互相比較。接著兩群各自再請一位同學當基準，照樣分下去，分到每群只剩一個人，全班就排好了。

這就是**快速排序（quick sort）**的做法。範例沿用前一天的 8 筆資料：

26  59  1  61  5  15  11  37

分而治之

快速排序是**分而治之（divide and conquer）**的例子：把大問題拆成同類型的小問題，分別解決後再組合起來。小問題的解法和大問題一樣，很適合用遞迴來寫。套到快速排序上：

1. 分割：挑一筆資料當基準（pivot），把不比它大的資料搬到左邊、比它大的搬到右邊，基準放在兩群中間。
2. 遞迴：左邊那段、右邊那段，各自再做一次快速排序。
3. 組合：不用做任何事。左段都不比基準大、右段都比基準大，兩段各自排好，整段就排好了。

分割：讓基準歸位

分割的寫法有好幾種，這裡以最左邊的資料當基準，再用兩個索引 i、j 從兩頭往中間找：

1. i 從基準的下一格往右找，停在第一筆比基準大的資料。
2. j 從最右邊往左找，停在第一筆不比基準大的資料。
3. 如果 i 還在 j 的左邊，表示兩筆都站錯邊，交換後回到步驟 1。
4. 如果 i 已經跑到 j 的右邊（兩人交錯），掃描結束，把基準和 j 所指的資料交換。

以整段 8 筆資料為例，基準是 26（橘色），粗框是要交換的兩筆：

1. i 停在 59，j 停在 11，交換。
2. i 停在 61，j 停在 15，交換。
3. i 往右停在剛換過去的 61，j 往左停在 5，兩人交錯，基準 26 和 5 交換。
4. 26 到達最終位置（灰色），之後不會再移動。

為什麼和 j 交換？掃描結束時，j 停在「不比基準大」那一群的最後一筆，基準換到這裡，就剛好站在兩群中間。

遞迴：左右兩段各自照做

接著對左段 [0..3]（索引 0 到 3）和右段 [5..7] 各自做快速排序；一段只剩 0 或 1 筆時本身就排好了，直接結束，這是遞迴的終止條件。完整過程如下（先左段、後右段）：

基準剛好是該段的最小值或最大值時（第 3～5 次），分割後會有一邊是空的。最後得到 1 5 11 15 26 37 59 61。

用 C 語言實作

#include <stdio.h>

#define SIZE 8

void printRange(const int data[], int left, int right) {
    for (int i = left; i <= right; i++) {
        printf("%d ", data[i]);
    }
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* 以 data[left] 為基準分割，回傳基準最後所在的索引 */
int partition(int data[], int left, int right) {
    int pivot = data[left];
    int i = left + 1;
    int j = right;

    while (1) {
        while (i <= right && data[i] <= pivot) {
            i++; /* i 往右找比基準大的 */
        }
        while (data[j] > pivot) {
            j--; /* j 往左找不比基準大的 */
        }
        if (i >= j) {
            break; /* 兩人相遇或交錯，這一次分割的掃描結束 */
        }
        swap(&data[i], &data[j]);
    }
    swap(&data[left], &data[j]); /* 基準放到 j，左邊都不比它大，右邊都比它大 */
    return j;
}

void quickSort(int data[], int left, int right) {
    if (left >= right) {
        return; /* 0 或 1 筆資料，不用排 */
    }

    printf("分割 [%d..%d]，基準 %2d：", left, right, data[left]);
    int pivotIndex = partition(data, left, right);
    printRange(data, left, pivotIndex - 1);
    printf("| %d | ", data[pivotIndex]);
    printRange(data, pivotIndex + 1, right);
    printf("\n");

    quickSort(data, left, pivotIndex - 1);
    quickSort(data, pivotIndex + 1, right);
}

int main(void) {
    int data[SIZE] = {26, 59, 1, 61, 5, 15, 11, 37};

    quickSort(data, 0, SIZE - 1);

    printf("排序結果：");
    printRange(data, 0, SIZE - 1);
    printf("\n");
    return 0;
}

執行結果和前面的表格一致：

分割 [0..7]，基準 26：5 11 1 15 | 26 | 61 59 37
分割 [0..3]，基準  5：1 | 5 | 11 15
分割 [2..3]，基準 11：| 11 | 15
分割 [5..7]，基準 61：37 59 | 61 |
分割 [5..6]，基準 37：| 37 | 59
排序結果：1 5 11 15 26 37 59 61

兩個迴圈的邊界要注意：

• i 的迴圈要檢查 i <= right。基準是最大值時（像第 4 次的 61），i 找不到比它大的資料，沒有這個檢查就會跑出陣列範圍。
• j 的迴圈不需要檢查。j 最多走到 left，而 data[left] 就是基準本身，一定會在那裡停下來。

時間：看分割得平不平均

快速排序快不快，取決於每次分割得平不平均。下圖用顏色標出每一層的基準：左邊是範例資料，右邊是已經由小到大排好的同一組數字。

每一層的工作量大約是 O(n)：同一層的各段加起來最多 n 筆，分割時 i、j 會掃過整段。

• 最好的情況：每次基準都落在正中間，段長每層減半，大約 log₂ n 層就切到只剩 1 筆，總時間 O(n log n)。
• 最壞的情況：每次基準都是該段的最小值或最大值，每層只少基準一筆，處理量是 n、n − 1、n − 2……，加總為 O(n²)。
• 平均的情況：假設鍵值互不相同，而且每種排列出現的機會都一樣，平均時間是 O(n log n)。

以最左邊當基準時，資料已經排好或完全相反反而最慢。這就像把排好序的資料依序插入二元搜尋樹，樹會長成一條鏈。

這個分割版本遇到全部相同的數字時，也會每次只排除一筆基準，退化成 O(n²)。

空間與穩定性

快速排序直接在原陣列上交換，額外空間來自遞迴：遞迴的深度就是分割的層數，平衡時約 log₂ n 層，最壞時接近 n 層。在鍵值互異、排列隨機的假設下，平均深度是 O(log n)，所以額外空間平均 O(log n)、最壞 O(n)。

快速排序也不穩定，也就是鍵值相同的資料，排序後不一定保持原本的先後順序。原因是分割時會把資料跨過一大段交換。例如「紅 5、黑 5、1」：以紅 5 為基準，i 找不到比 5 大的資料，j 停在 1，紅 5 和 1 交換，得到「1、黑 5、紅 5」，兩個 5 的順序就反過來了。

和前面的排序方法比較

n = 1 萬時，n² 是 1 億，n log₂ n 只有約 13 萬。快速排序的最壞情況雖然也是 O(n²)，但平均表現好很多，因此被廣泛使用。

小結

快速排序先用基準把資料分成兩邊，再讓左右兩段各自照做。快慢取決於分割是否平衡：平均時間是 O(n log n)，分割一直偏向一邊時則退化成 O(n²)。額外空間來自遞迴，而遠距離交換讓它不穩定。

今日重點：

• 分而治之：把大問題拆成同類型的小問題，分別解決後再組合。
• 分割後，基準左邊都不比它大、右邊都比它大，基準從此不再移動。
• 這裡的分割法：i 往右找比基準大的、j 往左找不比基準大的，i 在 j 左邊就交換，交錯後基準和 j 交換。
• 平均時間 O(n log n)；以最左邊當基準時，排好序的資料會讓每次分割都偏向一邊，退化成 O(n²)。
• 額外空間來自遞迴，平均 O(log n)、最壞 O(n)；快速排序不穩定。

快速排序是先費心分好兩邊，再各自遞迴；下一篇的合併排序正好反過來：不管三七二十一先從中間切成兩半，等兩半各自排好，再像拉拉鍊一樣合併起來。它完全不怕已經排好的資料，最壞情況也只要 O(n log n)，那它的代價又是什麼？