• 代码：
•  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]; // 线性关系
   }
• 总结：是折半插入排序的改进，目的是减少排序过程中移动记录的次数，但为此需要n个记录的辅助空间。
• 算法思想：

评论