接下來我來講述一下插入排序法。
首先來解釋一下插入排序法的原理，它的原理是每插入一個數都要將它和之前的已經完成排序的序列進行重新排序，也就是要找到新插入的數對應原序列中的位置。那麼也就是說，每次插入一個數都要對原來排序好的那部分序列進行重新的排序，時間複雜度同樣為O（n²）。 這種算法是穩定的排序方法。
直接插入排序算法分析
根據代碼我們來解釋一下直接插入排序的核心
例如，我們要對5,3,4,6,2這幾個數進行排序
當這個數組進入函數後，下標首先定義到i = 1，即排序前，首先定義為a[0] = 5即是有序的。
進入循環內，比較a[1] 是否小於 a[0] 發現是小於的，這個時候按理說是要把a[0]這個元素右移動1位。然後將a[1]這個元素插在a[0]的位置上
但是考慮到這樣子將覆蓋原來的a[1]的值，所以先將a[1]的值拷貝一份給temp，然後將a[0]右移一位，再將temp的值傳給a[0] .即
這時i =2了。此時a[0],a[1]屬於有序的序列了，我們此時再次比較a[2]是否小於a[1]（前一位），4<5，滿足if條件
temp = a[2] 先拷貝一份，再將a[1] 右移一位，再次比較a[0]是否大於temp ,發現3並沒有大於4，由此可見只要i前面有序數存在大於a[i]的值，有序序列就要向後移動，
然後再把a[i] 插在正確的位置。
當i = 3時，這個時候6比5大，不滿足if條件，也可以發現，前面已經都是有序序列{3,4,5,6}.
最後當i = 4時，發現2 < a[3] 這個時候同理前面操作，先將a[4]拷貝一份給temp ,a[4] = a[3],右移一位
再次比較 ,發現temp < a[2] , a[3] =a[2] ,右移一位
再次比較 ,發現temp < a[1] , a[2] =a[1] ,右移一位
再次比較 ,發現temp < a[0] , a[1] =a[0] ,右移一位
此時就可以把temp 賦值給了a[0] ，這個時候就已經排序完成了。
a[]01234值23456
直接插入排序複雜度分析
從空間上看，它只需要一個輔助空間temp ，因此我們關鍵看它的時間複雜度。
當最好的情況下，也就是序列本身就是有序的 ，這個時候我們只有進行每次的if判斷(第20行)，比較的次數n-1,移動的次數0，這個時候時間複雜度O(n)
如果排序記錄是隨機的話，那麼根據機率相同的情況原則，平均比較和移動的次數約為(n^2)/4 次，因此我們可以得出直接插入排序法的書劍複雜度為O(n^2) 從這裡也可以看出
直接插入排序比冒泡排序和簡單選擇排序性能要好一點，是一個穩定的排序算法。