归并排序

归并(Merge)排序是将两个(或两个以上)有序表合并成一个新的有序表,

即把待排序序列分为若干个有序的子序列,再把有序的子序列合并为整体有序序列

归并排序是建立在归并操作上的一种有效的排序算法。

该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

首先考虑下如何将两个有序数列合并:

只要从比较二个数列的第一个数,谁小就先取谁,

取了后就在对应数列中删除这个数,然后再进行比较,

如果有数列为空,那直接将另一个数列的数据依次取出即可

void merge_sort(int l[],int m,int r[],int n,int a[])
{
    int i=0,j=0,k=0;
    while(i<m&&j<n){
        if(l[i]<=r[j])
            a[k++]=l[i++];
        else
            a[k++]=r[j++];
    }
    while(i<m)
        a[k++]=l[i++];
    while(j<n)
        a[k++]=r[j++];
}

时间复杂度为O(n)

解决了上面的合并有序数列问题,再来看归并排序,

其的基本思路就是将数组分成二组A,B,如果这二组组内的数据都是有序的,

那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序?

可以将A,B组各自再分成二组,依次类推,当分出来的小组只有一个数据时,

可以认为这个小组组内已经达到了有序,然后再合并相邻的二个小组就可以了。

这样通过先递的分解数列,再合数列就完成了归并排序。

void cmp(int ll,int mid,int rr)
{
    int m=0,n=0,i,j,k;
    for(i=ll;i<=mid;i++)
        l[m++]=a[i];
    for(i=mid+1;i<=rr;i++)
        r[n++]=a[i];
    i=j=0;
    k=ll;
    while(i<m&&j<n){
        if(l[i]<=r[j])
            a[k++]=l[i++];
        else
            a[k++]=r[j++];
    }
    while(i<m)
        a[k++]=l[i++];
    while(j<n)
        a[k++]=r[j++];
}
void mergesort(int l,int r)
{
    int mid;
    if(l<r){
        mid=(l+r)/2;  //不断二分
        mergesort(l,mid);  //左边部分
        mergesort(mid+1,r); //右边部分
        cmp(l,mid,r);  //比较合并
    }
}

其时间复杂度为 O(n*log n)

归并排序的应用

归并排序最为经典的一个应用:求一个整数序列中逆序对数

设a[1...n]是一个包含n个不同数的数组,若当i<j时,有a[i] >a[j],则称(i,j)就是一个逆序对




郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。