堆排序（Heap Sort）完整指南
| 維度 | 內容 |
|---|---|
| 核心思想 | 用數組模擬完全二叉堆，反覆彈出最大值（或最小值）完成排序 |
| 平均複雜度 | O(n log n) |
| 最壞複雜度 | O(n log n) （無退化） |
| 額外空間 | O(1) （原地） |
| 穩定性 | 否 （相等元素可能翻轉） |
| 實現難度 | ★★☆ （約 30 行代碼） |
1 堆基礎速覽
| 術語 | 解釋 |
|---|---|
| 最大堆 | 父節點 ≥ 子節點，根為全局最大 |
| 存儲方式 | 一維數組下標 i 的左右子分別為 2i+1 和 2i+2 |
| 高度 | h = floor(log2(n))，約 lg n 層 |
2 算法步驟（升序，最大堆）
-
建堆（heapify）：把無序數組原地變成最大堆
- 自底向上 sift-down，複雜度 O(n)
- 排序階段：
a. 交換堆頂a[0]與末尾a[i]
b. 堆大小-1
c. 對新堆頂 sift-down 恢復堆序
重複n-1次即得升序
3 代碼實現（C++17，整數模板）
#include <vector>
#include <algorithm>
template <class T>
inline void siftDown(T* a, int n, int root) {
while (true) {
int l = 2 * root + 1;
int r = l + 1;
int largest = root;
if (l < n && a[l] > a[largest]) largest = l;
if (r < n && a[r] > a[largest]) largest = r;
if (largest == root) break;
std::swap(a[root], a[largest]);
root = largest;
}
}
template <class T>
void heapSort(T* a, int n) {
// 1. 建最大堆
for (int i = n / 2 - 1; i >= 0; --i)
siftDown(a, n, i);
// 2. 依次提取最大元
for (int i = n - 1; i > 0; --i) {
std::swap(a[0], a[i]); // 當前最大沉底
siftDown(a, i, 0); // 恢復堆
}
}4 複雜度分析
| 階段 | 比較次數 | 説明 |
|---|---|---|
| 建堆 | ≤ 2n | 自底向上 sift-down |
| 排序 | n log n | 每次 sift-down 深度 ≤ log n |
| 總 | O(n log n) | 最壞、平均、最好一致 |
5 穩定性 & 順序敏感性
- 不穩定：交換堆頂與末尾時可能改變相等元素相對順序
- 若需穩定 → 改用 歸併排序 或記錄原始下標
6 常考優化
| 技巧 | 效果 |
|---|---|
| 循環展開 + 分支預測 | 提速 1015% |
| 三值取中（median-of-3） | 減小建堆常數 |
| 批量建堆 | std::make_heap 已集成 Floyd 算法 |
7 與其他 O(n log n) 算法對比
算法 | 額外空間 | 最壞 |穩定性| 特點
快速排序 | O(log n) | O(n²) 否 | 平均最快，但最壞退化
歸併排序 | O(n) | O(n log n) | ✅ 穩定，需緩衝區
堆排序 | O(1) | O(n log n) | 否 | 空間潔癖，無退化
8 應用場景
✅ 內存受限（嵌入式、單片機）
✅ 需要硬實時（最壞確定）
✅ 作為 內省排序 (std::sort) 的 fallback
❌ 對 穩定性 有要求
❌ 數據 近乎有序（此時插入更快）
9 一句話總結
堆排序 = 原地建堆 + 反覆彈出最大值；
保證 O(n log n) 最壞且 O(1) 空間，是“空間潔癖”與“硬實時”場景的首選。
