問題詳情

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

參考答案

答案：B
難度：簡單0.78
書單：沒有書單，新增

用户評論

【牛奶】評論

插入排序作法：將資料分成已排序、未排序兩部份依序由未排序中的第一筆(正處理的值)，插入到已排序中的適當位置插入時由右而左比較，直到遇到第一個比正處理的值小的值，再插入比較時，若遇到的值比正處理的值大或相等，則將值往右移時間複雜度(Time Complexity)Best Case：Ο(1)當資料的順序恰好為由小到大時，每回合只需比較1次Worst Case：Ο(n2)當資料的順序恰好為由大到小時，第i回合需比i次Average Case：Ο(n2)第n筆資料，平均比較n/2次