C++ 排序算法模板庫：插入/冒泡/選擇/歸並/快速排序完整實現與證明

模板設計規範

• 函數模板 template <typename T> 支持任意可比較類型。
• 參數：T* array 原始指針 + size_t length，兼容數組與 vector.data()。
• 原地排序，返回 void；歸並排序需外部臨時數組 T* temp。

1. 插入排序 — 近乎有序數組的王者

template <typename T>
void insertionSort(T* a, size_t n) {
    for (size_t i = 1; i < n; ++i) {
        T key = a[i];
        size_t j = i;
        while (j > 0 && a[j-1] > key) {
            a[j] = a[j-1];
            --j;
        }
        a[j] = key;
    }
}

循環不變式：a[0..i-1] 已排序。
最優 O(N)（已有序），最差 O(N²)（逆序）。
穩定、原地。適合小規模（N≤50）或近乎有序數組。

2. 冒泡排序 — 教學用，實戰棄用

template <typename T>
void bubbleSort(T* a, size_t n) {
    for (size_t i = 0; i + 1 < n; ++i)
        for (size_t j = 0; j + i + 1 < n; ++j)
            if (a[j] > a[j+1]) swap(a[j], a[j+1]);
}

雙重循環不變式證明。最優/最差均 O(N²)，即使加 swapped 標誌優化最優至 O(N)，常數因子仍大於插入排序。唯一優勢：代碼最短，適合考試手寫。

3. 選擇排序 — 不穩定，但交換次數最少 O(N)

template <typename T>
void selectionSort(T* a, size_t n) {
    for (size_t i = 0; i < n; ++i) {
        size_t minIdx = i;
        for (size_t j = i+1; j < n; ++j)
            if (a[j] < a[minIdx]) minIdx = j;
        swap(a[i], a[minIdx]);
    }
}

不穩定（交換可能改變相等元素相對序）。
交換次數固定 N-1，適合寫入成本極高（如 Flash 存儲）場景。

4. 歸並排序 — 穩定 O(N log N) 基準

template <typename T>
void merge(T* src, T* tmp, int l, int m, int r) {
    int i = l, j = m+1, k = l;
    while (i <= m && j <= r)
        tmp[k++] = (src[i] <= src[j]) ? src[i++] : src[j++];
    while (i <= m) tmp[k++] = src[i++];
    while (j <= r) tmp[k++] = src[j++];
    copy(tmp+l, tmp+r+1, src+l);
}

template <typename T>
void mergeSort(T* src, T* tmp, int l, int r) {
    if (l < r) {
        int m = (l + r) >> 1;
        mergeSort(src, tmp, l, m);
        mergeSort(src, tmp, m+1, r);
        merge(src, tmp, l, m, r);
    }
}

遞歸式：T(n) = 2T(n/2) + O(n) → O(n log n)（主定理）。
穩定、外部排序基礎。缺點：需 O(N) 輔助空間。

5. 快速排序 — 實戰最快，平均 O(N log N)

template <typename T>
void quickSort(T* a, int l, int r) {
    if (l >= r) return;
    int i = l, j = r;
    T pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot) --j;
        a[i] = a[j];
        while (i < j && a[i] <= pivot) ++i;
        a[j] = a[i];
    }
    a[i] = pivot;
    quickSort(a, l, i-1);
    quickSort(a, i+1, r);
}

關鍵優化：
① 三數取中法選主元 → 避免有序數組退化。
② 小區間（<16）切換插入排序。
③ 尾遞歸消除 / 手動棧模擬 → 防棧溢出。
不穩定，但緩存局部性極好，實際運行速度通常最快。

鏈表歸並排序（額外補充）

// 快慢指針找中點 + 遞歸排序 + 合併兩有序鏈表
ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* mid = slow->next; slow->next = nullptr;
    return merge(sortList(head), sortList(mid));
}

鏈表合併無需額外空間，真正 O(1) 空間 O(N log N) 排序。

算法選擇決策樹

N ≤ 50          → Insertion Sort
需穩定 + O(NlogN) → Merge Sort / std::stable_sort
通用高性能       → Quick Sort (三數取中+小區間優化) / std::sort
空間極受限       → Heap Sort / 鏈表 Merge Sort
近乎有序         → Insertion Sort / Timsort (Python/Java 默認)