插入排序是一種簡(jiǎn)單的排序方法，因?yàn)榈膶?shí)現(xiàn)比較簡(jiǎn)單，所以在數(shù)據(jù)量較少時(shí)應(yīng)用很廣泛。插入排序根據(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(bǔ)[0]設(shè)置為臨時(shí)數(shù)據(jù)存放處（即原數(shù)組中a[0]未存儲(chǔ)元素），這樣就可以少進(jìn)行一些判斷，在數(shù)據(jù)量較大時(shí)可以節(jié)省一些時(shí)間，算法如下：
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;
}
}
折半插入排序法
由于插入排序的基本操作是在一個(gè)有序表中進(jìn)行查找和插入，則這個(gè)查找操作可以利用折半查找來(lái)實(shí)現(xiàn)。但是折半插入排序僅減少了元素間的比較次數(shù)，而元素的移動(dòng)次數(shù)不變，因此折半插入排序法的時(shí)間復(fù)雜度仍為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
}
希爾排序法
希爾排序法又稱縮小增量排序法，它也是插入排序類的方法，但在時(shí)間效率上較前面幾種插入排序算法有較大的改進(jìn)。
希爾排序法通過(guò)比較相距一定間隔的元素來(lái)工作，各趟比較所用的距離隨著算法的進(jìn)行而減小，直到比較相鄰元素的最后一趟排序?yàn)橹?。算法如下?br>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-路插入排序和表插入排序，有意者請(qǐng)補(bǔ)上！謝謝！