我們在開發過程中經常會到這樣一類排序問題就是把新的數據插入到已經排好的數據列中。這個時候我們就可能用直接插入排序算法來實現它。
直接插入排序的基本思想：在要排序的一組數中，假設前面(n-1) [n>=2] 個數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反覆循環，直到全部排好順序。
直接插入排序流程如下：
1、首先比較數組的前兩個數據，並排序；
2、比較第三個元素與前兩個排好序的數據，並將第三個元素放入適當的位置；
3、比較第四個元素與前三個排好序的數據，並將第四個元素放入適當的位置；
......
4、直至把最後一個元素放入適當的位置。
舉例說明：要排序數組：int[] arr = {7, 2, 6, 5, 9, 4};
第1趟後:[2, 7], 6, 5, 9, 4
第2趟後:[2, 6, 7], 5, 9, 4
第3趟後:[2, 5, 6, 7], 9, 4
第4趟後:[2, 5, 6, 7, 9], 4
第5趟後:[2, 4, 5, 6, 7, 9]
算法分析
空間複雜度O(1)
時間複雜度O(n2)
最差情況：反序，需要移動n*(n-1)/2個元素
最好情況：正序，不需要移動元素
數組在已排序或者是“近似排序”時，插入排序效率的最好情況運行時間為O(n)；
插入排序最壞情況運行時間和平均情況運行時間都為O(n2)。
通常，插入排序呈現出二次排序算法中的最佳性能。
對於具有較少元素（如n<=15）的列表來說，二次算法十分有效。
代碼實現
代碼
打完收工，謝謝，大家多多支持。
分享到:
閱讀更多 老貓碼坊 的文章
