1.序言
這是經典排序算法系列的第一篇，我們首先從插入排序算法開始。這是一個對少量元素排序的有效算法，主要包括：直接插入排序，二分插入排序（又稱折半插入排序），連結清單插入排序，希爾排序（又稱縮小增量排序）。對于每一種插入排序算法，我都闡述了其基本思想，給出了該算法的代碼，并分析了代碼的運作效率，最後對各種插入排序進行了比較。
2.直接插入排序
2.1基本思想
當插入第i (i >=1) 個對象時, 前面的V[0], V[1], …, V[i-1]已經排好序。這時, 用V[i]的排序碼與V[i-1], V[i-2], …的排序碼順序進行比較, 找到插入位置即将V[i]插入, 原來位置上的對象向後順移。
2.2算法思路
為了幫助我們了解直接插入排序算法，我們可以從生活中的一個執行個體來了解直接插入排序算法的基本思想。該算法的機理與我們在生活中打牌時，理牌的做法差不多。在剛開始摸牌的時候，我們的左手是空的，牌面朝下放在桌子上的，接着，一次從桌上摸起一張牌，并将它插入到左手一把牌中正确的位置，為了找到這張牌的正确位置，我們需将它與手中已有的牌從右到左地進行比較，如下圖所示。無論在什麼時候，手中的牌都是已經排好序的，而這些牌都是原先桌上那副牌裡最頂上的一些牌。
假如現在我們要對一個數組a={5,2,4,6,1,3}用直接插入排序算法進行排序，其基本思路如上圖所示，實作該算法的核心代碼如下：
//直接插入排序算法
void straightInsertSort(int *a, int length)
{
int i, j;
int temp;
for(i = 1; i <= length; i++)
{
//存儲要插入的數值
temp = a[i];
//從有序部分右端到左端逐個比較
for(j = i-1; j >= 0 && a[i] < a[j]; j--)
{
//當要插入的數值比數組值a[j]小則将a[j]後移一位
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
2.3代碼效率
在分析插入排序時，我們既考慮了最好情況，也考慮了最壞情況。可以明顯看出，最好情況則是輸入已經排好序的數組，最壞情況則是輸入按照逆序排序的數組。在最好情況下，比較次數時間複雜度為常量O(1)，進行了n輪，是以最好情況下的時間複雜度為O(n)；在最壞情況下，比較次數和移動次數的時間複雜度為O(n)，進行了n輪，是以最壞情況下的時間複雜度為O(n^2)。可以看出直接插入排序算法是一種穩定的排序算法，并且适合大部分有序的輸入數組。還有一點要注意的是，直接插入排序算法并不适合大數量級排序。
3.折半插入排序
3.1基本思想
二分插入排序（binary insertion sort）又稱折半插入排序，是對插入排序算法的一種改進，由于排序算法過程中，就是不斷的依次将元素插入前面已排好序的序列中。由于前半部分為已排好序的數列，這樣我們不用按順序依次尋找插入點，可以采用折半查找的方法來加快尋找插入點的速度。
假設待排序的記錄存放在數組V[1..n]中。初始時，V[1..i-1]為有序區，V[i..n]為無序區。在插入第i個元素時，對前面的0～i-1元素進行折半，先跟他們中間的那個元素比，如果小，則對前半再進行折半，否則對後半進行折半，直到left>right，然後再把第i個元素前1位與目标位置之間的所有元素後移，再把第i個元素放在目标位置上。
3.2算法思路
折半插入排序算法的具體操作為：在将一個新元素插入已排好序的數組的過程中，尋找插入點時，将待插入區域的首元素設定為a[low]，末元素設定為a[high]，則輪比較時将待插入元素與a[m],其中m=(low+high)/2相比較,如果比參考元素小，則選擇a[low]到a[m-1]為新的插入區域(即high=m-1)，否則選擇a[m+1]到a[high]為新的插入區域（即low=m+1），如此直至low<=high不成立，即将此位置之後所有元素後移一位，并将新元素插入a[high+1]。實作二分插入排序的核心代碼如下：
//折半插入排序算法
void binaryInsertSort(int *a, int length)
{
int i, j;
int temp;
int low, middle, high;
//周遊數組查找有序部分和無序部分臨界點
for(i = 1; i < length; i++)
{
if(a[i] < a[i-1])
{
//存儲要插入的數值
temp = a[i];
//存儲要插入的有序數組的左端下标值
low = 0;
//存儲要插入的有序數組的右端下标值
high = i-1;
//尋找要插入的位置
while(low <= high)
{
middle = (low+high)/2;
//插入值若比有序數組中間值小則插入位置在左端，否則在右端
if(a[i] < a[middle])
{
high = middle-1;
}
else
{
low = middle+1;
}
}
//後移比插入值大的有序數組部分
for(j = i; j > high; j--)
{
a[j] = a[j-1];
}
//插入數值
a[high] = temp;
}
}
}
3.3代碼效率
折半搜尋比順序搜尋查找快, 是以折半插入排序就平均性能來說比直接插入排序要快。它所需的排序碼比較次數與待排序對象序列的初始排列無關, 僅依賴于對象個數。在插入第i個對象時， 需要經過logi+1 次排序碼比較, 才能确定它應插入的位置。是以, 将 n 個對象(為推導友善, 設為 n=2k )用折半插入排序所進行的排序碼比較次數為n*logn。與直接插入排序算法相同，折半插入排序算法是一種穩定的算法。
當 n 較大時, 折半插入排序的總排序碼比較次數比直接插入排序的最壞情況要好得多, 但比其最好情況要差。在對象的初始排列已經按排序碼排好序或接近有序時, 直接插入排序比折半插入排序執行的排序碼比較次數要少。折半插入排序的對象移動次數與直接插入排序相同, 依賴于對象的初始排列。
4.連結清單插入排序
4.1基本思想
對于數組中的一組對象V[1], …, V[n], 若V[1], …, V[i-1]已經通過指針link, 按其排序碼從小到大連結起來。現要插入V[i], i = 2, 3, …, n, 則必須在前面i-1個連結起來的對象當中, 循鍊檢測比較, 找到 V[i] 應插入的位置，把V[i] 鍊入, 并修改相應連結指針。進而得到V[1], …, V[i]的一個通過指針排好的連結清單。
4.2算法思路
連結清單插入排序算法的機理和直接插入算法類似，将連結清單分為有序部分和無序部分，将無序部分的節點與有序部分連結清單從頭節點到尾節點逐個比較，找出最佳位置插入新增節點即可，實作該算法的核心代碼如下：
//連結清單插入排序
//定義連結清單結點類型
typedef struct Node
{
ElemType data;
struct Node * next;
}Node;
void linkedInsertSort(List L)
{
Node *head=L;
//有序區的尾節點
Node *tail;
//無序區的首元節點
Node *unsorted;
//用來記錄插入位置的前驅
NOde *pre;
//作為有序區的遊标
Node *p;
if(head->next!=NULL)
{
tail=head->next;
while(tail->next!=NULL)
{
unsorted=tail->next;
pre=head;
p=pre->next;
//逐個比較尋找插入位置
while(unsorted->data<=p->data&&unsorted!=p)
{
pre=p;
p=p->next;
}
if(p==unsorted)
{
tail=unsorted;
}
else
{
tail->next=unsorted->next;
pre->next=unsorted;
unsorted->next=p;
}
}
}
else
{
printf("the list is NULL!\n");
}
}
4.3代碼效率
使用連結清單插入排序，每插入一個對象，最大排序碼比較次數等于連結清單中已排好序的對象個數，最小排序碼比較次數為1。故總的排序碼比較次數最小為 n-1，最大為n*(n-1)/2，算法在unsorted->data== p->data時,将unsorted插在p的後面，是以，連結清單插入排序方法是穩定的。
5.希爾排序
5.1基本思想
希爾排序方法又稱為縮小增量排序。該方法的基本思想是：設待排序對象序列有n個對象，首先取一個整數gap<n作為間隔，将全部對象分為gap個子序列，所有距離為gap的對象放在同一個子序列中，在每一個子序列中分别施行直接插入排序。然後縮小間隔gap，例如取gap=gap/2，重複上述的子序列劃分和排序工作。直到最後取gap=1，将所有對象放在同一個序列中排序為止。
5.2算法思路
為了讓我們更好的了解希爾排序，我現在給大家示範一個執行個體，假如我們對數組a={49,38,65,97,76,13,27,49*,55,04}進行希爾排序，具體步驟如下圖所示：
由上面的結果我們可以很清楚的了解到希爾排序的機理，并且可以知道希爾排序是一種不穩定的排序。根據上面的步驟我們知道希爾排序就是将數組進行多次分組并使用直接插入算法排序，直接插入排序算法是每比較一次就移動1位，而在希爾排序中我們每比較一次移動d位就剛好，于是我們很容易對直接插入排序算法進行改造就可以實作希爾排序算法，下面是實作希爾排序算法的核心代碼：
//希爾排序算法
void ShellSort(int *a, int n, int d)
{
int i, j;
int temp;
while(d > 0)
{
for(i = d+1; i < n; i++)
{
//存儲要插入的值
temp = a[i];
//周遊分組尋找要插入的位置
for(j = i-d; j >=0 && a[i] < a[j]; j = j-d)
{
a[j+d] = a[j];
}
a[j+d] = temp;
}
//減小間隔值
d = d/2;
}
}
5.3代碼效率
開始時d的值較大，每組中的元素較少，排序速度較快；随着排序進展，d值逐漸變小，每組中元素的個數逐漸變多，由于前面工作的基礎，大多數元素已基本有序，是以排序速度仍然很快。時間效率：至今數學上尚未解決的難題。 約為O(n^1.3)。希爾排序是一種不穩定的排序算法。
希爾排序是基于插入排序的一種算法， 在此算法基礎之上增加了一個新的特性，提高了效率。希爾排序的時間複雜度為 O(N*(logN)^2)， 沒有快速排序算法快 O(N*(logN))，是以中等大小規模表現良好，對規模非常大的資料排序不是 最優選擇。但是比O(N2）複雜度的算法快得多。并且希爾排序非常容易實作，算法代碼短而簡單。 此外，希爾算法在最壞的情況下和平均情況下執行效率相差不是很多，與此同時快速排序在最壞 的情況下執行的效率會非常差。
6.參考資料
《算法導論》機械工業出版社 Thomas H.Cormen Charles E.Leiserson Ronlad L.Rivest Clifford Stein
《資料結構》清華大學出版社 李春葆 尹為民
7.學習心得
在學習插入排序算法的時候，我加深了對排序算法的一些了解。我覺得在插入排序算法裡面應該重點了解直接插入排序算法，後面的幾種算法都是由直接插入排序算法變化或改造就可以得到，還有在學習算法的時候應該注意多思考，多動手，讀者應該試着在了解其基本思想之後動手實作其算法的核心代碼，畢竟實踐出真知，隻有自己實踐并了解了，這個算法才是你的算法。
（注：代碼是本人所寫，如有錯誤，請多多指教，重在交流！）