插入排序(Insertion Sort)的基本思想是每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止，
程序算法藝術(shù)與實(shí)踐:經(jīng)典排序算法之插入排序
。基本思想與偽代碼
經(jīng)過j-1遍處理后,A[1..j-1]己排好序。第j遍處理僅將A[j]插入L[1..j-1]的適當(dāng)位置，使得A[1..j]又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較A[j]和A[j-1]，如果A[j-1]≤ A[j]，則A[1..j]已排好序，第i遍處理就結(jié)束了；否則交換A[j]與A[j-1]的位置，繼續(xù)比較A[j-1]和A[j-2]，直到找到某一個(gè)位置i(1≤i≤j-1)，使得A[j] ≤A[j+1]時(shí)為止。用偽碼描述如下：
算法: InsertSort(A,n)輸入：n個(gè)數(shù)組A輸出：按照遞增順序的數(shù)組A1. for j ← 2 to n do2. x←A[j]3. i ← j-1 //行3到行7把A[j]插入A[1.....j-1]之中4. while i >0 and x 如下圖所示演示了對(duì)4個(gè)元素進(jìn)行插入排序的過程，共需要(a),(b),(c)三次插入。對(duì)4個(gè)元素進(jìn)行插入排序</p><p> <img alt="/" src="http://img2.shangxueba.com/img/uploadfile/20150924/15/4B074EF11CDA1D4E4FDFB22345370710.gif" /></p><p> 在插入排序算法中，為了寫程序方便我們可以引入一個(gè)哨兵元素A[0]，它小于A[1..n]中任一記錄。所以，我們?cè)O(shè)元素的類型ElementType中有一個(gè)常量-∞，它比可能出現(xiàn)的任何記錄都小。如果常量-∞不好事先確定，就必須在決定A[i]是否向前移動(dòng)之前檢查當(dāng)前位置是否為1，若當(dāng)前位置已經(jīng)為1時(shí)就應(yīng)結(jié)束第i遍的處理。另一個(gè)辦法是在第i遍處理開始時(shí)，就將A[i]放入A[0]中，這樣也可以保證在適當(dāng)?shù)臅r(shí)候結(jié)束第i遍處理。</p><H4>效率分析</h4></p><p> 考慮算法Insertion_Sort的復(fù)雜性。對(duì)于確定的i，內(nèi)while循環(huán)的次數(shù)為O(i)，所以整個(gè)循環(huán)體內(nèi)執(zhí)行了∑O(i)=O(∑i)，其中i從2到n。即比較次數(shù)為O(n2)。如果輸入序列是從大到小排列的，那么內(nèi)while循環(huán)次數(shù)為i-1次，所以整個(gè)循環(huán)體執(zhí)行了∑(i-1)=n(n-1)/2次。由此可知，最壞情況下，Insertion_Sort要比較Ω(n^2)次。如果元素類型是一個(gè)很大的紀(jì)錄，則算法第5行要消耗大量的時(shí)間，因此有必要分析移動(dòng)元素的次數(shù)。經(jīng)過分析可知，平均情況下第5行要執(zhí)行n(n-1)/4次，分析方法與冒泡排序的分析相同。如果移動(dòng)元素要消耗大量的時(shí)間，則可以用鏈表來實(shí)現(xiàn)線性表。</p><H4>Insertion_Sort實(shí)現(xiàn)</h4></p><p> 根據(jù)插入排序偽碼思想，實(shí)現(xiàn)算法代碼如下所示:</p>電腦資料《程序算法藝術(shù)與實(shí)踐:經(jīng)典排序算法之插入排序》(http://clearvueentertainment.com)。那么如下代碼呢>_<:</p>