Q127.
若資料由小到大排序，則下列有關排序演算法之敘述，何者是錯誤？
電腦軟體設計共同科目 · 乙級 · Q127
難易度分析
3 / 5
本題考查多種排序演算法在不同輸入情境下的時間複雜度表現。考生需精確區分最佳情況與最差情況的觸發條件，並在多組對照選項中找出邏輯錯誤的描述，具有一定的對比分析難度。
正確答案：④若資料為依序輸入，Insertion Sort 會產生Worst Case
④ 若資料為依序輸入，Insertion Sort 會產生Worst Case:插入排序法（Insertion Sort） 在資料為已排序（由小到大） 時，每個元素只需與前一個元素比較一次即可確定位置，比較次數為 n-1，時間複雜度為 O(n)，此為 Best Case 而非 Worst Case，故此敘述錯誤。
錯誤選項解析
- ① 若資料為反序輸入，Insertion Sort 會產生Worst Case:插入排序法（Insertion Sort） 在資料為反序（由大到小） 時，每個元素都需要向前比較並移動至最前端，比較與移動次數達到最大值，時間複雜度為 O(n²)，確實會產生 Worst Case。
- ② 若資料為依序輸入，Quick Sort 會產生Worst Case:快速排序法（Quick Sort） 在資料為已排序（由小到大） 且以第一個或最後一個元素作為樞紐（Pivot） 時，每次分割都會產生極度不平衡的分割（一邊為空、另一邊為 n-1 個元素），遞迴深度退化為 n，時間複雜度降為 O(n²)，確實會產生 Worst Case。
- ③ 若資料為反序輸入，Quick Sort 會產生Worst Case:快速排序法（Quick Sort） 在資料為反序 時，同樣因樞紐選擇不當導致分割不平衡，遞迴深度退化，時間複雜度為 O(n²)，確實會產生 Worst Case。
Learning Tip
"本題核心考點為 Insertion Sort 與 Quick Sort 的 Best Case / Worst Case 觸發條件。Insertion Sort 在資料已排序時效率最佳（O(n)），反序時最差（O(n²)）；Quick Sort 則在資料已排序或反序且使用固定端點作為 Pivot 時，皆會退化為 O(n²)。實務上常考陷阱為混淆兩者的最佳與最差情境，需特別注意 Insertion Sort 對已排序資料的適應性（Adaptive） 特性。"
學員答題分佈
①若資料為反序輸入，Insertion Sort 會產生Worst Case0%
②若資料為依序輸入，Quick Sort 會產生Worst Case0%
③若資料為反序輸入，Quick Sort 會產生Worst Case0%
④若資料為依序輸入，Insertion Sort 會產生Worst Case0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！