常見排序算法 C++ 實現與複雜度總結：快排、堆排、歸並、插入、冒泡

一、快速排序 — 分治法標杆

核心思想

選基準，分區：左邊 ≤ 基準，右邊 ≥ 基準；遞歸處理左右子區。

關鍵函數 partition

int partition(int head, int tail, int a[]) {
    int pivot = a[tail], i = head, j = tail;
    while (i < j) {
        while (i < j && a[i] <= pivot) ++i;
        while (i < j && a[j] >= pivot) --j;
        if (i < j) { swap(a[i], a[j]); ++i; --j; }
    }
    a[tail] = a[i]; a[i] = pivot;
    return i;
}

複雜度

• 平均 O(n log n)
• 最壞 O(n²)（有序數組 + 固定基準）
• 空間 O(log n) 遞歸棧
• 不穩定

優化

• 隨機基準 / 三數取中
• 小區間切換插入排序
• 尾遞歸消除 / 顯式棧迭代

二、堆排序 — 保證 O(n log n) 最壞情況

核心操作

• maxheapify：將節點下沉，維持最大堆性質。
• buildmaxheap：自底向上構建堆。

複雜度

• 時間 **恆定 O(n log n)**
• 空間 O(1) 原地排序
• 不穩定

三、歸並排序 — 穩定、外排基石

核心 merge

雙指針合併兩個有序子陣列，需 O(n) 輔助空間。

複雜度

• 時間 O(n log n) 恆定
• 空間 O(n)
• 穩定

四、插入排序 — 小規模/近乎有序首選

• 時間 O(n²)，最好 O(n)（已有序）
• 空間 O(1)
• 穩定、適應性強、常用作快排/歸並小區間優化

五、冒泡排序 — 教學用，實戰棄用

• 時間 O(n²)，空間 O(1)，穩定
• 優化：標志位提前終止、雞尾酒排序（雙向）

綜合對比表

工程建議

1. **首選標準庫** std::sort (Introsort: 快排+堆排+插入)、std::stable_sort (歸並)。
2. 自行實現時：隨機基準 + 三路分區 + 小區間插入排序 是快排工業級標配。
3. 鏈表排序用歸並（O(1) 空間合併）。
4. 外部排序（數據超內存）必用歸並多路合併。