排序演算法 — 教材（含 C++ 範例）

---

目錄

1. 總覽與比較
2. 氣泡排序（Bubble Sort）
3. 選擇排序（Selection Sort）
4. 插入排序（Insertion Sort）
5. 希爾排序（Shell Sort）
6. 合併排序（Merge Sort）
7. 快速排序（Quick Sort）
8. 堆積排序（Heap Sort）
9. 計數排序（Counting Sort）
10. 基底排序（Radix Sort）
11. 可編譯的整合範例
12. 穩定性：用一筆資料看懂
13. 比較排序的下界
14. 桶排序（Bucket Sort）
15. 怎麼選一個排序

---

1. 總覽與比較

排序問題： 給定長度為 (n) 的序列，將元素依鍵值（通常為數值）遞增（或遞減）排列。

演算法	平均時間	最壞時間	額外空間	穩定？	備註
氣泡排序	(O(n^2))	(O(n^2))	(O(1))	是	教學用，實務少用
選擇排序	(O(n^2))	(O(n^2))	(O(1))	否	交換次數少
插入排序	(O(n^2))	(O(n^2))	(O(1))	是	近乎有序時很快
希爾排序	視間隙而定	(O(n^{1.5}))～(O(n^2))	(O(1))	否	插入排序的改良
合併排序	(O(n \log n))	(O(n \log n))	(O(n))	是	可保證 (n\log n)
快速排序	(O(n \log n))	(O(n^2))	(O(\log n)) 遞迴棧	否*	實務常見（*原地版可改穩定但少用）
堆積排序	(O(n \log n))	(O(n \log n))	(O(1))	否	原地、無遞迴深度問題
計數排序	(O(n+k))	(O(n+k))	(O(k))	是	(k) 為值域大小
基底排序	(O(d(n+r)))	(O(d(n+r)))	(O(n+r))	是	(d) 位數、(r) 進位

穩定排序： 相等鍵值的元素，排序後相對順序與輸入相同。

---

2. 氣泡排序（Bubble Sort）

想法： 反覆走訪序列，若相鄰兩元素順序錯誤就交換；每一輪會把目前最大（或最小）「冒」到一端。若某一輪沒有任何交換，可提前結束。

性質： 實作簡單；大型資料效率差。

#include <vector>
#include <algorithm>

void bubble_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

---

3. 選擇排序（Selection Sort）

想法： 每一輪在未排序區間找出最小（或最大）元素的索引，與區間開頭交換。

性質： 交換次數至多 (O(n))，但比較次數仍為 (\Theta(n^2))。

#include <vector>
#include <algorithm>

void selection_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[min_idx]) min_idx = j;
        if (min_idx != i) std::swap(a[i], a[min_idx]);
    }
}

---

4. 插入排序（Insertion Sort）

想法： 維護左側已排序、右側未排序；每次將下一個元素向左插入到正確位置（可透過向後挪動完成）。

性質： 資料量小或近乎有序時表現佳；線上（online）演算法。

#include <vector>

void insertion_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

---

5. 希爾排序（Shell Sort）

想法： 以遞減的「間隙 gap」對多個子序列做插入排序，最後 gap=1 等同完整插入排序。間隙序列可選 Sedgewick、Knuth 等。

性質： 比 (O(n^2)) 的簡單排序快，實作仍簡單；複雜度分析依間隙序列而異。

#include <vector>

void shell_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    // 簡單 gap 序列：n/2, n/4, ... , 1
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
    }
}

---

6. 合併排序（Merge Sort）

想法： 分治：將序列二分，遞迴排序兩半，再將兩個有序區間合併成一個有序區間。

性質： 時間穩定 (O(n \log n))，需 (O(n)) 額外空間；穩定排序。

#include <vector>

static void merge(std::vector<int>& a, int left, int mid, int right, std::vector<int>& buf) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
        buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) buf[k++] = a[i++];
    while (j <= right) buf[k++] = a[j++];
    for (int t = 0; t < k; ++t) a[left + t] = buf[t];
}

static void merge_sort_rec(std::vector<int>& a, int left, int right, std::vector<int>& buf) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    merge_sort_rec(a, left, mid, buf);
    merge_sort_rec(a, mid + 1, right, buf);
    merge(a, left, mid, right, buf);
}

void merge_sort(std::vector<int>& a) {
    if (a.size() <= 1) return;
    std::vector<int> buf(a.size());
    merge_sort_rec(a, 0, static_cast<int>(a.size()) - 1, buf);
}

---

7. 快速排序（Quick Sort）

想法： 選一個 pivot，將小於 pivot 的放左邊、大於的放右邊，再遞迴處理兩側。此處示範 Lomuto 分割（實作短）。

性質： 平均 (O(n \log n))，最壞 (O(n^2))（已排序且選法不佳）；可隨機選 pivot 降低最壞機率。

#include <vector>
#include <algorithm>

static int partition_lomuto(std::vector<int>& a, int low, int high) {
    int pivot = a[high];
    int i = low;
    for (int j = low; j < high; ++j) {
        if (a[j] <= pivot) {
            std::swap(a[i], a[j]);
            ++i;
        }
    }
    std::swap(a[i], a[high]);
    return i;
}

static void quick_sort_rec(std::vector<int>& a, int low, int high) {
    if (low >= high) return;
    int p = partition_lomuto(a, low, high);
    quick_sort_rec(a, low, p - 1);
    quick_sort_rec(a, p + 1, high);
}

void quick_sort(std::vector<int>& a) {
    if (a.size() <= 1) return;
    quick_sort_rec(a, 0, static_cast<int>(a.size()) - 1);
}

---

8. 堆積排序（Heap Sort）

想法： 將陣列視為二元堆（此處用最大堆），反覆取出堆頂（最大值）放到陣列尾端並調整堆。

性質： 原地、(O(n \log n)) 最壞情況；不穩定。

#include <vector>
#include <algorithm>

static void sift_down(std::vector<int>& a, int n, int i) {
    while (true) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

void heap_sort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n <= 1) return;
    for (int i = n / 2 - 1; i >= 0; --i)
        sift_down(a, n, i);
    for (int end = n - 1; end > 0; --end) {
        std::swap(a[0], a[end]);
        sift_down(a, end, 0);
    }
}

---

9. 計數排序（Counting Sort）

想法： 假設鍵值範圍在 ([0, k])（或已知最小值可平移）。統計每個值出現次數，再依計數還原有序序列。

性質： (O(n+k)) 時間與 (O(k)) 空間；僅適合範圍不大的整數（或可映射為整數的鍵）。

#include <vector>
#include <algorithm>

void counting_sort(std::vector<int>& a, int min_val, int max_val) {
    if (a.empty()) return;
    const int k = max_val - min_val + 1;
    std::vector<int> cnt(k, 0);
    for (int x : a) ++cnt[x - min_val];
    int idx = 0;
    for (int v = 0; v < k; ++v)
        while (cnt[v]-- > 0) a[idx++] = v + min_val;
}

---

10. 基底排序（Radix Sort）

想法： 從最低位（LSD）或最高位（MSD）開始，對每一位用穩定的子排序（常用計數排序，進位為 (r)）。

性質： 對 (d) 位、進位 (r)，LSD 搭配計數排序約為 (O(d(n+r))) 時間與 (O(n+r)) 額外空間。

#include <vector>

static void counting_sort_digit(std::vector<int>& a, int exp, int radix) {
    const int n = static_cast<int>(a.size());
    std::vector<int> output(n);
    std::vector<int> cnt(radix, 0);
    for (int x : a) {
        int digit = (x / exp) % radix;
        ++cnt[digit];
    }
    for (int i = 1; i < radix; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        int digit = (a[i] / exp) % radix;
        output[--cnt[digit]] = a[i];
    }
    a.swap(output);
}

// 非負整數；若含負數需先平移或改用符號位處理
void radix_sort_lsd(std::vector<int>& a, int radix = 10) {
    if (a.empty()) return;
    int mx = *std::max_element(a.begin(), a.end());
    for (int exp = 1; mx / exp > 0; exp *= radix)
        counting_sort_digit(a, exp, radix);
}

---

11. 可編譯的整合範例

下列為單一檔案完整程式：存成 sort_demo.cpp 後可直接編譯執行，內容與第 2～10 節演算法一致。

// sort_demo.cpp — 排序演算法整合示範（C++17）
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

void bubble_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i) {
        bool swapped = false;
        for (int j = 0; j < n - 1 - i; ++j) {
            if (a[j] > a[j + 1]) {
                std::swap(a[j], a[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

void selection_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[min_idx]) min_idx = j;
        if (min_idx != i) std::swap(a[i], a[min_idx]);
    }
}

void insertion_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int i = 1; i < n; ++i) {
        int key = a[i];
        int j = i - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            --j;
        }
        a[j + 1] = key;
    }
}

void shell_sort(std::vector<int>& a) {
    const int n = static_cast<int>(a.size());
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = a[i];
            int j = i;
            while (j >= gap && a[j - gap] > temp) {
                a[j] = a[j - gap];
                j -= gap;
            }
            a[j] = temp;
        }
    }
}

static void merge(std::vector<int>& a, int left, int mid, int right, std::vector<int>& buf) {
    int i = left, j = mid + 1, k = 0;
    while (i <= mid && j <= right)
        buf[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid) buf[k++] = a[i++];
    while (j <= right) buf[k++] = a[j++];
    for (int t = 0; t < k; ++t) a[left + t] = buf[t];
}

static void merge_sort_rec(std::vector<int>& a, int left, int right, std::vector<int>& buf) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    merge_sort_rec(a, left, mid, buf);
    merge_sort_rec(a, mid + 1, right, buf);
    merge(a, left, mid, right, buf);
}

void merge_sort(std::vector<int>& a) {
    if (a.size() <= 1) return;
    std::vector<int> buf(a.size());
    merge_sort_rec(a, 0, static_cast<int>(a.size()) - 1, buf);
}

static int partition_lomuto(std::vector<int>& a, int low, int high) {
    int pivot = a[high];
    int i = low;
    for (int j = low; j < high; ++j) {
        if (a[j] <= pivot) {
            std::swap(a[i], a[j]);
            ++i;
        }
    }
    std::swap(a[i], a[high]);
    return i;
}

static void quick_sort_rec(std::vector<int>& a, int low, int high) {
    if (low >= high) return;
    int p = partition_lomuto(a, low, high);
    quick_sort_rec(a, low, p - 1);
    quick_sort_rec(a, p + 1, high);
}

void quick_sort(std::vector<int>& a) {
    if (a.size() <= 1) return;
    quick_sort_rec(a, 0, static_cast<int>(a.size()) - 1);
}

static void sift_down(std::vector<int>& a, int n, int i) {
    while (true) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && a[l] > a[largest]) largest = l;
        if (r < n && a[r] > a[largest]) largest = r;
        if (largest == i) break;
        std::swap(a[i], a[largest]);
        i = largest;
    }
}

void heap_sort(std::vector<int>& a) {
    int n = static_cast<int>(a.size());
    if (n <= 1) return;
    for (int i = n / 2 - 1; i >= 0; --i)
        sift_down(a, n, i);
    for (int end = n - 1; end > 0; --end) {
        std::swap(a[0], a[end]);
        sift_down(a, end, 0);
    }
}

void counting_sort(std::vector<int>& a, int min_val, int max_val) {
    if (a.empty()) return;
    const int k = max_val - min_val + 1;
    std::vector<int> cnt(k, 0);
    for (int x : a) ++cnt[x - min_val];
    int idx = 0;
    for (int v = 0; v < k; ++v)
        while (cnt[v]-- > 0) a[idx++] = v + min_val;
}

static void counting_sort_digit(std::vector<int>& a, int exp, int radix) {
    const int n = static_cast<int>(a.size());
    std::vector<int> output(n);
    std::vector<int> cnt(radix, 0);
    for (int x : a) {
        int digit = (x / exp) % radix;
        ++cnt[digit];
    }
    for (int i = 1; i < radix; ++i) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        int digit = (a[i] / exp) % radix;
        output[--cnt[digit]] = a[i];
    }
    a.swap(output);
}

void radix_sort_lsd(std::vector<int>& a, int radix = 10) {
    if (a.empty()) return;
    int mx = *std::max_element(a.begin(), a.end());
    for (int exp = 1; mx / exp > 0; exp *= radix)
        counting_sort_digit(a, exp, radix);
}

static void print(const std::string& name, const std::vector<int>& a) {
    std::cout << name << ": ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    std::vector<int> original = {5, 2, 8, 1, 9, 3, 7, 4, 6};

    auto run = [&](const char* name, auto sort_fn) {
        std::vector<int> v = original;
        sort_fn(v);
        print(name, v);
    };

    run("bubble_sort", [](std::vector<int>& v) { bubble_sort(v); });
    run("selection_sort", [](std::vector<int>& v) { selection_sort(v); });
    run("insertion_sort", [](std::vector<int>& v) { insertion_sort(v); });
    run("shell_sort", [](std::vector<int>& v) { shell_sort(v); });
    run("merge_sort", [](std::vector<int>& v) { merge_sort(v); });
    run("quick_sort", [](std::vector<int>& v) { quick_sort(v); });
    run("heap_sort", [](std::vector<int>& v) { heap_sort(v); });

    std::vector<int> c = {2, 5, 3, 0, 2, 3, 0, 3};
    counting_sort(c, 0, 5);
    print("counting_sort [0..5]", c);

    std::vector<int> r = {170, 45, 75, 90, 2, 802, 24, 66};
    radix_sort_lsd(r, 10);
    print("radix_sort_lsd", r);

    return 0;
}

編譯範例（C++17）：

g++ -std=c++17 -O2 -Wall -Wextra -o sort_demo sort_demo.cpp
./sort_demo

---

12. 穩定性：用一筆資料看懂

排序鍵相同時，穩定排序保留它們在輸入裡的相對順序。多鍵排序依賴這件事：先排次要鍵，再穩定地排主要鍵，次要鍵的順序才不會被打亂。

輸入（姓名, 分數），先依分數升序：

輸入順序	姓名	分數
1	Ann	80
2	Bo	90
3	Cy	80

穩定排序後：Ann 仍在 Cy 前面，因為兩人分數同為 80，而 Ann 原本在前。結果是 (Ann,80), (Cy,80), (Bo,90)。

選擇排序可能先把 Bo 和某個位置交換時打亂相等鍵；堆積排序的下沉也不看原始位置。所以這兩個不能當多鍵排序的第二步，除非另外把原始索引放進比較鍵。

計數排序與基底排序是穩定的，前提是實作把相同鍵依出現順序寫回（由後往前填桶，或等價的前綴和寫法）。若改成由前往後填，穩定性會消失，LSD 基底排序就會算錯。

---

13. 比較排序的下界

比較排序只能透過「(a_i < a_j)？」來決定順序。任何這類演算法都可以畫成一棵二元決策樹：每個內部節點是一次比較，每片葉子是一種排列。

(n) 個相異元素有 (n!) 種可能的輸入順序，所以樹至少要有 (n!) 片葉子。高度為 (h) 的二元樹最多 (2^h) 片葉子，因此

[ 2^h \ge n! \implies h \ge \log_2(n!) = \Omega(n\log n) ]

合併排序與堆積排序達到 (O(n\log n))，在比較模型裡已經最佳。這個下界管不到計數排序、基底排序、桶排序，因為它們不是只靠兩兩比較，而是用鍵的數值範圍或位數。鍵是任意實數、只能比較時，不要指望線性時間。

---

14. 桶排序（Bucket Sort）

適用於鍵大致均勻分布在一個區間，例如 ([0,1)) 上的隨機實數。

1. 準備 (n) 個桶，把 (x) 放進桶 (\lfloor n \cdot x \rfloor)。
2. 每個桶用插入排序（桶很短，插入排序的常數小）。
3. 依桶的順序接起來。

均勻分布時，每個桶的期望長度是常數，插入排序的期望成本是常數，總期望時間 (O(n))。分布若全部擠在同一個桶，就退回 (O(n^2))。它不是最壞線性，和計數排序的保證不同。

整數且值域是 (0..k) 時，直接用計數排序，不必再分桶。

---

15. 怎麼選一個排序

情況	選擇
一般物件、要最壞 (O(n\log n))、可不穩定	堆積排序，或實務上的 IntroSort（std::sort）
必須穩定，或要做多鍵排序	合併排序（std::stable_sort）
幾乎已排序的短序列	插入排序
整數、值域 (k = O(n))	計數排序
非負整數、位數 (d) 小	LSD 基底排序（底層用穩定的計數排序）
([0,1)) 上大致均勻	桶排序
資料放不進記憶體	外部多路合併（見堆積教材的多路合併）
只要第 (k) 小，不必全排序	見 Order_Statistics_Quickselect_Teaching_Materials.md

比較次數已經 (\Omega(n\log n)) 的時候，繼續微調氣泡排序沒有漸近意義。

---

延伸閱讀

• std::sort：通常為 IntroSort（快速排序 + 堆積排序 + 插入排序），最壞時間 (O(n \log n))。
• std::stable_sort：通常為合併排序類型，穩定且 (O(n \log n))（可能額外線性空間）。
• 外部排序（資料無法一次載入記憶體時）多採多路合併與磁碟區塊讀寫優化。

---

本教材與專案內其他 *_Teaching_Materials.md 風格一致，供課堂與自修對照程式使用。