插入排序演算法原理

這個演算法要解決的問題是，怎么對序列 A = ( a 1 , a 2 , a 3 , . . . a n ) A=(a_1,a_2,a_3,...a_n) A=(a1?,a2?,a3?,...an?)重新排序，
一種暴力排序的方法是，每一個回圈中，通過兩兩比較，找到現有序列中最小值，依次放到一個新序列中（已經放到新序列中的數，下一個找最小值的回圈就不再參與），這樣，為了排出有序列，需要比較 n ( n ? 1 ) 2 \frac{n(n-1)}{2} 2n(n?1)?次，也就是說，其時間復雜度為 O ( n 2 ) O(n^2) O(n2)，相對較高，并且，因為要形成一個新的容器存放排好序的序列，在大資料的情況下，很占記憶體，即該演算法空間復雜度也較高，
如何改進這種暴力解法？首先，要降低空間復雜度，需要減少新容器中的元素；其次，要降低時間復雜度，要減少元素比較的次數，
從空間復雜度上優化該暴力演算法的思路可以類比撲克牌抓牌時候的排序程序，每新抓一張牌，會把這張牌和已有的牌比較大小，依此選擇插入點，因此，每次抓牌之前，手中的牌都是一個排好序的序列，歸結到演算法上，是每次將一個數插入到合適的位置中，
若要將序列從小到大排序，可以將這一程序抽象為：先在序列 A A A中抽出第2個元素 a 2 a_2 a2?，將其與 a 1 a_1 a1?比較大小，若 a 2 < a 1 a_2<a_1 a2?<a1?，將 a 2 a_2 a2?放在 a 1 a_1 a1?左側，若 a 2 > a 1 a_2>a_1 a2?>a1?，將 a 2 a_2 a2?放在 a 1 a_1 a1?右側，這樣，在 A A A中排好了兩個元素的有序子列 ( a 1 ′ , a 2 ′ ) (a_1^{'},a_2^{'}) (a1′?,a2′?)，本次排序結束，再抽出 a 3 a_3 a3?，將其與 a 2 ′ a_2^{'} a2′?比較，若大于，令 a 3 ′ = a 3 a_3^{'}=a_3 a3′?=a3?，其他元素均不變，本次排序結束，若小于，先令 a 3 ′ = a 2 ′ a_3^{'}=a_2^{'} a3′?=a2′?，再將 a 3 a_3 a3?與 a 1 ′ a_1^{'} a1′?比較，若大于，令 a 2 ′ = a 3 a_2^{'}=a_3 a2′?=a3?，本次排序結束，若小于 a 1 ′ a_1^{'} a1′?，因為 a 1 ′ a_1^{'} a1′?左邊沒有其他數了， a 3 a_3 a3?只能放在 a 1 ′ a_1^{'} a1′?左邊，也就是令 a 2 ′ = a 1 ′ a_2^{'}=a_1^{'} a2′?=a1′?， a 1 ′ = a 3 a_1^{'}=a_3 a1′?=a3?，本次排序結束，由特例可以發現，整個排序程序有兩次回圈，大回圈是從序列A中依此抽元素 a k a_k ak?，小回圈是將 a k a_k ak?與 A ′ A^{'} A′中每個元素比較，小回圈中止條件是 a k > a j ′ a_k>a_j^{'} ak?>aj′?（ a k a_k ak?插到 a j ′ a_j^{'} aj′?右側， a j + 1 ′ a_{j+1}^{'} aj+1′?左側），或是 j ? 1 = 0 j-1=0 j?1=0（ a k a_k ak?插到序列最左側），回圈繼續條件則反過來，
可以算出，該方法時間復雜度仍是 O ( n 2 ) O(n^2) O(n2)，但因為該解法使用原地排序，只要建立一個存放待插入元素的容器，空間復雜度會比暴力解法低很多，
據此，可以寫出該程序的代碼，

偽代碼及Python實作

偽代碼

for j=2 to len(A)
//為了避免在賦值的程序中數字丟失，需要另設一個引數存放每次要插入的元素，可以試試如果不設key會怎樣
//這里可看出，相比于暴力解法，該解法大大降低了空間復雜度，暴力解法需要建立一個和原序列一樣長的容器，而該解法只要建立單元素容器，
  key = a[j]
  //默認條件是j之前的數已經排好序，因為代碼正確執行后，這一條件一定成立，這是理解該代碼的難點，
  //每次都是先和序列中前一個數比大小，這里的a[i]相當于A'序列中的數，
  i = j-1
  //小回圈，這里用while書寫，因為回圈次數未知，根據本文第一部分的分析，可寫出回圈繼續條件
  while key < a[i] & i>0
  //新元素小于A'第i個值，則A’第i個值往后移一位，即A'中第i+1個元素被賦值為原第i個元素的值
      a[i+1]=a[i]
      //注意while回圈中要規定回圈方向（for則不需要），否則會停住，此處是往A'的左側走
      i=i-1
      //若新元素大于等于A'第i個值，則將該元素插到A'第i+1個位置，同時回圈結束，新元素右側的元素位置都已經更新過，左側的則不用變，
      //若新元素小于A'所有值，即掃描到了i=0，則回圈結束，該元素插到A’第1個位置，也即i+1，故兩種情況可以統一表示，
  a[i+1]=key
    //一個新元素的插入完成，從原序列中抽下一個元素，

python代碼實作

構造一個實體：對序列A=[1,4,6,3,5,10,7,3,8]從小到大排序，
當然，用python內置的sorted函式可以一次性完成排序：

sorted(A, reverse=FALSE)

如果要自己撰寫一個排序函式，如何實作呢？可以根據上述偽代碼寫出python代碼：

//升序排列
def sort(lista):
    for j in range(1,len(lista)):
        key = lista[j]
        i = j-1
        while key > lista[i]  and i>=0:
            lista[i+1]=lista[i]
            i = i-1
        lista[i+1]=key
        print(lista)
sort(A)

//降序排列只要把key > lista[i]換成key<lista[i]即可

演算法分析（RAM模型）

在RAM模型中，假定：1、陳述句只能是真實的基本計算機指令，而不能是一個封裝好的包，2、每一陳述句的執行時間是一個常量，3、不同陳述句不能并行計算，
雖然這些條件不一定成立，但在分析演算法時間復雜度中有很大作用，
下圖是插入排序演算法每一步的執行時間與執行次數統計（圖源自《演算法導論》），

為何第一句運行次數為n而非n-1？需要注意for，while回圈陳述句執行測驗次數比執行回圈體次數多1，
t j t_j tj?指第j個元素進行插入時，進行while回圈測驗的次數（注意比回圈體執行次數多1），回圈體執行次數即待插入元素與A‘序列元素比較的次數，取決于是序列排序程度，最好情況是完全升序，這樣即不用執行回圈體， t j = 1 t_j=1 tj?=1，最壞情況是完全降序，這樣待插入元素需要和j之前的j-1個元素比較，則有 t j = j t_j=j tj?=j，可以總結出技巧：同一級回圈體內的陳述句執行次數應當是相同的，while下面的陳述句實際是和for回圈一級的，因此執行次數也是n-1，
根據RAM的假設，若要知道該演算法耗費總時間，求這些步的時間次數乘積和即可，
計算可得，在最好情況下， T ( n ) = a n + b T(n)=an+b T(n)=an+b
最壞情況下， T ( n ) = a n 2 + b n + c T(n)=an^2+bn+c T(n)=an2+bn+c
這里也可以看出，演算法運行時間取決于很多因素：輸入規模(n)、資料排序程度、單步運行時間……

時間復雜度

由上述部分可以看出，演算法運行時間有最壞情況，也有最好情況，但演算法分析一般只看最壞情況，1、最壞情況確定了演算法運行時間的上界，在演算法時間復雜度的比較上，如果可以證明A演算法的最壞情況都比B演算法的最好情況快，那A在這一層面上一定是優于B演算法的，2、一般來說，平均情況和最壞情況一樣壞，在插入排序中，平均情況是有一半數是升序排好的， t j = j / 2 t_j=j/2 tj?=j/2，這樣算出的T(n)仍然有二次項，
并且，我們更關注的是演算法運行時間的增長率，或者說我們作不同演算法的比較時，統一將n視為無窮大，此時，常數系數也可以被忽略，因此，我們定義時間復雜度 O ( n ) O(n) O(n)為當n趨向無窮大時，其運行時間增長率的決定因素，即T(n)最高項的非常數因子，因此，在暴力排序和插入排序中，都有 O ( n ) = n 2 O(n)=n^2 O(n)=n2，
對于最高項階數相同的演算法，比較其復雜度則可以看其最高項系數，如A演算法有 O ( n ) = 2 n O(n)=2n O(n)=2n，B演算法有 O ( n ) = n O(n)=n O(n)=n，B時間復雜度更低，
當然，當輸入規模較小時，常數系數和低階項的影響可能會占上風，但總會存在臨界規模，高于該規模，高階項起決定作用，