公務人員特種考試計算機大意112 年第 10 題單選題
如果鍵值相同之資料，在排序後相對位置與排序前相同時，則稱為穩定排序（stable sorting）法，下列何者不屬於穩定排序法？
A堆積排序法（Heap sort）正確答案
B氣泡排序法（Bubble sort）
C插入排序法（Insertion sort）
D合併排序法（Merge sort）
A正確答案
Heap sort 因建堆與交換過程會破壞相同鍵值的相對順序，屬於不穩定排序。
為什麼答案是 A
Heap sort 在 sift-down/swap 時會把後方元素交換到前面，造成相同鍵值的相對順序改變，為不穩定排序。
載入中…
完整詳解
Pro · 無限重點 Heap sort 因建堆與交換過程會破壞相同鍵值的相對順序，屬於不穩定排序。
1. 穩定排序定義：相同鍵值排序後相對位置不變。
2. 常見穩定：Bubble、Insertion、Merge、Counting、Radix。
3. 常見不穩定：Heap、Quick、Selection、Shell。
4. 本題四選項中僅 Heap sort 屬不穩定 → 答案 (A)。
逐選項分析
✓ 正確
Heap sort 在 sift-down/swap 時會把後方元素交換到前面，造成相同鍵值的相對順序改變，為不穩定排序。
✕
Bubble sort 僅在 a[i] > a[i+1] 時交換，相等不交換，屬穩定排序。
✕
Insertion sort 將元素插入到第一個大於它的位置之前，相等者保留原順序，屬穩定排序。
✕
Merge sort 在合併時遇到相等鍵值優先取左半段，可保持原序，屬穩定排序。
常見排序法穩定性與時間複雜度
| 排序法 | 穩定性 | 平均時間 |
|---|
| Bubble | 穩定 | \(O(n^2)\) |
| Insertion | 穩定 | \(O(n^2)\) |
| Merge | 穩定 | \(O(n\log n)\) |
| Heap | 不穩定 | \(O(n\log n)\) |
| Quick | 不穩定 | \(O(n\log n)\) |
| Selection | 不穩定 | \(O(n^2)\) |
易把『時間複雜度好』與『穩定』混為一談；Heap sort 雖為 \(O(n\log n)\) 但不穩定，Quick sort 同樣不穩定。 
