民國99年 乙級專案 電腦軟體應用乙級 學科
第54題
下列「排序演算法」中,那一種的平均速度最快?
題目
下列「排序演算法」中,那一種的平均速度最快?
- (1) 插入排序
- (2) 泡沬排序
- (3) 快速排序
- (4) 選擇排序
官方答案
(3) 快速排序
解析
快速排序（Quick Sort）採用「分割再遞迴」：先選一個基準值（pivot），把資料分成小於與大於基準的兩群，再分別遞迴排序，平均時間複雜度為 O(n log n)。插入排序、泡沫排序與選擇排序的平均複雜度都是 O(n²)。當資料量 n 變大時，n log n 的成長速度明顯低於 n²，例如 n=1000 時約為 10⁴ 次與 10⁶ 次比較，差距可達百倍，因此平均速度以快速排序最快。快速排序最差情況（例如資料已排序且基準選得不好）會退化為 O(n²)，但平均表現仍最佳。
AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。