插入排序

關鍵碼是數據元素中某個數據項的值，用它可以標示一個數據元素。通常會用紀錄來標示數據元素，一個紀錄可以有若干數據項組成。例如，一個學生的信息就是一條紀錄，它包括學號，姓名，性別等若干數據項。主關鍵碼可以唯一的標示一個紀錄的關鍵碼，如學號。次關鍵碼是可以標示若干記錄的關鍵字，如性別、姓名。

假設一個文件有n跳紀錄{}，對應的關鍵碼是{}，排序家就是將此n個紀錄按照關鍵碼的大小遞增（或遞減）的次序排列起來，使這些紀錄由無序變為有序的一種操作。排序后的序列若為{}時，其對應的關鍵碼值滿足{}或{}。

若在待排序的紀錄中，存在兩個或兩個以上的關鍵碼值相等的紀錄，經排序后這些記錄的相對次序仍然保持不變，則稱相應的排序方法是穩定的方法，否則是不穩定的方法。

根據排序過程中涉及的存儲器不同，可以講排序方法分為兩大類：一類是內部排序，指的是待排序的幾率存放在計算機隨機存儲器中進行的排序過程；另一類的外部排序，指的是排序中要對外存儲器進行訪問的排序過程。

內部排序是排序的基礎，在內部排序中，根據排序過程中所依據的原則可以將它們分為5類：插入排序、交換排序、選擇排序、歸併排序和基數排序；根據排序過程的時間複雜度來分，可以分為三類：簡單排序、先進排序、基數排序。

評價排序演演算法優劣的標準主要是兩條：一是演演算法的運算量，這主要是通過記錄的比較次數和移動次數來反應；另一個是執行演演算法所需要的附加存儲單元的的多少。

包括：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）。屬於穩定排序的一種（通俗地講，就是兩個相等的數不會交換位置） 。

直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。

例如，已知待排序的一組紀錄是：

60,71,49,11,24,3,66

假設在排序過程中，前3個紀錄已按關鍵碼值遞增的次序重新排列，構成一個有序序列：

49,60,71

將待排序紀錄中的第4個紀錄（即11）插入上述有序序列，以得到一個新的含4個紀錄的有序序列。首先，應找到11的插入位置，再進行插入。可以講11放入數組的第一個單元r中，這個單元稱為監視哨，然後從71起從右到左查找，11小於71，將71右移一個位置，11小於60，又將60右移一個位置，11小於49，又再將49右移一個位置，這時再將11與r的值比較，11≥r，它的插入位置就是r。假設11大於第一個值r。它的插入位置應該在r和r之間，由於60已經右移了，留出來的位置正好留給11.後面的紀錄依照同樣的方法逐個插入到該有序序列中。若紀錄數n,續進行n-1趟排序，才能完成。

直接插入排序的演演算法思路：

（1）設置監視哨r，將待插入紀錄的值賦值給r；

（2）設置開始查找的位置j；

（3）在數組中進行搜索，搜索中將第j個紀錄后移，直至r.key≥r[j].key為止；

（4）將r插入r[j+1]的位置上。

直接插入排序演演算法：

public void zjinsert (Redtype r[],int n)

{

int I,j;

Redtype temp;

for (i=1;i

{

temp = r[i];

j=i-1;

while (j>-1 &&temp.key

{

r[j+1]=r[j];

j--;

}

r[j+1]=temp;

}

}

將直接插入排序中尋找A[i]的插入位置的方法改為採用折半比較，即可得到折半插入排序演演算法。在處理A[i]時，A……A[i-1]已經按關鍵碼值排好序。所謂折半比較，就是在插入A[i]時，取A[i-1/2]的關鍵碼值與A[i]的關鍵碼值進行比較，如果A[i]的關鍵碼值小於A[i-1/2]的關鍵碼值，則說明A[i]只能插入A到A[i-1/2]之間，故可以在A到A[i-1/2-1]之間繼續使用折半比較；否則只能插入A[i-1/2]到A[i-1]之間，故可以在A[i-1/2+1]到A[i-1]之間繼續使用折半比較。如此擔負，直到最後能夠確定插入的位置為止。一般在A[k]和A[r]之間採用折半，其中間結點為A[k+r/2]，經過一次比較即可排除一半紀錄，把可能插入的區間減小了一半，故稱為折半。執行折半插入排序的前提是文件紀錄必須按順序存儲。

折半插入排序的演演算法思想：

演演算法的基本過程：

（1）計算 0 ~ i-1 的中間點，用 i 索引處的元素與中間值進行比較，如果 i 索引處的元素大，說明要插入的這個元素應該在中間值和剛加入i索引之間，反之，就是在剛開始的位置 到中間值的位置，這樣很簡單的完成了折半；

（2）在相應的半個範圍裡面找插入的位置時，不斷的用（1）步驟縮小範圍，不停的折半，範圍依次縮小為 1/2 1/4 1/8 .......快速的確定出第 i 個元素要插在什麼地方；

（3）確定位置之後，將整個序列后移，並將元素插入到相應位置。

3 希爾排序法

希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成個組，所有距離為的記錄分在同一組內，並對每一組內的記錄進行排序。然後，取，重複上述分組和排序的工作。當到達=1時，所有記錄在統一組內排好序。

各組內的排序通常採用直接插入法。由於開始時s的取值較大，每組內記錄數較少，所以排序比較快。隨著不斷增大，每組內的記錄數逐步增多，但由於已經按排好序，因此排序速度也比較快。

將n個元素的數列分為已有序和無序兩個部分，如

下所示：

{{a1}，{a2，a3，a4，…，an}}

{{a1⑴，a2⑴}，{a3⑴，a4⑴ …，an⑴}}

…

{{a1(n-1），a2(n-1) ，…},{an(n-1)}}

每次處理就是將無序數列的第一個元素與有序數列的元素從后往前逐個進行比較，找出插入位置，將該元素插入到有序數列的合適位置中。

假設在一個無序的數組中，要將該數組中的數按插入排序的方法從小到大排序。假設啊a[]={3,5,2,1,4};插入排序的思想就是比大小，滿足條件交換位置，一開始會像冒泡排序一樣，但會比冒泡多一步就是交換后（a[i]=a[i+1]后）原位置（a[i]）會繼續和前面的數比較滿足條件交換，直到a[i+1]前面的數組是有序的。比如在第二次比較后數組變成a[]={2,3,5,1,4};

一般來說，插入排序都採用in-place在 數組上實現。具體演演算法描述如下：

⒈ 從第一個元素開始，該元素可以認為已經被排序

⒉ 取出下一個元素，在已經排序的元素序列中從後向前掃描

⒊ 如果該元素（已排序）大於新元素，將該元素移到下一位置

⒋ 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置

⒌ 將新元素插入到下一位置中

⒍ 重複步驟2~5

如果比較操作的代價比交換操作大的話，可以採用 二分查找法來減少比較操作的數目。該演演算法可以認為是插入排序的一個變種，稱為 二分查找排序。

INSERTION-SORT( )

1 for 2 tolength[ ]

2 do = [ ]

3 //Insert [ ] into the sorted sequence [1.. -1].

4 = -1

5 while >0 and [ ] >

6 do [ +1] = [ ]

7 = -1

8 [ +1] =

示例代碼為C語言，輸入參數中，需要排序的 數組為array[ ]，起始索引為first（數組有序部分最後一個的下標，或者直接標 0），終止索引為last（數組元素的最後一個的下標）。示例代碼的函數採用insert-place排序，調用完成後，array[]中從first到last處於升序排列。

這個更好：

c++版本

運行軟體：eclipse

procedure insertsort(var R:filetype);

//對R[1..N]按遞增序進行插入排序，R是監視哨

begin

for I := 2 To n do //依次插入R,...,R[n]

begin

R:=R[I];j:=l-1;

while R < R[J] Do //查找R[I]的插入位置

begin

R[j+1]:=R[j]; //將大於R[I]的元素后移

j:=j-1;

end;

R[j+1]:=R ; //插入R[I]

end;

end; //InsertSort

(運行軟體：Free Pascal IDE 2.6.4)

如果目標是把n個元素的序列升序排列，那麼採用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需（n-1）次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數加上 (n-1）次。平均來說插入排序演演算法的時間複雜度為O(n^2）。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。

插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素。當然，剛開始這個有序的小序列只有1個元素，就是第一個元素。比較是從有序序列的末尾開始，也就是想要插入的元素和已經有序的最大者開始比起，如果比它大則直接插入在其後面，否則一直往前找直到找到它該插入的位置。如果碰見一個和插入元素相等的，那麼插入元素把想插入的元素放在相等元素的後面。所以，相等元素的前後順序沒有改變，從原無序序列出去的順序就是排好序后的順序，所以插入排序是穩定的。