归并排序求解逆序对数

66 阅读 0 评论 44 点赞

我是靠谱客的博主帅气铃铛，最近开发中收集的这篇文章主要介绍归并排序求解逆序对数，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

逆序对

定义

逆序对就是对于i<j且a[i]>a[j]，这样的数对在序列中的个数。

求解方法

·　　归并排序是采用分治的思想划分数列，然后将两路有序的数列合并。通过划分和合并的递归调用来完成排序。在合并的过程中，两个数列中的元素的相对位置不会发生改变（这里只是前后关系）。而且如果后一个数列B中某个元素b在需要先放入（优先于前一个数列A数列元素a），则a在b的前面，但是b小于a这样就会产生逆序对，对数的数目为（数列B中b包括b在内的b前面的元素）都能与a产生逆序对。
　　对于每次位置的改变不会产生逆序对，如果改变前存在逆序对，那么将会计算一部分，未计算的部分未改变。

代码实现：

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long 
#define Max 5000100
int a[Max];
ll cnt;
void marge(int l,int mid,int r)
{
    int i=l,j=mid+1;
    int num[r-l+2];
    int n=0;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            num[++n]=a[i++];
        }
        else{
            cnt+=mid+1-i;
            num[++n]=a[j++];
        }
    }
    while(i<=mid){
        num[++n]=a[i++];
    }
    while(j<=r){
        num[++n]=a[j++];
    }
    for(int s=1;s<=n;s++){
        a[l+s-1]=num[s];
    }
}
void margeSort(int l,int r){
    if(l>=r) return ;
    int mid=l+r>>1;
    margeSort(l,mid);
    margeSort(mid+1,r);
    marge(l,mid,r);
}
inline int read(){//快读
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    margeSort(1,n);
    cout<<cnt<<endl;
    //for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}