算法清單與複雜度速查
| 算法 | 平均時間 | 最壞時間 | 空間 | 穩定性 | 備註 |
|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 穩定 | 教學用，實戰少用 |
| 簡單選擇排序 | O(n²) | O(n²) | O(1) | 不穩定 | 交換次數少 |
| 直接插入排序 | O(n²) | O(n²) | O(1) | 穩定 | 近乎有序時極快 |
| 希爾排序 | O(n^1.3~2) | O(n²) | O(1) | 不穩定 | 分組插入，增量序列影響大 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不穩定 | 原地、最壞情況有保證 |
| 歸並排序 | O(n log n) | O(n log n) | O(n) | 穩定 | 外部排序基石 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不穩定 | 實際最快，三數取中優化 |
核心代碼片段（關鍵邏輯）
1. 冒泡排序（優化版）
void BubbleSort(int* a, int n) {
for (int i = 0; i < n-1; ++i) {
bool swapped = false;
for (int j = n-2; j >= i; --j)
if (a[j] > a[j+1]) { swap(a[j], a[j+1]); swapped = true; }
if (!swapped) break; // 提前終止
}
}
2. 快速排序（三數取中 + 雙向掃描）
int Partition(int* a, int low, int high) {
int mid = (low + high) / 2;
// 三數取中，將中位數換到 low
if (a[low] > a[high]) swap(a[low], a[high]);
if (a[mid] > a[high]) swap(a[mid], a[high]);
if (a[low] < a[mid]) swap(a[low], a[mid]);
int pivot = a[low];
while (low < high) {
while (low < high && a[high] > pivot) --high;
a[low] = a[high];
while (low < high && a[low] < pivot) ++low;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
void QuickSort(int* a, int low, int high) {
if (low < high) {
int p = Partition(a, low, high);
QuickSort(a, low, p-1);
QuickSort(a, p+1, high);
}
}
3. 歸並排序（遞歸 + 迭代雙版本）
// 遞歸版
void Merge(int* a, int l, int m, int r) {
vector<int> tmp(r-l+1);
int i=l, j=m+1, k=0;
while (i<=m && j<=r) tmp[k++] = (a[i]<a[j]) ? a[i++] : a[j++];
while (i<=m) tmp[k++] = a[i++];
while (j<=r) tmp[k++] = a[j++];
copy(tmp.begin(), tmp.end(), a+l);
}
void MergeSort(int* a, int l, int r) {
if (l >= r) return;
int m = (l+r)/2;
MergeSort(a, l, m);
MergeSort(a, m+1, r);
Merge(a, l, m, r);
}
// 非遞歸版（自底向上）
void MergePass(int* a, int k, int n) { /* 間隔 k 歸並 */ }
void MergeSortIter(int* a, int n) {
for (int k=1; k<n; k*=2) MergePass(a, k, n);
}
4. 堆排序（最大堆）
void AdjustHeap(int* a, int s, int m) {
int tmp = a[s];
for (int i=2*s+1; i<=m; i=2*i+1) {
if (i<m && a[i]<a[i+1]) ++i;
if (tmp >= a[i]) break;
a[s] = a[i]; s = i;
}
a[s] = tmp;
}
void HeapSort(int* a, int n) {
for (int i=(n-2)/2; i>=0; --i) AdjustHeap(a, i, n-1); // 建堆
for (int i=n-1; i>0; --i) { swap(a[0], a[i]); AdjustHeap(a, 0, i-1); }
}
工程選型建議
- 小規模/近乎有序：插入排序 O(n)。
- 通用高性能：快速排序（隨機化/三數取中）或
std::sort（Introsort 混合）。
- 需穩定/外部排序：歸並排序。
- 嵌入式/嚴格 O(1) 空間：堆排序。
- 教學/面試：掌握所有算法的分區、合併、堆調整核心邏輯。
