排序

下面是几种内部排序算法：

1.冒泡排序；

2.插入排序；

3.希尔排序；

4.堆排序；

5.归并排序；

6.快速排序。

没有什么排序算法能做到在任何时候都是最好的排序算法。

下面是各排序算法的C语言实现：

typedef long int Elemtype;

void swap(long int *a,long int *b)
{
    long temp;
    temp = *a;
    *a = *b;

冒泡排序，可以对单链表使用，不必要求元素随机存储。

void Bubble_Sort(Elemtype A[],int N)
{
    int i,j;
    for(i=N-1;i>=0;--i)
    {
        int flag = 0;
        for(j=0;j<i;++j)
        {
            if(A[j]>A[j+1])//稳定的 
            {
                swap(&A[j],&A[j+1]);
                flag = 1;
            }
        }
        if(flag==0) break;
    }
}

插入排序，有T(N+I),其中I为逆序对的数量。

void Insert_Sort(Elemtype A[],int N)
{
    int i,j;
    for(i=1;i<N;++i)
    {
        int temp = A[i];
        for(j=i;j>0&&A[j-1]>temp;--j)//稳定 
        {
            A[j] = A[j-1];
        }
        A[j] = temp;
    }
}

希尔排序，使用不同的增量序列可以得到不同的时间复杂度。

//Hibbard增量序列Dk=2^k-1; 
void Shell_Sort(Elemtype A[],int N)
{
    int i,j,k;
    for(k=N/2;k>0;k/=2)
    {
        for(i=k;i<N;++i)
        {
            Elemtype temp = A[i];
            for(j=i;j>=k&&A[j-k]>temp;j-=k)
            {
                A[j] = A[j-k];
            }
            A[j] = temp;
        }
    }
}

堆排序，是不稳定的。

void HeapAdjust(Elemtype *H,int S,int N)
{
    Elemtype temp = H[S];
    int parent,child;
    for(parent=S;parent*2+1<N;parent=child)
    {
        child = parent*2+1;
        if(child+1<N&&H[child+1]>H[child])
        {
            child += 1;
        }
        if(temp>H[child]) break;
        H[parent] = H[child];
    }
    H[parent] = temp;
}
//不稳定 
void Heap_Sort(Elemtype *A,int N)
{
    int i;
    for(i=(N-1)/2;i>=0;--i)
    {
        HeapAdjust(A,i,N);
    }
    for(i=N-1;i>0;--i)
    {
        swap(&A[0],&A[i]);
        HeapAdjust(A,0,i);
    }
}

归并排序

void Merge(Elemtype A[],Elemtype temp[],int L,int R,int Rend)
{
    int Lend = R-1;
    int length = Rend-L+1;
    int cnt = L;
    while(L<=Lend&&R<=Rend)
    {
        if(A[L]<=A[R])
        {
            temp[cnt++] = A[L++];
        }
        else
        {
            temp[cnt++] = A[R++];
        }
    }
    while(L<=Lend) temp[cnt++] = A[L++];
    while(R<=Rend) temp[cnt++] = A[R++];
    while(length-->0)
    {
        A[Rend] = temp[Rend--];
    }
}

void MSort(Elemtype A[],Elemtype temp[],int S,int E)
{
    if(S<E)
    {
        int m = (S+E)/2;
        MSort(A,temp,S,m);
        MSort(A,temp,m+1,E);
        Merge(A,temp,S,m+1,E);
    }
}

void Merge_Sort(Elemtype A[],int N)
{
    Elemtype *temp;
    temp = (Elemtype*)malloc(sizeof(Elemtype)*N);
    MSort(A,temp,0,N-1);
}

快速排序，通过Median函数获取每一轮的排序元素，它是待排序数组，low，mid，high三者的中位数。

Elemtype Median(Elemtype A[],int low,int high)
{
    int mid = (low+high)/2;
    if(A[low]>A[mid])
    {
        swap(&A[low],&A[mid]);
    }
    if(A[low]>A[high])
    {
        swap(&A[low],&A[high]);
    }
    if(A[mid]>A[high])
    {
        swap(&A[mid],&A[high]);
    }
    swap(&A[mid],&A[high-1]);
    return A[high-1];
}

void Insertion_Sort(Elemtype A[],int left,int right)
{
    int i,j;
    for(i=left+1;i<=right;++i)
    {
        Elemtype temp = A[i];
        for(j=i;j>left&&A[j-1]>temp;--j)
            A[j] = A[j-1];
        A[j] = temp;
    }
}

void QSort(Elemtype A[],int low,int high)
{
    if(high-low>100){
        if(low>=high) return;
        Elemtype pivot = Median(A,low,high);
        if(high-low==1) return;//别忘了 ,或在下面加两个while加i<j 
        int i = low,j = high-1;
        while(1)
        {
            while(i<j&&A[++i]<pivot);
            while(i<j&&A[--j]>pivot);
            if(i<j)
                swap(&A[i],&A[j]);
            else
                break;
        }
        swap(&A[i],&A[high-1]);
        QSort(A,low,i-1);
        QSort(A,i+1,high);
    }
    else
        Insertion_Sort(A,low,high);
}

void Quick_Sort(Elemtype A[],int n)
{
    QSort(A,0,n-1);
}