插入排序演演算法原理

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

虛擬碼及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$指第j個元素進行插入時，進行while迴圈測試的次數（注意比迴圈體執行次數多1）。迴圈體執行次數即待插入元素與A‘序列元素比較的次數，取決於是序列排序程度。最好情況是完全升序，這樣即不用執行迴圈體，$t_j=1$。最壞情況是完全降序，這樣待插入元素需要和j之前的j-1個元素比較，則有$t_j=j$。可以總結出技巧：同一級迴圈體內的語句執行次數應當是相同的。while下面的語句實際是和for迴圈一級的，因此執行次數也是n-1。
根據RAM的假設，若要知道該演演算法耗費總時間，求這些步的時間次數乘積和即可。
計算可得，在最好情況下，$T(n)=an+b$
最壞情況下，$T(n)=a{n}^2+bn+c$
這裡也可以看出，演演算法執行時間取決於很多因素：輸入規模(n)、資料排序程度、單步執行時間……

時間複雜度

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