/* bo10-1.c 順序表插入排序的函數(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]; /* 復制為哨兵 */
       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; /* 插入點在低半區 */
       else
         low=m+1; /* 插入點在高半區 */
     }
     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]; /* 設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數組的元素) */
       first=(first-1+(*L).length)%(*L).length; /* 設d為循環向量 */
       d[first]=(*L).r[i];
     }
     else if((*L).r[i].key>d[final].key)
     { /* 待插記錄大于d中最大值，插到d[final]之后(不需移動d數組的元素) */
       final=final+1;
       d[final]=(*L).r[i];
     }
     else
     { /* 待插記錄大于d中最小值，小于d中最大值，插到d的中間(需要移動d數組的元素) */
       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]; /* 線性關系 */
 }