若資料由小到大排序,則下列有關排序演算法之敘述,何者是錯誤?

題目

若資料由小到大排序,則下列有關排序演算法之敘述,何者是錯誤?

1. (1) 若資料為反序輸入,Insert ion Sort 會產生Worst Case
2. (2) 若資料為依序輸入,Qu ick Sort 會產生Worst Case
3. (3) 若資料為反序輸入,Quick Sort 會產生Worst Case
4. (4) 若資料為依序輸入,Insertion Sort 會產生Worst Case

官方答案

(4) 若資料為依序輸入,Insertion Sort 會產生Worst Case

解析

Insertion Sort 在資料已依序（近乎有序）時比較與搬移次數最少，屬最佳狀況 O(n)，故「依序輸入產生 worst case」是錯誤敘述，答案 4。選項 1 對：反序時每個元素皆需逐格移至最前端，為 worst case O(n²)；選項 2、3 對：Quick Sort 若固定取首或尾為基準，已排序或反序都會使分割極度不平衡，皆為 worst case O(n²)。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF