資料結構與演算法
以插入排序將有10個元素的陣列依升冪排列。依序取出第2個以後的元素，從左側相鄰的元素開始依序比較，直到找到小於或等於取出值的元素，或到達開頭為止。一開始就是升冪時與一開始是降冪時，比較次數的組合為下列何者？
- A都是45次
- B10次與100次
- C9次與45次
查看答案與解析
正確答案：C. 9次與45次
若已是升冪，取出的值只要與左側相鄰元素比較1次就能決定位置，9個元素合計9次。若是降冪，第 i 個取出的值要與左側全部 i 個元素比較，合計 1 + 2 + … + 9 = 45次。由此可見插入排序最佳為 O(n)、最差為 O(n²)，會隨輸入大幅改變，對幾乎已排序的資料非常快。利用這個性質，先對間隔一定距離的元素進行插入排序的就是希爾排序，Timsort 等也會在短區間使用插入排序。
- A. 比較次數固定為45次的是選擇排序。插入排序的次數會隨輸入的排列而變。
- B. 元素數10或 10² 的100，並不是比較次數。
- C. 正確。升冪時每個元素1次共9次，降冪時為 1 + 2 + … + 9 = 45次。