逆序对数（归并排序）

80 阅读 0 评论 53 点赞

我是靠谱客的博主想人陪斑马，最近开发中收集的这篇文章主要介绍逆序对数（归并排序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

以前都是线段树写，这次归并排序写的

class Solution {
public:
    int InversePairs(vector<int> data) {
       vector<int>temp(data.begin(),data.end());
       if(data.size()<2) return 0;
       return merge_sort(data,temp,0,data.size()-1);
    }
    int merge_sort(vector<int>&a,vector<int>&b,int s,int e)
    {
        int ans=0;
        if(s>=e) return 0;
        int mid=(s+e)>>1;
        ans+=merge_sort(a,b,s,mid);
        ans+=merge_sort(a,b,mid+1,e);
        ans+=array_merge(a,b,s,e);
        return ans;
    }
    int array_sort(vector<int>&a,vector<int>&b,int s,int e)
    {
        int i,j,ans=0;
        int mid=(s+e)>>1;
        i=s;
        j=mid+1;
        int pos=s;
        while(i<=mid&&j<=e)
        {
            if(a[i]<=a[j])
            {
                temp[pos++]=a[i++];
            }
            else
                {
                    temp[pos++]=a[j++];
                    ans+=mid-i+1;
                }
        }
        while(i<=mid) temp[pos++]=a[i++];
        while(j<=e) temp[pos++]=a[j++];
        for(int i=s;i<=e;i++)
            a[i]=temp[i];
        return ans;
    }
};