排序

int a[10];
n=10;
------------------------------------------------
//直接插入排序
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 InsertSortx(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');
}

------------------------------------------------
//选择排序
void SelectSort(int *a,int n)//从下标0开始。
{
    int i;
    int k;
    int j;
    for(i=0;i<n-1;i++)
    {
        k=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[k])
                k=j;
        }
        if(i!=k)
        {
            a[i]+=a[k];
            a[k]=a[i]-a[k];
            a[i]=a[i]-a[k];
        }
    }
    for(i=0;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}

void SelectSortx(int *a,int n)//从下标1开始。
{
    int i;
    int k;
    int j;
    for(i=1;i<n-1;i++)
    {
        k=i;
        for(j=i+1;j<n;j++)
        {
            if(a[j]<a[k])
                k=j;
        }
        if(i!=k)
        {
            a[i]+=a[k];
            a[k]=a[i]-a[k];
            a[i]=a[i]-a[k];
        }
    }
    for(i=1;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}

------------------------------------------------
//冒泡排序
void BubbleSort(int *a,int n)//下标从0开始
{
    int i;
    int j;
    for(i=0;i<n-1;i++)//n-1趟
    {
        for(j=0;j<n-i-1;j++)
        {
            if(a[j]>a[j+1])
            {
                a[j]+=a[j+1];
                a[j+1]=a[j]-a[j+1];
                a[j]=a[j]-a[j+1];
            }
        }
    }
    for(i=0;i<n;i++)
        printf("%d,",a[i]);
    putchar('\n');
}

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

------------------------------------------------
//堆排序，从下标1开始。
void Sift(int i,int n)//i为根节点，n为数组最大下标
{

    int k=2*i;//左孩子结点
    a[0]=a[i];
    while(k<=n)
    {
        if((k<n)&&(a[k]<a[k+1]))
            k++;
        if(a[0]<a[k])
        {
            a[i]=a[k];
            i=k;
            k=2*i;
        }
        else
            k=n+1;
    }
    a[i]=a[0];
}
void HeapSort(int *a,int n)//n为数组的大小，即0 ~ n-1
{
    int i;
    for(i=(n-1)/2;i>=1;i--)//初始建堆
        Sift(i,n-1);
    for(i=n-1;i>=2;i--)
    {
        a[0]=a[1];//交换a[1]和a[i]
        a[1]=a[i];
        a[i]=a[0];

        Sift(1,i-1);
    }
    for(i=1;i<n;i++)
    {
        printf("%d,",a[i]);
    }
    putchar('\n');
}

------------------------------------------------
//快速排序
int Partition(int i,int j)
{
    a[0]=a[i];
    while(i<j)
    {
        while((i<j)&&(a[0]<=a[j]))
            j--;
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while((i<j)&&(a[0]>=a[i]))
            i++;
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=a[0];
    return i;
}

void QuickSort()
{
    struct{
        int low;
        int high;
    }s[100];
    int t=1;
    int i;
    int k;
    s[t].low=1;
    s[t].high=9;

    do{
        int i,j;
        i=s[t].low;
        j=s[t].high;
        t--;
        k=Partition(i,j);
        if(k+1<j)
        {
            t++;
            s[t].low=k+1;
            s[t].high=j;
        }
        if(k-1>i)
        {
            t++;
            s[t].low=i;
            s[t].high=k-1;
        }
    }while(t>0);
    for(i=1;i<10;i++)
    {
        printf("%d,",a[i]);
    }
    putchar('\n');

}

void QuickSortx(int* a,int low,int high)
{
    int i=low;
    int j=high;
    a[0]=a[i];
    while(i<j)
    {
        while((i<j)&&(a[0]<=a[j]))
            j--;
        if(i<j)
        {
            a[i]=a[j];
            i++;
        }
        while((i<j)&&(a[0]>=a[i]))
            i++;
        if(i<j)
        {
            a[j]=a[i];
            j--;
        }
    }
    a[i]=a[0];
    if(low<i-1)
        QuickSortx(a,low,i-1);
    if(i+1<high)
        QuickSortx(a,i+1,high);
}

------------------------------------------------
//2路归并排序
void merge(int *r,int *s,int a,int b,int c)
{
    int i=a;
    int j=b+1;
    int k=a;
    while((i<=b)&&(j<=c))
    {
        if(r[i]<r[j])
            s[k++]=r[i++];
        else
            s[k++]=r[j++];
    }
    while(i<=b)
    {
        s[k++]=r[i++];
    }
    while(j<=c)
    {
        s[k++]=r[j++];
    }
}

int mergepass(int *r,int *s,int m,int n)
{
    int i=1,j;
    while(i+2*m-1<=n)
    {
        merge(r,s,i,i+m-1,i+2*m-1);
        i=i+2*m;
    }
    if(i+m-1<n)
        merge(r,s,i,i+m-1,n);
    else
        for(j=i;j<=n;j++)
            s[j]=r[j];
    return m*2;
}
void mergesort(int n)
{
    int m=1;
    while(m<n)
    {
        m=mergepass(a,b,m,n);
        m=mergepass(b,a,m,n);
    }
}