民國107年 第2梯次 電腦軟體設計(C++)乙級 學科
第22題
對於排序演算法,下列敘述何者正確?
題目
對於排序演算法,下列敘述何者正確?
- (1) 不論資料的順序為何,快速入排序法(Qu ick)所需的比較次數總數皆會比泡沫排序(Bubb le Sort)所需的次數少
- (2) 若輸入n 筆資料已排序完成,利用堆積排序 (Heap So rt)只需O(n)的時間即可完成排序
- (3) 利用快速排序法(Quick Sort)將n 筆資料排序,在最壞的情況下需要O(n log n)時間
- (4) 利用合併排序法(Merge Sort)將n 筆資料排序,平均需要O(n log n)時間
官方答案
(4) 利用合併排序法(Merge Sort)將n 筆資料排序,平均需要O(n log n)時間
解析
合併排序將序列不斷對半分割再合併，分割為 O(log n) 層，每層合併需 O(n)，因此平均與最壞皆為 O(n log n)，此敘述正確。快速排序最壞情況（如資料已排序且固定取首元素為基準）會退化為 O(n^2)，故選項 3 錯誤；也因為如此，快速排序的比較次數不可能恆少於泡沫排序，泡沫排序在資料已排序時最佳可達 O(n)，故選項 1 錯誤。堆積排序即使輸入已排序，仍須 O(n log n)，建堆的 O(n) 只是其中一步，選項 2 錯誤。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。