地方政府公務人員四等-電子工程類科計算機概要108 年第 22 題單選題
下列何者排序演算法在最差情況下（worst case）的時間複雜度最佳？
A選擇排序（selection sort）
B快速排序（quick sort）
C堆積排序（heap sort）正確答案
D氣泡排序（bubble sort）
C正確答案
堆積排序在最差情況下時間複雜度為 O(n log n)，優於其他選項的 O(n²) 或退化風險。
為什麼答案是 C
堆積排序利用二元堆積樹結構，保證在任何輸入下，建堆積與排序階段皆為 O(n log n)，是四個選項中「最差情況」表現最佳者。
載入中…
完整詳解
Pro · 無限重點 堆積排序在最差情況下時間複雜度為 O(n log n)，優於其他選項的 O(n²) 或退化風險。
口訣「堆積穩贏」：Heap Sort 最差仍 O(n log n)；Quick Sort 最差會退化成 O(n²)。
逐選項分析
A✕
選擇排序無論最佳、平均或最差情況，皆需進行雙層迴圈比較與交換，時間複雜度固定為 O(n²)，效率較低。
B✕ 陷阱
快速排序平均表現優異 O(n log n)，但在最差情況（如已排序陣列且選錯基準點）會退化為 O(n²)，非本題所求之「最差最佳」。
C✓ 正確
堆積排序利用二元堆積樹結構，保證在任何輸入下，建堆積與排序階段皆為 O(n log n)，是四個選項中「最差情況」表現最佳者。
D✕
氣泡排序在最差與平均情況下均需 O(n²) 次比較與交換，僅在已排序時可達 O(n)，整體效率為四者中最差。
排序演算法時間複雜度對照
| 演算法 | 最佳 | 平均 | 最差 |
|---|
| 選擇排序 | O(n²) | O(n²) | O(n²) |
| 快速排序 | O(n log n) | O(n log n) | O(n²) |
| 堆積排序 | O(n log n) | O(n log n) | O(n log n) |
| 氣泡排序 | O(n) | O(n²) | O(n²) |
考生常誤認快速排序總是最快，但題目強調「最差情況」。Quick Sort 在特定輸入下會退化，唯有 Heap Sort 能保證最差仍為 O(n log n)。 
