2-lu.txt

数据结构中的所涉及到的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)
{SqList q;
 q.length=L.length; 
 int first=L.length+1,final=1,fl,ft=0,e,i;
 if(L.length>1)
  {q.r[1]=L.r[1];
   for(i=2;i<=L.length;i++)
     {if(L.r[i].key>=q.r[1].key)
        {fl=1;
         while(L.r[i].key>=q.r[fl].key&&fl<=final) ++fl;
         if(L.r[i].key<q.r[fl].key)
           {q.r[final+1]=q.r[final];
            for(e=final-1;e>=fl;e--)
              q.r[e+1]=q.r[e];
           }  
         q.r[fl]=L.r[i];
         ++final;
        }
      else
        {if(ft==0)
           {q.r[L.length]=L.r[i];
            ft=L.length;
           } 
         else
         {ft=L.length;
          while(L.r[i].key<=q.r[ft].key&&ft>=first) --ft;
          if(L.r[i].key>q.r[ft].key)
            {q.r[first-1]=q.r[first];
             for(e=first+1;e<=ft;e++)
               q.r[e-1]=q.r[e];
            }
           q.r[ft]=L.r[i];           
         }
         --first;
        } 
     }
   }  
  for(e=first,i=1;e<=L.length;e++,i++)
        L.r[i]=q.r[e];
   for(e=1;e<=final;e++,i++)
        L.r[i]=q.r[e];     
}