首先來解釋一下插入排序法的原理，它的原理是每插入一個數都要將它和之前的已經完成排序的序列進行重新排序，也就是要找到新插入的數對應原序列中的位置。那么也就是說，每次插入一個數都要對原來排序好的那部分序列進行重新的排序，時間復雜度同樣為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) 從這里也可以看出
直接插入排序比冒泡排序和簡單選擇排序性能要好一點，是一個穩定的排序算法。
