归并排序应用-----求逆序数

2020/1/23 19:37:57 人评论 次浏览 分类:学习教程

归并排序是冒泡排序的一种升级版排序,其灵魂是二分思想加上冒泡,在二分的基础上进行冒泡排序,可以将原来时间复杂度为O(n^2)的冒泡排序降低为O(logn)的归并排序。
下面我们先来看归并排序,之后再来讲归并排序的应用—求逆序数

归并排序

前面提到,归并排序采用的是二分思想,我们先把一段需要排序的序列分成两半,是不是每一段的交换次数就会变少,然后我们又将分成的两段,继续分成四段,以此类推,直到分到每一段只有一个数的时候,就可以停止,接下来就是分治的–“治”
我们把它们拆开之后,就依次合上来,原来一个数合成两个数,在合的时候又进行比较大小,这样效率会提高很多,最终实现整个序列的排序。

看这张图,可以更好的理解:
在这里插入图片描述
下面看一下具体的代码实现

int gb[100001];//临时数组
void mers(int *a,int s,int mid,int end)//治(合)
{
    int k=s;
    int i=s,j=mid+1;
    while(i<=mid&&j<=end)
    {
        if(a[i]<=a[j])
        {
            gb[k++]=a[i];
            i++;
        }
        else
        {
            gb[k++]=a[j];
            j++;
        }
    }
        while(i<=mid)
        {
            gb[k++]=a[i++];
        }
        while(j<=end)
        {
            gb[k++]=a[j++];
        }
        for(i=s;i<=end;i++)
        {
            a[i]=gb[i];
        }
}
void mergesort(int *a,int s,int end)//分
{
    if(s<end)//只要起点小于终点就一直二分下去
    {
        int mid=(s+end)/2;
        mergesort(a,s,mid);
        mergesort(a,mid+1,end);
        mers(a,s,mid,end);
    }
}

可以看到我们开辟了一个临时数组,虽然我们把时间复杂度降低了,但是是以空间为代价换取的,有利也有弊。

求逆序数

首先我们必须知道逆序数是什么,我们来看个例子
1 3 2
这里的3和2就是一对逆序数,所以答案是1
1 5 2 3
这里的5和2 5和3也是逆序数,所以答案是2
这其实就是求他的交换次数,在对于少量数据来说冒泡排序就可以解决问题,但是对于数据量比较大的时候我们用的就是归并排序来求,理解了上面的归并排序后求逆序数也就很简单了。
具体来看下面的代码

int gb[100001];
void mers(int *a,int s,int mid,int end)
{
    int k=s,n1=mid+1;
    int i=s,j=mid+1;
    while(i<=mid&&j<=end)
    {
        if(a[i]<=a[j])
        {
            gb[k++]=a[i];
            i++;
        }
        else//只有在前面比后面大的情况才有逆序数
        {
            count+=n1-i;//求逆序个数
            gb[k++]=a[j];
            j++;
        }
    }
        while(i<=mid)
        {
            gb[k++]=a[i++];
        }
        while(j<=end)
        {
            gb[k++]=a[j++];
        }
        for(i=s;i<=end;i++)
        {
            a[i]=gb[i];
        }

}

归并排序是排序算法中比较重要而且比较快速的算法,所以必须要掌握。

性感程序员
发布了4 篇原创文章 · 获赞 0 · 访问量 82
私信 关注

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->