09-排序1 排序 (堆、归并)

堆排序

中心思想

选择排序的优化版，选择排序是顺序扫描整个数组，找到最大值然后放到末尾，堆排序是使用了一个最大堆来存储最大值，然后每次找最大值就使用删除首节点的方法，最终继续使用选择排序完成剩下的排序过程。

实现代码

#include<stdlib.h>
#include<stdio.h>

void Heap_sort(int Data[],int N);
void PercDown(int *Data,int M,int N);
void swap(int *A,int *B);

int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Heap_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Heap_sort(int *Data,int N)
{   
    int i;
    for(i = N/2;i>=0;i--)
        PercDown(Data,i,N);
    for(i = N-1;i > 0; i--)
    {
        swap(&Data[0],&Data[i]);
        PercDown(Data,0,i);
    }
}
void PercDown(int *Data,int M,int N)
{
    int parent,child,X;
    X = Data[M];
    for(parent = M; parent*2 + 2 <= N; parent = child){
        child = parent*2 + 1;
        if((child != N-1)&&(Data[child] < Data[child+1]))
            child++;
        if(Data[child] <= X) break;
        else
            Data[parent] = Data[child];
    }
    Data[parent] = X;
}
void swap(int *A,int *B)
{
    int tmp;
    tmp = *A;
    *A = *B;
    *B = tmp;
}

测试结果

堆排序是一个复杂度为 $O(NlogN)$ 的排序算法，可以看出来它的排序效率和希尔排序是差不多的，不过堆排序额外开辟了一个数量级为 $N$ 的数组，导致了可排序的数字减少了一半，不过使用空间换时间也是比较常见的策略

归并排序

中心思想

归并排序的想法是开辟一个数组，把我们要排序的数组分成左右两部分，先解决左边的排序问题在解决右边的排序问题。要怎么解决左边的问题呢？再递归调用归并排序的函数，继续分而治之。

递归实现代码

#include<stdlib.h>
#include<stdio.h>

void Merge_sort(int *Data,int N);
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd );
void Msort(int Data[], int TmpData[], int L, int RightEnd);
int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Merge_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Merge_sort(int *Data,int N)
{
    int *TmpData;
    TmpData = (int*)malloc(N * sizeof(int));
    Msort( Data, TmpData, 0, N-1 );
    free( TmpData );
}
void Msort(int Data[], int TmpData[], int L, int RightEnd)
{
    int Center;
    if( L < RightEnd )
    {
        Center = ( L + RightEnd ) / 2;
        Msort( Data, TmpData, L, Center );
        Msort( Data, TmpData, Center+1, RightEnd );
        Merge( Data, TmpData, L, Center+1, RightEnd);
    }
}

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd )
{ /* 将有序的Data[L]~Data[R-1]和Data[R]~Data[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp, i;
    NumElements = RightEnd - L + 1;
    LeftEnd = R-1;
    Tmp = L;
    while(L <= LeftEnd && R <= RightEnd)
    {
        if(Data[L] > Data[R])
            TmpData[Tmp++] = Data[R++];
        else
            TmpData[Tmp++] = Data[L++];
    }
    while( L <= LeftEnd )
        TmpData[Tmp++] = Data[L++];
    while( R <= RightEnd )
        TmpData[Tmp++] = Data[R++];
    for(i = 0; i < NumElements; i++, RightEnd--)
        Data[RightEnd] = TmpData[RightEnd];
}

测试结果

非递归实现代码

#include<stdlib.h>
#include<stdio.h>

void Merge_sort(int *Data,int N);
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd );
void Msort(int Data[], int TmpData[], int N, int length);
int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Merge_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Merge_sort(int *Data,int N)
{
    int *TmpData,length;
    length = 1;
    TmpData = (int*)malloc(N * sizeof(int));
    while(length < N){
        Msort( Data, TmpData, N, length );
        length *= 2;
        Msort( TmpData, Data, N, length );
        length *= 2;
    }
free( TmpData );
}
void Msort(int Data[], int TmpData[], int N, int length)
{
    int i,j;
    for( i = 0;i < N - 2*length; i+=2*length)
        Merge(Data, TmpData, i, i+length, i+2*length-1 );
    if(i + length < N)
        Merge(Data, TmpData, i, i+length, N-1);
    else
        for(j = i;j < N;j++)TmpData[j] = Data[j];
}

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd )
{ /* 将有序的Data[L]~Data[R-1]和Data[R]~Data[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp;
    NumElements = RightEnd - L + 1;
    LeftEnd = R-1;
    Tmp = L;
    while(L <= LeftEnd && R <= RightEnd)
    {
        if(Data[L] > Data[R])
            TmpData[Tmp++] = Data[R++];
        else
            TmpData[Tmp++] = Data[L++];
    }
    while( L <= LeftEnd )
        TmpData[Tmp++] = Data[L++];
    while( R <= RightEnd )
        TmpData[Tmp++] = Data[R++];
}