void InsertSort(int A[],int n) {
    int i,j;
    for(i=2; i<=n; i++) {//依次将A[2]~A[n]插入到前面已经排序的序列
        if(A[i]<A[i-1]) {//若A[i]的关键码小于其前驱，需要将A[i]插入有序表
            A[0]=A[i];//复制为哨兵，A[0]不存放元素
            for(j=i-1; A[0]<A[j]; --j)//从后往前查找待插入的位置
                A[j+1]=A[j];//向后挪位
            A[j+1]=A[0];//复制到插入位置
        }
    }
}

void InsertSort(int A[],int n) {
    int i,j,low,high,mid;
    for(i=2; i<=n; i++) {//依次将A[2]~A[n]插入到前面已排序序列 
        A[0]=A[i];//将A[i]暂存到A[0] 
        low=1;high=i-1;//设置折半查找的范围 
        while(low<=high) {//半查找（默认递增有序） 
            mid=(low+high)/2;
            if(A[0]>A[mid])low=mid+1;
            else
                high=mid-1;
        }
        for(j=i-1; j>=high+1; j--)
            A[j+1]=A[j];//统一后移元素，空出插入位置 
        A[high+1]=A[0];//插入操作 
    }
}

void ShellSort(int A[],int n) {
    int i,j;//A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到 
    for(int d=n/2; d>=1; d=d/2) {//步长变化 
        for( i=d+1; i<=n; i++) {
            if(A[i]<A[i-d]) {//需将A[i]插入有序增量子表 
                A[0]=A[i];//暂存在A[0] 
                for(j=i-d; j>0&&A[0]<A[j]; j-=d)
                    A[j+d]=A[j];//记录后移，查找插入位置 
                A[j+d]=A[0];//插入 
            }
        }
    }
}