假設使用插入排序法（Insertion sort），正要從頭到尾讀取陣列的資料進行排序，對下列那種情況的輸入資料會有最好的效果？

題目

假設使用插入排序法（Insertion sort），正要從頭到尾讀取陣列的資料進行排序，對下列那種情況的輸入資料會有最好的效果？ A. 如果陣列資料以相反順序排序 B. 如果陣列資料已經排序好 C. 如果陣列資料是隨機的順序 D. 輸入陣列資料的順序與效果無關

官方答案

• 答案：B. 如果陣列資料已經排序好

解析

插入排序逐一取出元素，插入前方已排序部分。若輸入已依序排好，每次只需與前一個元素比較一次即可確定位置，不需搬移，時間複雜度降為 O(n)，是最佳情況。若為相反順序，每個元素都得比對並搬移到最前面，退化為 O(n^2)，是最差情況。隨機順序則介於兩者之間，平均約 O(n^2)，所以效果與輸入順序明顯有關。

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

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。