#include<stdio.h>
#include<iostream.h>
#include<stdlib.h>
typedef  int  keytype;
typedef  char infotype;
const maxsize=20;
typedef  struct
{
      keytype key;//关键字项
      infotype  otherinfo;//其他数据项
}rcdtype;//记录类型
typedef struct
{
      rcdtype r[maxsize+1];//a[0]闲置作为不能别标志的哨兵
      int length;     //顺序表排序的记录空间r[1,length]
}sqlist;// 顺序表类型
void  insertsort(sqlist &l)
{
    //对顺序表l做插入排序
    int i,j;
    for(i=2;i<=l.length;++i)
    {
         if(l.r[i].key<l.r[i-1].key)//当<时，才需要将l.r[i].key插入有序序列中
         {
         l.r[0]=l.r[i];//复制为哨兵
          }
          for(j=i-1;l.r[0].key<l.r[j].key;--j)
          {
         l.r[j+1]=l.r[j];//记录后移
          }
              l.r[j+1]=l.r[0];//插入到正确位置
     }
}
int main()
{
      sqlist l;
      int i;
      l.length=7;
      l.r[1].key=10;l.r[2].key=15;
      l.r[3].key=20;l.r[4].key=30;
      l.r[5].key=25;l.r[6].key=36;
      l.r[7].key=50;
      cout<<"排序后的顺序表："<<endl;
      insertsort(l);
      for(i=1;i<l.length+1;i++)
      {
          printf("%4d",l.r[i].key);
      }
      cout<<endl<<endl;
      return 0;