排序演算法 — 教材（含 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. 可編譯的整合範例

---

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

---

延伸閱讀

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

---

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