直接插入排序，将一个记录插入到一个已经排好序的有序表中。 插入排序的思想：插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。当然，刚开始这个有序的小序列只有1个元素， 就是第一个元素。比较是从有 序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面， 否则一直往前找直到找到它该插入的位置。如果碰见一 个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。 所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所 以插入排序是稳定的。 下面考虑使用哨兵和不使用哨兵的情况： 未引入哨兵的情况：

#include 
     
      #define MAXSIZE 9        /* 用于要排序数组个数最大值，可根据需要修改 */typedef struct {    int r[MAXSIZE];        int length;            /* 用于记录顺序表的长度 */}SqList;/* 交换L中数组r的下标为i和j的值 */void swap(SqList * L, int i, int j){    int temp=L->r[i];    L->r[i]=L->r[j];    L->r[j]=temp;}//打印L中数组的值void print(SqList L){    int i;    for(i=0; i < L.length; i++)        printf("%3d",L.r[i]);    printf("\n");}//直接插入排序，将一个记录插入到一个已经排好序的有序表中void insertsort(SqList * L){    int i,j,temp=0;    for(i=1; i
      
       length; i++){        if(L->r[i] < L->r[i-1]){            temp=L->r[i];       //此处没有用哨兵的形式,设置哨兵的情况下，不用每次比较j>=0,提高算法效率            for(j=i-1; j>=0 && L->r[j]>temp; j--){                L->r[j+1]=L->r[j];    //记录后移            }            L->r[j+1]=temp;            //插入到正确的位置        }    }}int main(){    SqList L;    int num[10]    ={
   5,3,2,4,6,1,7,8,9};        for(int i=0; i<9; i++){        L.r[i]=num[i];    }//注意给数组赋值的方法    L.length=9;    //直接插入选择排序    insertsort(&L);    print(L);    return 0;} 引入哨兵的情况： L->r[1]到L->[n]存放待排序的数据，将L->[0]作为哨兵。
      
     

/* 对顺序表L作直接插入排序 */void InsertSort(SqList *L){     int i,j;    for(i=2;i<=L->length;i++)    {        if (L->r[i]
      
       r[i-1]) /* 需将L->r[i]插入有序子表 */        {            L->r[0]=L->r[i]; /* 设置哨兵 */            for(j=i-1;L->r[j]>L->r[0];j--)                L->r[j+1]=L->r[j]; /* 记录后移 */            L->r[j+1]=L->r[0]; /* 插入到正确位置 */        }    }}
      

算法中引进的附加记录R[0]称监视哨或哨兵(Sentinel)。

哨兵有两个作用：

① 进人查找(插入位置)循环之前，它保存了R[i]的副本，使不致于因记录后移而丢失R[i]的内容；

②

它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R[0].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。

注意：

① 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。

【例】单链表中的头结点实际上是一个哨兵

② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以

不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。

时间复杂度O(n^2);