10.23.c

数据结构习题及答案

10.23②  试以L.r[k+1]作为监视哨改写教材10.2.1节
中给出的直接插入排序算法。其中，L.r[1..k]为待排
序记录且k<MAXSIZE。

实现下列函数：
void InsertSort(SqList &L);

顺序表的类型SqList定义如下：
typedef struct {
   KeyType key; 
   ... 
} RedType;

typedef struct {
   RedType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元
   int     length;
} SqList;
void InsertSort(SqList &L)
{
  int i,j,k;
  k=L.length;
  for(i=k-1;i>=1;i--)
    if(L.r[i].key>L.r[i+1].key)
     {L.r[k+1]=L.r[i];
      L.r[i]=L.r[i+1];
      for(j=i+1;L.r[k+1].key>L.r[j].key;++j) L.r[j-1]=L.r[j];
      L.r[j-1]=L.r[k+1];
      }   
}