民國107年 第2梯次 電腦軟體設計(JAVA)乙級 學科
第30題
對於排序演算法,下列敘述何者正確?
題目
對於排序演算法,下列敘述何者正確?
- (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(n)，共約 log n 層，平均與最壞情況皆為 O(n log n)，故第 4 項正確。快速排序最壞情況（如資料已排序且固定取邊界元素為基準）會退化為 O(n²)，並非 O(n log n)。堆積排序建立堆積需 O(n)，但後續 n 次取出最大值每次調整堆積需 O(log n)，即使輸入已排序仍為 O(n log n)，不會降到 O(n)。快速排序在特定輸入下比較次數也可能多於泡沫排序，因此「不論資料順序皆較少」的說法不成立。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。