插入排序

//直接插入排序
void InsertSort(int *a, int n)//下标从0开始。
{
    int i;
    for(i=1;i<n;i++)
    {
        int j=i-1;
        int temp=a[i];
        while((a[j]>temp)&&(j>=0))
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=temp;
    }
    for(i=0;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}

void InsertSort(int *a, int n)//下标从1开始。
{
    int i;
    for(i=2;i<n;i++)
    {
        int j=i-1;
        a[0]=a[i];
        while((a[j]>a[0])&&(j>=1))
        {
            a[j+1]=a[j];
            j--;
        }
        a[j+1]=a[0];
    }
    for(i=1;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}

//折半插入排序
void BinaryInsertSort(int* a,int n)//下标从0开始。
{
    int i;
    int j;
    for(i=1;i<n;i++)
    {

        int low=0;
        int high=i-1;
        int temp=a[i];
        if(a[i]>=a[i-1])
            continue;
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(a[mid]>a[i])
                high=mid-1;
            else
                low=mid+1;
        }
        for(j=i-1;j>=low;j--)
        {
            a[j+1]=a[j];
        }
        a[low]=temp;
    }
    for(i=0;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}

void BinaryInsertSortx(int* a,int n)//下标从1开始。
{
    int i;
    int j;
    for(i=2;i<n;i++)
    {
        int low=1;
        int high=i-1;
        if(a[i]>=a[i-1])
            continue;
        a[0]=a[i];
        while(low<=high)
        {
            int mid=(low+high)/2;
            if(a[mid]>a[i])
                high=mid-1;
            else
                low=mid+1;
        }
        for(j=i-1;j>=low;j--)
        {
            a[j+1]=a[j];
        }
        a[low]=a[0];
    }
    for(i=1;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}