排序算法——归并算法

参考文章：http://blog.csdn.net/u010275850/article/details/45536535

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用，时间复杂度最坏情形为O(NlogN)。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。（引自百度百科）

这个算法的基本操作是合并两个已排序的表。基本的合并算法是取两个输入数组A和B，一个输出数组C，以及三个计数器Aptr,Bptr,Cptr.他们初始位置置于对应数组的开始端。A[Aptr]和B[Bptr]中的较小者被拷贝到C中的下一个位置，相关的计数器向前推进一步。当两个输入表有一个用完时，则将另一个表中剩余的部分拷贝到C中。合并例程工作的例子可见下图：

至此，整个合并过程结束。

对于整个序列，归并排序所采用的方法是递归的拆分，然后再递归的合并。可用下图表示：

其代码实现：

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

void MSort(int *data,int *tmp,int left,int right);
void Mergesort(int *data,int n);
void Merge(int *data,int *tmp,int frist,int mid,int last);

int main()
{
    int i=0;
    int data[8]={24,13,26,1,2,27,38,15};

    printf("Before Sort:\n");
    for(i=0;i<8;i++)
        printf("%d\t",data[i]);
    Mergesort(data,8);

    printf("\nAfter Sort:\n");
    for(i=0;i<8;i++)
        printf("%d\t",data[i]);
    return 0;
}

void MSort(int *data,int *tmp,int left,int right)
{
    int center;
    if(left<right)
    {
        center=(left+right)/2;
        MSort(data,tmp,left,center);//左边有序
        MSort(data,tmp,center+1,right);//右边有序
        Merge(data,tmp,left,center,right);//再将俩个有序数列合并
    }
}

void Mergesort(int *data,int n)
{
    int *tmp;
    tmp=malloc(n*sizeof(int));
    if(tmp!=NULL)
    {
        MSort(data,tmp,0,n-1);
        free(tmp);
    }
    else
        printf("No space for tmp array!!\n");
}

//将两个有序数列a[first...mid]和a[mid+1,...last]合并。
void Merge(int *data,int *tmp,int first,int mid,int last)
{
    int i=first, j=mid+1;
    int n=mid, m=last;
    int k=0;

    while((i<=n)&&(j<=m))
    {
        if(data[i]<=data[j]) //取出较小值放到前面
            tmp[k++]=data[i++];
        else
            tmp[k++]=data[j++];
    }

    while(i<=n)
        tmp[k++]=data[i++];

    while(j<=m)
        tmp[k++]=data[j++];

    for(i=0;i<k;i++)
        data[first + i]=tmp[i];
}