插入排序

插入排序的工作機理跟打牌時整理手中的牌差不多，開始摸牌時，我們左手是空的，牌面朝下放在桌上。接著，一次從桌上摸起一張牌，并將它插入到左手一把牌中的正確位置上。為了找到這張牌的正確位置，要將它與手中已有的每一張牌從右到左地進行比較。

算法的偽代碼如下所示：

INSERTION-SORT(A)1    for j <— 2 to length[A]2       do k <— A[j]3             Insert A[j] into the sorted sequence A[1..j-1].4            i <— j - 15            while i > 0 and A[i] > key6                do A[i+1] <— A[i]7                    i <— i - 18            A[i+1] <— key

回到頂部

偽代碼中的約定：

1.書寫上的“縮進”表示程序中的分程序（程序塊）結構

2.while,for,repeat等循環結構和if,then,else條件結構與Pascal中相同

3.符號“”表示后面部分是注釋

4.多重賦值i<—j<—e 是將表達式e的值賦給變量i和j;等價于賦值j<—e,在進行賦值i <—j

5.變量（如i,j和key等）是局部于給定過程的。在沒有顯示說明的情況下，我們不使用全局變量

6.數組元素是通過“數組名[下標]”這樣的形式來訪問的

7.復合數據一般組織成對象，它們是由屬性或域所組成的

8.參數采用按值傳遞方式：被調用的過程會收到參數的一份副本

9.布爾運算符“and”和“or”都具有短路能力

回到頂部

算法分析：

首先給出 INSERTION-SORT 過程中，每一條指令的執行時間及執行次數。對j=2,3,...,n,n=length[A],設t_j為地5行中while循環所做的測試次數。當for或while以通常方法退出（即，因為循環頭部的測試條件不滿足而退出）時，測試要比循環體多執行一次。另外，還假定注解部分是不可執行的，因而不占運算時間。

對上面偽代碼分析如下：

sequence　　　　cost　　　　times

　　1　　　　　  　c_{1　　　　　　n}

　　2　　　　　　 c₂ n-1

　　3 　　　　　　0　　　　　　n-1

　　4　　　　　　 c₄ 　　　　　n-1

　　5　　　　　　 c₅ 

　　6　　　　　　 c₆ 

　　7　　　　　　 c₇ 

　　8　　　　　　 c₈ n-1

該算法總的運行時間是每一條語句執行時間之和。如果執行一條語句需要c_i步，又共執行了n次這條語句，那么它在總運行時間中占c_in。為計算總運行時間T[n],對每一對cost與times之積求和，得：

即使是對給定規模的輸入，一個算法的運行時間也有可能要依賴于給定的是該規模下的哪種輸入。

如果輸入數組已經是排好序的話，就會出現最佳情況。對j=2,3,...,n中的每一個值，我們發現，在第五行中，當i取其初始值 j-1 時，都有A[i]≤key。于是，對j=2,3,...,n，有t_j=1，最佳運行時間為：

這一運行時間可以表示為 an+b，常量a和常量b依賴于語句的代價c_{i；因此，它是n的一個線性函數。}

如果輸入數組是按照逆序排序的，那么就會出現最壞情況，運行時間為：

注：　　，

這一最壞情況運行時間可以表示為an²+bn+c，常量a,b,c仍依賴于語句的代價c_i；因此，這是一個關于n的二次函數。

回到頂部

算法實現

以下是JavaScript代碼對其算法的實現：

 1 'use strict'; 2 function insertionSort(Arr) { 3     for(let j = 1,len = Arr.length; j < len; j++) { 4         let key = Arr[j]; 5         let i = j - 1; 6         while (i > 0 && Arr[i] > key) { 7             Arr[i + 1] = Arr[i]; 8             i--; 9         }10         Arr[i + 1] = key;11     }12 }