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