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

題目

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

1. (1) 若資料為反序輸入, I n s e r t i o n S o r t 會產生W o r s t C a s e
2. (2) 若資料為依序輸入,Q u i c k S o r t 會產生W o r s t C a s e
3. (3) 若資料為反序輸入,Q u i c k S o r t 會產生W o r s t C a s e
4. (4) 若資料為依序輸入,I n s e r t i o n S o r t 會產生W o r s t C a s e

官方答案

(4) 若資料為依序輸入,I n s e r t i o n S o r t 會產生W o r s t C a s e

解析

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

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

官方資料

• 官方試題 PDF