插入排序的基本思想：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。
1. 直接插入排序
void InsertSort(SqList &L)
{ //对顺序表L做直接插入排序
int i,j;
for(i=2;i<=L.i8length;i++)
{
if (L.r[i].key<L.r[i-1].key) /* 需将r[i]插入有序子表 */
{
L.r[0]=L.r[i]; /* 将待插入的记录暂存到监视哨中 */
L.r[i] = L.r[i-1];//r[i-1]后移
for(j=i-2;L.r[0].key<L.r[j].key;j--)
L.r[j+1]=L.r[j]; /* 记录逐个后移直到找到插入位置 */
L.r[j+1]=L.r[0]; /* 将r[0]即原r[i],插入到正确位置 */
}
}
}
复杂度分析
从空间上来看，它只需要一个记录的辅助空间r[0]，空间复杂度O(1)。
最好的情况，也就是要排序的表本身就是有序的，比如纸牌拿到后就是{2.3.4.5.6}时，那么我们比较次数，其实就是代码中每个L.r[i]与L.r[i-1]的比较，共比较了n-1次，由于每次都是L.r[i]＞L.r[i-1]，因此没有移动的记录，时间复杂度为O(n)。
当最坏的情况，即待排序表是逆序的情况，比如{6.5.4.3.2}，此时需要比较次，而记录的移动次数也达到最大值次。
如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为(n^2)/4次。因此，我们得出直接插入排序法的时间复杂度为O(n^2)。 从这里也看出，同样的O(n^2)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。
2. 折半插入排序
void BInsertSort(SqList &L)
{
for(i=2;i<L.length;i++)
{
L.r[0] = L.r[i];//将待插入的记录暂存到监察哨中
low=1;high=i-1;//置查找区间初值
while(low<high)//在r[low..high]中折半查找插入位置
{
m=(low+high)/2;//折半
if(L.r[0].key < L.r[m].key) high = m-1;
else low = m+1;
}
for(j=i-1;j>=high+1;--j) L.r[j+1] =L.r[j];//记录后移
L.r[high+1] =L.r[o];//将r[0]即原r[i]，插入到正确位置
}
}
3. 希尔排序
希尔排序又称为缩小增量排序，是对直接插入排序方法的改进。
希尔排序实质上是采用分组插入的方法。先将整个待排序记录分割成几组，从而减少参与直接插入排序的数据量，对每个分组分别进行直接插入排序，然后增加每组的数据量，重新分组。这样当经过几次分组排序以后，整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序。
希尔对记录的分组，不是简单地逐段分割，而是相隔某个增量的记录分成一组。
1.第一趟取增量d1(d1<n)把全部记录分成d1个分组，所有间隔为d1的记录分为同一组，在各组中进行直接插入排序。
- 第二趟取增量d2(d2<d1)，重复上述分组和排序。
依次类推，直到所取增量d1=1,所有记录在同一组进行直接排序为止。
void ShellInsert(SqList &L,int dk)
{//对顺序表L做一趟增量是dk的希尔插入排序
for(i= dk+1;i<=L.length;i++)
if(L.r[i].key < L.r[i=dk].key) //需将L.r[i]插入有序增量子表
{
L.r[0] = L.r[i];//暂存
for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
L.r[j+dk] = L.r[j];//记录后移，直到找到插入位置
L.r[j+dk] = L.r[0];//将r[o]即原r[i],插入到正确位置
}
}
void ShellSort(SqList &L,int dt[],int t)
{//按增量dt[0..t-1]对顺序表L做t趟希尔排序
for(k=0;k<t;++k)
ShellInsert(L,dt[k]);//一趟增量为dt[t]的希尔插入排序
}
