插入排序是一種簡單的排序方法，因為的實現(xiàn)比較簡單，所以在數(shù)據(jù)量較少時應用很廣泛。插入排序根據(jù)其插入的不同方式，可以分為直接插入排序，折半插入排序，2-路插入排序，表插入排序和希爾排序。在這里我將一一寫出各種插入排序的算法代碼。
直接插入排序
template <class T>
void InsertSort(T a[], int len)
{
int i, j;
T temp;
for (i=1; i<len; i++)
{
temp = a[i];
for (j=i-1; j>=0 && a[j]>temp; j--)//元素后移
a[j+1] = a[j];
a[j+1] = temp; //插入
}
}
有些算法把a[0]設置為臨時數(shù)據(jù)存放處（即原數(shù)組中a[0]未存儲元素），這樣就可以少進行一些判斷，在數(shù)據(jù)量較大時可以節(jié)省一些時間，算法如下：
template <class T>
void InsertSort(T a[], int len)
{
int i, j;
for (i=1; i<len; i++)
{
a[0] = a[i];
for (j=i-1; a[j]>temp; j--)
a[j+1] = a[j];
a[j+1] = temp;
}
}
折半插入排序法
由于插入排序的基本操作是在一個有序表中進行查找和插入，則這個查找操作可以利用折半查找來實現(xiàn)。但是折半插入排序僅減少了元素間的比較次數(shù)，而元素的移動次數(shù)不變，因此折半插入排序法的時間復雜度仍為O(n^2)。算法如下：
template <class T>
void HalfInsertSort(T a[], int len)
{
int i, j;
int low, high, mid;
T temp;
for (i=1; i<len; i++)
{
temp = a[i];
low = 0;
high = i - 1;
while (low <= high) //在a[low。。。high]中折半查找有序插入的位置
{
mid = (low + high) / 2;
if (a[mid] > temp)
high = mid - 1;
else
low = mid + 1;
} //while
for (j=i-1; j>high; j--)//元素后移
a[j+1] = a[j];
a[high+1] = temp; //插入
}//for
}
希爾排序法
希爾排序法又稱縮小增量排序法，它也是插入排序類的方法，但在時間效率上較前面幾種插入排序算法有較大的改進。
希爾排序法通過比較相距一定間隔的元素來工作，各趟比較所用的距離隨著算法的進行而減小，直到比較相鄰元素的最后一趟排序為止。算法如下：
template <class T>
void ShellSort(T a[], int len)
{
for (int increment=len/2; increment>0; increment/=2)
{
for (int i=increment; i<len; i++)
{
T temp = a[i];
int j = i;
for (; j>=increment; j-=increment)//元素后移
{
if (temp < a[j-increment])
a[j] = a[j-increment];
else
break;
}
a[j] = temp; //插入
}//for
}//for
}
注：缺2-路插入排序和表插入排序，有意者請補上！謝謝！