插入排序

C語言的插入排序法是什么？

插入排序(inrtion sort)

如果需要對一個小型數組進行升序排列，那么可以選用插入排序，插入排序可以用打牌時對摸起的牌根據牌的點數來對其進行插入排列來描述。

可以把左手中的牌比做已經摸起的牌，即已經被排列好的牌，左手可以容納的牌數的空間可以假想為和要摸的牌的總數相同；而在桌子上的那部分沒摸的牌則是未被排序的牌，這二者的關系可以抽象為數組中已經被排序好的部分和未被排序好的部分。

一開始摸起的第一張牌不需要排序，可以認定其為已排序的牌。

如果用外層循環for來表示摸起的牌的話，則可以抽象為：

// 對象數組

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 從數組的第二個元素開始抽取

for(int i = 1; i < sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j記錄已排序部分的最后一張牌的位置

. . .

}

而后摸起的排要根據排列策略和先前摸起的牌的點數的大小來確定其插入的合適位置，這里示范的排列策略是升序排列，摸起了這張牌后，便自右向左地和手中的牌進行比較。

把pick稱作摸起的牌，如果pick比手中的牌小，則手中較大的那張牌就向右挪一位，pick再和下一張牌做比較，如果下一張牌仍然比pick大，那么那張牌便也向右移動一個位置，依此類推。

如果手中下一張和pick比較的牌比pick小，那么pick就被插入在了手中前一張牌移動后空下的位置；

或者手中所有的牌都比pick大，那么所有的牌就都向右移動過一個位置，所以pick最終被插入在了手中最左邊的位置。

這個過程可以抽象為：

// 對象數組

// 桌子上的牌

int A[] = {5,1,3,6,2,4};

// 從數組的第二個元素開始抽取

for(int i = 1; i < sizeof A/sizeof A[0]; ++i)

{

int pick = A[i]; // 被摸起的牌

int j = i - 1; // j記錄已排序部分的最后一張牌的位置

// 如果循環了j+1次，即j = -1時還未找到比pick小的牌

// 那么pick就是最小的牌被插入在位置A[0]處

// A[j]是當前手中和pick進行比較的牌

while(j >= 0 && A[j] > pick)

{

// 未找到可插入位置，則A[j]向后挪一位

A[j+1] = A[j];

// j減1繼續向左定位手中下一張供和pick比較的牌--j;

}


// while結束后，j+1所表達的位置便是pick可以插入的位置

A[j+1] = pick;

}

// 對于有N個元素的數組A，采用插入排序法排序時，當外層循環進行了N-1次后排序完畢

插入排序的分類

包括：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）。屬于穩定排序的一種（通俗地講，就是兩個相等的數不會交換位置） 。 直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的紀錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的紀錄插入完為止，得到一個新的有序序列。
例如,已知待排序的一組紀錄是：
60,71,49,11,24,3,66
假設在排序過程中，前3個紀錄已按關鍵碼值遞增的次序重新排列，構成一個有序序列：
49,60,71
將待排序紀錄中的第4個紀錄（即11）插入上述有序序列，以得到一個新的含4個紀錄的有序序列。首先，應找到11的插入位置，再進行插入。可以講11放入數組的第一個單元r[0]中，這個單元稱為監視哨，然后從71起從右到左查找，11小于71，將71右移一個位置，11小于60，又將60右移一個位置，11小于49，又再將49右移一個位置，這時再將11與r[0]的值比較，11≥r[0]，它的插入位置就是r[1]。假設11大于第一個值r[1]。它的插入位置應該在r[1]和r[2]之間，由于60已經右移了，留出來的位置正好留給11.后面的紀錄依照同樣的方法逐個插入到該有序序列中。若紀錄數n,續進行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1） 設置監視哨r[0]，將待插入紀錄的值賦值給r[0]；
（2） 設置開始查找的位置j；
（3） 在數組中進行搜索，搜索中將第j個紀錄后移，直至r[0].key≥r[j].key為止；
（4） 將r[0]插入r[j+1]的位置上。
直接插入排序算法：
public void zjinrt (Redtype r[],int n)
{
int I,j;
Redtype temp;
for (i=1;i<n;i++)
{
temp = r[i];
j=i-1;
while (j>-1 &&temp.key<r[j].key)
{
r[j+1]=r[j];
j--;
}
r[j+1]=temp;
}
} 將直接插入排序中尋找A[i]的插入位置的方法改為采用折半比較，即可得到折半插入排序算法。在處理A[i]時，A[0]……A[i-1]已經按關鍵碼值排好序。所謂折半比較，就是在插入A[i]時，取A[i-1/2]的關鍵碼值與A[i]的關鍵碼值進行比較，如果A[i]的關鍵碼值小于A[i-1/2]的關鍵碼值，則說明A[i]只能插入A[0]到A[i-1/2]之間，故可以在A[0]到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的取值較大，每組內記錄數較少，所以排序比較快。隨著不斷增大，每組內的記錄數逐步增多，但由于已經按排好序，因此排序速度也比較快。

插入排序過程詳解

從有序數列和無序數列{a2,a3，…，an}開始進行排序；處理第i個元素時（i=2,3，…，n），數列{a1,a2，…，ai-1}是已有序的，而數列{ai,ai+1，…，an}是無序的。用ai與ai-1，ai-2，…，a1進行比較，找出合適的位置將ai插入；重復第二步，共進行n-i次插入處理，數列全部有序。

注意事項：

折半插入排序是對直接插入排序的一種改良方式，在直接插入排序中，每次向已排序序列中插入元素時，都要去尋找插入元素的合適位置，但是這個過程是從已排序序列的最后開始逐一去比較大小的，這其實很是浪費，因為每比較一次緊接著就是元素的移動。

直接插入排序的介紹

在日常生活中，經常碰到這樣一類排序問題：把新的數據插入到已經排好的數據列中。例如：一組從小到大排好順序的數據列{1,2,3,4,5,6,7,9,10}，通常稱之為有序列，我們用序號1,2,3，…表示數據的位置，欲把一個新的數據8插入到上述序列中。完成這個工作的步驟：①確定數據“8”在原有序列中應該占有的位置序號。數據“8”所處的位置應滿足小于或等于該位置右邊所有的數據，大于其左邊位置上所有的數據。②將這個位置空出來，將數據“8”插進去。直接插入排序(straight inrtion sort)的做法是：每次從無序表中取出第一個元素，把它插入到有序表的合適位置，使有序表仍然有序。第一趟比較前兩個數，然后把第二個數按大小插入到有序表中； 第二趟把第三個數據與前兩個數從后向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以后就完成了整個排序過程。直接插入排序是由兩層嵌套循環組成的。外層循環標識并決定待比較的數值。內層循環為待比較數值確定其最終位置。直接插入排序是將待比較的數值與它的前一個數值進行比較，所以外層循環是從第二個數值開始的。當前一數值比待比較數值大的情況下繼續循環比較，直到找到比待比較數值小的并將待比較數值置入其后一位置，結束該次循環。插入排序的基本方法是：每步將一個待排序的記錄按其關鍵字的大小插到前面已經排序的序列中的適當位置，直到全部記錄插入完畢為止。

插入排序的設計步驟

算法設計有很多方法。插入排序使用的是增量（incremental）方法；在排好子數組A[1..j-1]后，將A[j]插入，形成排好序的子數組A[1..j]；
步驟
⒈從有序數列和無序數列{a2,a3，…，an}開始進行排序；
⒉處理第i個元素時（i=2,3，…，n），數列{a1,a2，…，ai-1}是已有序的，而數列{ai,ai+1，…，an}是無序的。用ai與ai-1，a i-2，…，a1進行比較，找出合適的位置將ai插入；
⒊重復第二步，共進行n-i次插入處理，數列全部有序。
思路
假定這個數組的序是排好的，然后從頭往后，如果有數比當前外層元素的值大，則將這個數的位置往后挪，直到當前外層元素的值大于或等于它前面的位置為止.這具算法在排完前k個數之后，可以保證a[1…k]是局部有序的，保證了插入過程的正確性.