插入排序(Insertion Sort)的基本思想是每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子文件中的適當位置，直到全部記錄插入完成為止。 #### 基本思想與偽代碼 經過j-1遍處理后,A[1..j-1]己排好序。第j遍處理僅將A[j]插入L[1..j-1]的適當位置，使得A[1..j]又是排好序的序列。要達到這個目的，我們可以用順序比較的方法。首先比較A[j]和A[j-1]，如果A[j-1]≤ A[j]，則A[1..j]已排好序，第i遍處理就結束了；否則交換A[j]與A[j-1]的位置，繼續比較A[j-1]和A[j-2]，直到找到某一個位置i(1≤i≤j-1)，使得A[j] ≤A[j+1]時為止。用偽碼描述如下： ~~~ 算法: InsertSort(A,n) 輸入：n個數組A 輸出：按照遞增順序的數組A 1. for j ← 2 to n do 2. x←A[j] 3. i ← j-1 //行3到行7把A[j]插入A[1.....j-1]之中 4. while i >0 and x <A[i] do 5. A[i+1] ← A[i] 6. i← i-1 7. A[i+1] ← x ~~~ 如下圖所示演示了對4個元素進行插入排序的過程，共需要(a),(b),(c)三次插入。對4個元素進行插入排序  在插入排序算法中，為了寫程序方便我們可以引入一個哨兵元素A[0]，它小于A[1..n]中任一記錄。所以，我們設元素的類型ElementType中有一個常量-∞，它比可能出現的任何記錄都小。如果常量-∞不好事先確定，就必須在決定A[i]是否向前移動之前檢查當前位置是否為1，若當前位置已經為1時就應結束第i遍的處理。另一個辦法是在第i遍處理開始時，就將A[i]放入A[0]中，這樣也可以保證在適當的時候結束第i遍處理。 #### 效率分析 考慮算法Insertion_Sort的復雜性。對于確定的i，內while循環的次數為O(i)，所以整個循環體內執行了∑O(i)=O(∑i)，其中i從2到n。即比較次數為O(n2)。如果輸入序列是從大到小排列的，那么內while循環次數為i-1次，所以整個循環體執行了∑(i-1)=n(n-1)/2次。由此可知，最壞情況下，Insertion_Sort要比較Ω(n^2)次。如果元素類型是一個很大的紀錄，則算法第5行要消耗大量的時間，因此有必要分析移動元素的次數。經過分析可知，平均情況下第5行要執行n(n-1)/4次，分析方法與冒泡排序的分析相同。如果移動元素要消耗大量的時間，則可以用鏈表來實現線性表。 #### Insertion_Sort實現 根據插入排序偽碼思想，實現算法代碼如下所示: ~~~ void InsertSort(int *a,int n) { int i,j,t,m; for (i=1;i<n;i++) { t=a[i]; j=i-1; while(j>=0 && t<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=t; } } ~~~ 我們對上述實現codes，感覺并不是喜歡編程風格(^_^)。那么如下代碼呢>_<: ~~~ void InsertionSort(int *ptritems, int count) { int i, j, k; for (i=1; i< count; ++i) { k = ptritems[i]; for ( j=i-1; (j>=0) && (k<ptritems[j]); j--) ptritems[j+1] = ptritems[j]; ptritems[j+1] = k; } } ~~~ 測試之前，在此給出部分Main函數的部分code.其中約定N為20（輸入數組大小），同時，為了讓輸入數組的值是隨機產生，使用rand()函數。代碼如下所示： ~~~ int array[N],i; //聲明數組 srand(time(NULL)); for(i=0;i<N;i++){ //初始化數組 array[i]=rand()/1000+10; } printf("Sort Before:\n"); for(i=0;i<N;i++) { printf("%d ",array[i]); //輸出 } printf("\n"); InsertSort(array,N);//排序 printf("Sort After：\n"); for(i=0;i<N;i++) { printf("%d ",array[i]); //輸出 } ~~~ 在這段程序中，主函數首先初始化一個數組，并輸出排序前的數組內容。然后，調用插入排序法子函數，接著輸出排序后的數組內容。 在插入排序法子程序中，首先將需要插入的元素保存到變量t中。變量j表示插入的位置（插入數組元素的序號），設置其值為i-1，表示準備將當前位置（序號為i）的數插入到序號為i-1（即前一個元素）的位置。 接著，通過while循環判斷，如果序號為j元素的數據大于變量t（需要插入的數據），則將序號為j的元素向后移，同時j-1，以判斷前一個數據是否還需要向后移。通過該循環，找到一個元素的值比t小，該元素的序號為j。然后，將在序號為j的下一個元素插入數據。 編譯執行這段程序，得到如下結果，如下圖所示。  插入排序法在數據已有一定順序的情況下，效率較好。但如果數據無規則，則需要移動大量的數據，其效率就與冒泡排序法和選擇排序法一樣差了。插入排序法是一個原地置換排序法，也是一個穩定排序法。插入法雖然在最壞情況下復雜性為θ(n^2)，但是對于小規模輸入來說，插入排序法是一個快速的原地置換排序法。許多復雜的排序法，在規模較小的情況下，都使用插入排序法來進行排序，比如快速排序和桶排序。 關于[程序算法藝術與實踐](http://blog.csdn.net/column/details/tac-programalgrithm.html)更多討論與交流，敬請關注本博客和新浪微博[songzi_tea](http://weibo.com/songzitea).