直接插入排序：
算法思想：假设待排序的记录存放在数组R[1……n]中，初始时，i=1,R[1]自成一个有序区，无序区为R[2……n].然后从i=2起直到i=n,依次将R[i]插入当前的有序区R[1...n-1]中，最后，生成含n个的记录的有序区。
算法实现：
void insertsort(Reqlist R)
{
int i,j;
for(i=2;i<=n;i++)//从第二个数字开始插入排序
{
R[0]=R[i];//R[0]作为哨兵，一方面暂存数据，另一方面，检测下标j是否越界（2）
j=i-1;
while(R[0].key<R[j].key)//（2）
{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
}
算法复杂度计算：
当待排序的n个数据为正序时候，算法复杂度为O(n);
当待排序的n个数据为反序时候，算法复杂度为O(n^2);
当待排序的n个数据为乱序时候，算法复杂度为O(n^2);
原文：http://www.cnblogs.com/hai5111/p/6238323.html