Q47.
對於排序演算法，下列敘述何者正確？
電腦軟體設計共同科目 · 乙級 · Q47
難易度分析
3 / 5
本題要求考生精確區分多種排序演算法在最佳、平均及最壞情況下的時間複雜度差異，且選項中設定了多個容易混淆的複雜度數值，需具備對演算法特性之精準記憶與對比能力方能正確判斷。
正確答案：④利用合併排序法(Merge Sort)將n 筆資料排序，平均需要O(n log n)時間
④ 利用合併排序法(Merge Sort)將n 筆資料排序，平均需要O(n log n)時間:合併排序法(Merge Sort) 採用 分治法(Divide and Conquer) 策略，無論最佳、平均或最壞情況，時間複雜度均穩定為 O(n log n)，此為其核心特性。
錯誤選項解析
- ① 不論資料的順序為何，快速入排序法(Quick)所需的比較次數總數皆會比泡沫排序(Bubble Sort)所需的次數少:快速排序法(Quick Sort) 在最壞情況下（如資料已排序且樞紐選取不當）時間複雜度為 O(n²)，此時比較次數可能多於 泡沫排序(Bubble Sort) 的最佳情況 O(n)，因此並非「不論資料順序為何」都較少。
- ② 若輸入n 筆資料已排序完成，利用堆積排序(Heap Sort)只需O(n)的時間即可完成排序:堆積排序(Heap Sort) 即使輸入資料已排序完成，仍需執行 Build Heap 與 n 次 Extract-Max 操作，時間複雜度為 O(n log n)，無法在 O(n) 時間內完成。
- ③ 利用快速排序法(Quick Sort)將n 筆資料排序，在最壞的情況下需要O(n log n)時間:快速排序法(Quick Sort) 在最壞情況下（如樞紐始終選到最大或最小值）需要 O(n²) 時間，而非 O(n log n)；O(n log n) 是其 平均情況 的時間複雜度。
Learning Tip
"本題核心考點為各排序演算法的 時間複雜度 比較。常考陷阱：快速排序 平均為 O(n log n) 但最壞為 O(n²)；合併排序 始終為 O(n log n) 但需額外空間；堆積排序 為原地排序且固定 O(n log n)。需特別注意題目問的是「最佳」、「平均」或「最壞」情況，避免混淆。"
學員答題分佈
①不論資料的順序為何，快速入排序法(Quick)所需的比較次數總數皆會比泡沫排序(Bubble Sort)所需的次數少0%
②若輸入n 筆資料已排序完成，利用堆積排序(Heap Sort)只需O(n)的時間即可完成排序0%
③利用快速排序法(Quick Sort)將n 筆資料排序，在最壞的情況下需要O(n log n)時間0%
④利用合併排序法(Merge Sort)將n 筆資料排序，平均需要O(n log n)時間0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！