10.24.c

数据结构习题及答案

10.24③ 试编写教材10.2.2节中所述2-路插入排序的算法。

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

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

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