// bo10-1.cpp 順序表插入排序的函數(shù)(3個)
 void InsertSort(SqList &L)
 { // 對順序表L作直接插入排序。算法10.1
   int i,j;
   for(i=2;i<=L.length;++i)
     if LT(L.r[i].key,L.r[i-1].key) // "<",需將L.r[i]插入有序子表
     {
       L.r[0]=L.r[i]; // 復(fù)制為哨兵
       for(j=i-1;LT(L.r[0].key,L.r[j].key);--j)
         L.r[j+1]=L.r[j]; // 記錄后移
       L.r[j+1]=L.r[0]; // 插入到正確位置
     }
 }

 void BInsertSort(SqList &L)
 { // 對順序表L作折半插入排序。算法10.2
   int i,j,m,low,high;
   for(i=2;i<=L.length;++i)
   {
     L.r[0]=L.r[i]; // 將L.r[i]暫存到L.r[0]
     low=1;
     high=i-1;
     while(low<=high)
     { // 在r[low..high]中折半查找有序插入的位置
       m=(low+high)/2; // 折半
       if LT(L.r[0].key,L.r[m].key)
         high=m-1; // 插入點在低半?yún)^(qū)
       else
         low=m+1; // 插入點在高半?yún)^(qū)
     }
     for(j=i-1;j>=high+1;--j)
       L.r[j+1]=L.r[j]; // 記錄后移
     L.r[high+1]=L.r[0]; // 插入
   }
 }

 void P2_InsertSort(SqList &L)
 { // 2_路插入排序
   int i,j,first,final;
   RedType *d;
   d=(RedType*)malloc(L.length*sizeof(RedType)); // 生成L.length個記錄的臨時空間
   d[0]=L.r[1]; // 設(shè)L的第1個記錄為d中排好序的記錄(在位置[0])
   first=final=0; // first、final分別指示d中排好序的記錄的第1個和最后1個記錄的位置
   for(i=2;i<=L.length;++i)
   { // 依次將L的第2個～最后1個記錄插入d中
     if(L.r[i].key<d[first].key)
     { // 待插記錄小于d中最小值，插到d[first]之前(不需移動d數(shù)組的元素)
       first=(first-1+L.length)%L.length; // 設(shè)d為循環(huán)向量
       d[first]=L.r[i];
     }
     else if(L.r[i].key>d[final].key)
     { // 待插記錄大于d中最大值，插到d[final]之后(不需移動d數(shù)組的元素)
       final=final+1;
       d[final]=L.r[i];
     }
     else
     { // 待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動d數(shù)組的元素)
       j=final++; // 移動d的尾部元素以便按序插入記錄
       while(L.r[i].key<d[j].key)
       {
         d[(j+1)%L.length]=d[j];
         j=(j-1+L.length)%L.length;
       }
       d[j+1]=L.r[i];
     }
   }
   for(i=1;i<=L.length;i++) // 把d賦給L.r
     L.r[i]=d[(i+first-1)%L.length]; // 線性關(guān)系
 }