数组中的逆序对

1、题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

2、解题

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

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

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

class Solution {
public:
    int InversePairs(vector<int> data) {
        if(data.size()==0)return 0;
        vector<int>copy;
        for(int i = 0;i<data.size();i++){
            copy.push_back(data[i]);
        }
        long long count = FindReserveCount(data,copy,0,data.size()-1);
        return count%1000000007;
    }
    long long FindReserveCount(vector<int>&data,vector<int>&copy,int low,int high){
        if(low>=high){
            return 0;
        }
        int mid = (low+high)>>1;
        long long leftCnt = FindReserveCount(data,copy,low,mid)%1000000007;
        long long rightCnt = FindReserveCount(data,copy,mid+1,high)%1000000007;
        int end1 = mid;
        int end2 = high;
        long long count = 0;
        //申请辅助空间
        int index = high;
        while(end1>=low && end2>=mid+1){
            if(data[end1]>data[end2]){
                copy[index--] = data[end1--];
                count += end2-mid;
            }else{
                copy[index--] = data[end2--];
            }
        }
        while(end1>=low){
            copy[index--] = data[end1--];
        }
        while(end2>=mid+1){
            copy[index--] = data[end2--];
        }
        //写入原数组
        for(int i = low;i<=high;i++){
            data[i] = copy[i]; 
        }
        return leftCnt+rightCnt+count;
    }
};