求逆序对数(归并排序)

56 阅读 0 评论 37 点赞

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

概述

在这里插入图片描述

算法思路

1.即在归并排序合并数组时恰好可以统计逆序对的数量
2.给出统计规则如下：
if(q[i]<q[j]) 不产生逆序对
else 产生mid-i+1个逆序对

#include <iostream>

using namespace std;

const int N = 100010;

int q[N],tmp[N],n;

long long merge_sort(int l,int r,int q[])
{
    if(l>=r)
        return 0;
    
    long long res = 0;
    
    int mid = l+r >>1;
    res = merge_sort(l,mid,q) + merge_sort(mid+1,r,q);
    
    //在归并的过程中求逆序对数
    int i = l;
    int j = mid +1;
    int k = 0;
    while(i<=mid && j<=r)
    {
        if(q[i]<=q[j])
            tmp[k++] = q[i++];
        else
        {
            tmp[k++] = q[j++];
            res += mid - i + 1; 
        }
        
    }
    
    while(i<=mid)
        tmp[k++] = q[i++];
    while(j<=r)
        tmp[k++] = q[j++];
    
    for(int i = l,k=0;i<=r;i++,k++)
        q[i] = tmp[k];
        
    return res;
}

int main()
{
    cin>>n;
    for(int i = 0;i<n;i++)
        cin>>q[i];
        
    cout<<merge_sort(0,n-1,q)<<endl;
    
    return 0;
}