排序算法是程式設計的基石，也是面試必考題。本文以通俗易懂的方式，系統梳理冒泡、插入、歸並、快速、堆排序五大經典算法的核心邏輯、時間空間複雜度，並探討它們在實際工程中的適用場景。
核心隱喻：氣泡從湖底上浮，大的先浮出水面。
演算邏輯：雙重迴圈，相鄰元素兩兩比較，逆序則交換。每輪將當前最大值「冒泡」到末尾。
for i = 0 to n-2:
for j = 0 to n-i-2:
if a[j] > a[j+1]:
swap(a[j], a[j+1])
複雜度：時間 O(n²)，空間 O(1)，穩定排序。
核心隱喻：將無序區元素逐一插入已排序區的適當位置。
演算邏輯：外層遍歷無序區，內層從右向左掃描有序區，位移元素騰出空位。
for i = 1 to n-1:
key = a[i]
j = i-1
while j >= 0 and a[j] > key:
a[j+1] = a[j]
j--
a[j+1] = key
複雜度：時間 O(n²)，最佳 O(n)（近乎有序時），空間 O(1)，穩定排序。
核心隱喻：分而治之，先拆後合，哨兵簡化合併邏輯。
演算邏輯：遞歸拆分至單元素，再雙指標合併兩有序子陣列。
MergeSort(a, l, r):
if l < r:
m = (l+r)/2
MergeSort(a, l, m)
MergeSort(a, m+1, r)
Merge(a, l, m, r)
複雜度：時間 O(n log n)，空間 O(n)（需輔助陣列），穩定排序。
核心隱喻：以基準值分區，左小右大，遞歸征服。
演算邏輯：Partition 將基準值歸位，返回索引；遞歸處理左右子區。
Partition(a, l, r):
pivot = a[l]
i = l
for j = l+1 to r:
if a[j] < pivot:
i++; swap(a[i], a[j])
swap(a[l], a[i])
return i
複雜度：平均 O(n log n)，最壞 O(n²)（有序序列），空間 O(log n)（遞歸棧），不穩定。
核心隱喻：完全二叉樹性質，堆頂恆為極值，原地排序無需遞歸。
演算邏輯：建最大堆 → 交換堆頂與末尾 → 縮小堆範圍 → 下沉調整 → 重複。
HeapSort(a, n):
BuildMaxHeap(a, n)
for i = n-1 downto 1:
swap(a[0], a[i])
Heapify(a, 0, i)
複雜度：時間 O(n log n)，空間 O(1)，不穩定，無遞歸棧溢位風險。
| 場景 | 推薦算法 | 理由 |
|---|---|---|
| 小規模/近乎有序 | 插入排序 | 最佳 O(n)，代碼簡潔 |
| 通用高效排序 | 快速排序 | 平均效能最優，快取友好 |
| 需穩定/外部排序 | 歸並排序 | 穩定 O(n log n)，易並行化 |
| 海量數據/嵌入式 | 堆排序 | O(1) 空間，無遞歸風險 |
| 教學/極小數據 | 冒泡排序 | 邏輯最直觀，利於理解 |
qsort/std::sort 通常採用「快排+插入排序+三數取中」混合策略Arrays.sort 對物件用歸並（TimSort），基本型別用雙軸快排理解排序算法的本質權衡——時間、空間、穩定性、快取行為、遞歸深度——才能在實際專案中做出最優技術決策。
