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

 /*
       最简单的思路：数组的所有数两两比较，进行累加，空间复杂度为O(n^2)

 */

class Solution {
public:
    int InversePairs(vector<int> data) {
        int P = 0;
        if(data.size()<2)
            return P;
        for(int i=0;i<data.size()-1;i++){
            for(int j=i+1;j<data.size();j++){
                if(data[i] > data[j])
                    P++;
            }
        }
        return P%1000000007;
       
    }
};

/*
思路二：
归并排序的改进，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)，
合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；则前面
数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - i
参考剑指Offer，但是感觉剑指Offer归并过程少了一步拷贝过程。
还有就是测试用例输出结果比较大，对每次返回的count mod(1000000007)求余
*/

class Solution {
public:
    int P = 0;
    int InversePairs(vector<int> data) {        
        if(data.size()<2)
            return P;
        vector<int> copy ;
        for(int i=0;i<data.size();i++){
            copy.push_back(data[i]);
        }
        mergeSort(data,copy,0,data.size()-1);
        return P%1000000007;
    }
    void mergeSort(vector<int> &data,vector<int> &copy,int begin,int end){
        if(begin < end){
            int mid = (begin + end)/2;
            mergeSort(data,copy,begin,mid);
            mergeSort(data,copy,mid+1,end);
            merge(data,copy,begin,mid,end);
        }
    }
    void merge(vector<int> &data,vector<int> &copy,int begin,int mid,int end){
        
        int i = begin,j = mid + 1;
        while(i<=mid && j<=end){
            if(data[i] <= data[j])
                copy.push_back(data[i++]);
            else{
                copy.push_back(data[j++]);
                P += mid - i + 1;
            }
        }
        while(i <= mid)
            copy.push_back(data[i++]);
        while(j <= end)
            copy.push_back(data[j++]);
        for(int k=begin;k<=end;k++){
            data[k] = copy[k];
        }
    }
};