Q30.
下列排序方法，何者在最壞情況下所需計算時間，其複雜度為O(n log n)
電腦軟體設計共同科目 · 乙級 · Q30
難易度分析
3 / 5
本題要求對比多種排序演算法在極端情況下的時間複雜度，考生需能精準區分各演算法在平均與最壞情況下的性能差異，避免將平均複雜度誤認為最壞情況複雜度。
正確答案：③Heap Sort
③ Heap Sort:堆積排序 (Heap Sort) 利用 二元樹堆積 (Binary Heap) 結構進行排序，無論輸入資料分佈為何，建立堆積需 O(n)，每次取出根節點並調整堆積需 O(log n)，共執行 n 次，故最壞情況時間複雜度恆為 O(n log n)。
錯誤選項解析
- ① Bubble Sort:氣泡排序 (Bubble Sort) 在最壞情況下（陣列完全反向）需進行 n-1 輪相鄰元素比較與交換，其時間複雜度為 O(n²)，非 O(n log n)。
- ② Quick Sort:快速排序 (Quick Sort) 的平均時間複雜度為 O(n log n)，但在最壞情況下（每次 樞紐元素 Pivot 均選到最大或最小值，已排序陣列時發生），遞迴深度退化為 n，時間複雜度退化為 O(n²)。
- ④ Shell Sort:希爾排序 (Shell Sort) 為插入排序的改良版，透過 間隔序列 (Gap Sequence) 進行分組排序，其最壞情況時間複雜度取決所選間隔序列，通常為 O(n²) 或 O(n^(3/2))，無法保證達到 O(n log n)。
Learning Tip
"此類題型常考各排序演算法的 時間複雜度 差異。需特別注意 Quick Sort 平均為 O(n log n) 但最壞為 O(n²)，而 Heap Sort 與 Merge Sort 無論任何情況皆穩定維持 O(n log n)。實務上選擇排序演算法時，除複雜度外亦需考量 穩定性 (Stability) 與 記憶體空間 (Space Complexity) 等指標。"
學員答題分佈
①Bubble Sort0%
②Quick Sort0%
③Heap Sort0%
④Shell Sort0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！