【剑指offer】面试题36：数组中的逆序对

题目：

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

思路：

归并排序的合并过程。主要是考虑合并两个有序序列时，计算逆序对数。

对于两个升序序列，设置两个下标：两个有序序列的末尾。每次比较两个末尾值，如果前末尾大于后末尾值，则有”后序列当前长度“个逆序对；否则不构成逆序对。然后把较大值拷贝到辅助数组的末尾，即最终要将两个有序序列合并到辅助数组并有序。

这样，每次在合并前，先递归地处理左半段、右半段，则左、右半段有序，且左右半段的逆序对数可得到，再计算左右半段合并时逆序对的个数。

总个数=左个数+右个数+左右合并时的个数

注意：

注意InversePairsCore形参的顺序是(data,copy)，而递归调用时实参是(copy,data)。

要明白递归函数InversePairsCore的作用就行了，它是对data的左右半段进行合并，复制到辅助数组copy中有序。

最后，data和copy两个数组都是有序的。

代码：

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()<=1)  return 0;
        
        vector<int>  copy(data);
        return InversePairsCore(data,copy,0,data.size()-1);
    }
private:
    int InversePairsCore(vector<int> &data,vector<int> &copy, int begin, int end)
    {//合并data的两半段到辅助数组copy中有序
        if(begin==end)
        {
            copy[end]=data[end];
            return 0;
        }
        else
        {
            int mid=begin+(end-begin)/2;
            
            int left=InversePairsCore(copy,data,begin,mid);//使data的左半段有序 
            int right=InversePairsCore(copy,data,mid+1,end);//使data的右半段有序 
            
            int cnt=0;
            int cpIndex=end;
            int pre=mid;
            int post=end;
            //合并两个有序段，到copy数组 
            while(pre>=begin && post>=mid+1)
            {
                if(data[pre]>data[post])//每次比较的是两个有序序列
                {
                    cnt=cnt+(post-mid-1+1);
                    copy[cpIndex--]=data[pre];
                    pre--;
                }
                else
                {
                    copy[cpIndex--]=data[post];
                    post--;
                }
            }
            
            for(;pre>=begin;--pre)
                copy[cpIndex--]=data[pre];
            for(;post>=mid+1;--post)
                copy[cpIndex--]=data[post];
            
            return left+right+cnt;
        }
    }
};