2路插入排序

2路插入排序
2路插入是在折半插入的基础上进行改进。
折半插入在原先直接插入的基础上改进，通过折半查找，以较少的比较次数就找到了要插入的位置，但是在插入的过程中仍然没有减少移动次数，所以2路插入在此基础上改进，减少了移动次数，但是仍然并没有避免移动记录（如果要避免的话还是得改变存储结构）
那么如何减少的移动次数？？？
常规的一个数组{2, 7, 8,10,15 ,29,30, 40,50,66,70,80}，如果插入9，那么按照常规的折半查找后，需要移动记录9次，这是因为我们只能够在一个方向上插入。
因此我们设定一个辅助数组A，大小是原来数组相同的大小，将A[0]设为第一个原数组第一个数，通过设置first和final指向整个有序序列的最小值和最大值，即为序列的尾部和头部，并且将其设置位一个循环数组，这样就可以进行双端插入。此时原数组只需往左边移动3次。

之所以能减少移动次数的原因在于可以往2个方向移动记录，故称为2路插入。
A[0]的前面是个有序序列，后面也是有序序列，整个也是有序序列

具体操作思路：
1.将原数组第一个元素赋值给A[0],作为标志元素
2.按顺序依次插入剩下的原数组的元素

1. 将带插入元素与第一个进行比较，偌大于A[0],则插入A[0]前面的有序序列，否则插入后面的有序序列
2. 对前面的有序序列或后面的有序序列进行折半查找
3. 查找到插入位置后进行记录的移动，分别往first方向前移和往final方向移动
4. 插入记录

3.将排序好的A数组的数据从first到final，按次序赋值回原数组。

代码如下

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100

typedef struct{
   int Score[MAXSIZE];
   int length;
}Sqlist;

int HalfInsertLocal(int a[],int length,int key){
      int low,high,m;
      low=0;high=length-1;
      while(low<=high){
        m=(low+high)/2;
        if(*(a+m)<key)
            low=m+1;
        else
            high=m-1;
      }
      return high+1;
}

void TwoPathInsert(Sqlist *L){
    int A[12]={0};
    int first=0,final=0;
    int j=0,k=0;int cur;
    A[0]=L->Score[0];
    for(int i=1;i<=L->length-1;i++){
          if(L->Score[i]>=A[0]){
            if(L->Score[i]>=A[final]){
                 A[++final]=L->Score[i];
                 j++;
            }
           else{
              cur=HalfInsertLocal(A,j+1,L->Score[i]);
              for(int g=final;g>=cur;g--)
                  A[g+1]=A[g];
              *(A+cur)=L->Score[i];
              j++;
             final++;
          }
          }
        else{
            if(L->Score[i]<A[first]){
                first=(first-1+L->length)%(L->length);
                A[first]=L->Score[i];
                k++;
            }
            else{
                cur=HalfInsertLocal(&A[first],k,L->Score[i]);
                cur--;
                for (int h=first;h<=(first+cur);h++)
                    A[h-1]=A[h];
                A[first+cur]=L->Score[i];
                first--;
                k++;
            }
        }
    }
    for(int i=0;i<=L->length-1;i++)
    {
        cur=(first+i)%(L->length);
        L->Score[i]=A[cur];
    }
    return;
}

int main()
{
    Sqlist L;
    L.length=0;
    for(int i=0;i<=11;i++,L.length++)
          scanf("%d",&L.Score[i]);
    TwoPathInsert(&L);
    for(int i=0;i<=11;i++)
          printf("%d
",L.Score[i]);
    return 0;
}