归并排序+求逆序数

Time Limit: 50 ms Memory Limit: 65536 KiB

Problem Description

对于数列a1,a2,a3…中的任意两个数ai,aj (i < j)，如果ai > aj,那么我们就说这两个数构成了一个逆序对；在一个数列中逆序对的总数称之为逆序数，如数列 1 6 3 7 2 4 9中，(6,4)是一个逆序对，同样还有(3,2),(7,4),(6,2)，(6,3)等等，你的任务是对给定的数列求出数列的逆序数。

Input

输入数据N(N <= 100000)表示数列中元素的个数，随后输入N个正整数，数字间以空格间隔。

Output

输出逆序数。

Sample Input

10
10 9 8 7 6 5 4 3 2 1

Sample Output

45

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

时间复杂度：O(n log ⁿ)

思路：有点像线段树（所以时间复杂度上会优化），但是我们只需要对区间进行排序就好了，没必要真的写成线段树。

#include<bits/stdc++.h>

using namespace std;

int n,a[100010],b[100010];//a数组储存输入，b数组是对区间进行排序时用到的
long long int ans;		//这道题记得要开long long，ans代表的是逆序对的对数

void build(int l,int r)	//这里就是有点像建树的操作了
{
    int mid = (l+r)/2;
    if(l >= r)
        return ;
    build(l,mid);
    build(mid+1,r);
    int i = l,j = mid+1;
    int top = 0;
    while(i <= mid && j <= r)
    {
        if(a[i] <= a[j])//在b数组里面先存小的
        {
            b[top++] = a[i++];
        }
        else//因为在这之前两边的区间都是有序的，所以a[j] < a[i]的时候，比如
        {	//456   123，我们发现1<4所以456都是大于1的也就是说多了mid-i+1个逆序对
            b[top++] = a[j++];
            ans += mid-i+1;
        }
    }
    while(i <= mid)//没弄完的接上
    {
        b[top++] = a[i++];
    }
    while(j <= r)
    {
        b[top++] = a[j++];
    }
    for(int i = 0;i < top; i++)//我们要通过b数组来更新a数组让a数组有序，上面的操作
    {						//就是两个有序数组的合并，有点像链表的合并
        a[l+i] = b[i];
    }
    return ;
}

int main()
{
    scanf("%d",&n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d",&a[i]);
    }
    build(0,n-1);
    printf("%lld",ans);
    return 0;
}

最后

以上就是洁净蜻蜓为你收集整理的归并排序+求逆序数的全部内容，希望文章能够帮你解决归并排序+求逆序数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。