算法排序之插入排序
基本思想
一般來說，插入排序都采用in-place在數組上實現。具體算法描述如下：
從第一個元素開始，該元素可以認為已經被排序
取出下一個元素，在已經排序的元素序列中從後向前掃描
如果該元素（已排序）大於新元素，將該元素移到下一位置
重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
將新元素插入到該位置後
重復步驟2~5
動態演示
使用插入排序為一列數字進行排序的過程
時間復雜度分析
如果目標是把n個元素的序列升序排列，那麼采用插入排序存在最好情況和最壞情況。最好情況就是，序列已經是升序排列了，在這種情況下，需要進行的比較操作需(n-1)次即可。最壞情況就是，序列是降序排列，那麼此時需要進行的比較共有n(n-1)/2次。插入排序的賦值操作是比較操作的次數減去(n-1)次。平均來說插入排序算法復雜度為O(n2)。因而，插入排序不適合對於數據量比較大的排序應用。但是，如果需要排序的數據量很小，例如，量級小於千，那麼插入排序還是一個不錯的選擇。 插入排序在工業級庫中也有著廣泛的應用，在STL的sort算法和stdlib的qsort算法中，都將插入排序作為快速排序的補充，用於少量元素的排序（通常為8個或以下）。
算法改進
一.如果比較操作的代價比交換操作大的話，可以采用二分查找法來減少比較操作的數目。該算法可以認為是插入排序的一個變種，稱為二分查找排序
二.查找比較操作和記錄移動操作交替地進行的方法
具體做法：
將待插入記錄R[i]的關鍵字從右向左依次與有序區中記錄R[j](j=i-1，i-2，…，1)的關鍵字進行比較：
① 若R[j]的關鍵字大於R[i]的關鍵字，則將R[j]後移一個位置；
②若R[j]的關鍵字小於或等於R[i]的關鍵字，則查找過程結束，j+1即為R[i]的插入位置。
關鍵字比R[i]的關鍵字大的記錄均已後移，所以j+1的位置已經騰空，只要將R[i]直接插入此位置即可完成一趟直接插入排序。
算法C實現
[cpp]
void insertion_sort(char array[], int first, int last)
{
int i,j;
int temp;
for (i = first+1; i<=last;i++)
{
temp = array[i];
j=i-1;
//與已排序的數逐一比較，大於temp時，該數向後移
while((j>=first) && (array[j] > temp)) //當first=0，j循環到-1時，由於[[短路求值]]，不會運算array[-1]
{
array[j+1] = array[j];
j--;
}
array[j+1] = temp; //被排序數放到正確的位置
}
}
