数组中的逆序对

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

这个问题就是检查每个数后面有多少个比他小的数字。我们当然可以遍历这个数组，找到一个数字，然后再遍历的查找后面的数组中有多少个数字比它小。但是这样就n^2的时间了。

那么我们可以使用归并排序来解决，时间O（nlgn）。使用归并排序，我们可以找到两个数字的逆序对，再找到四个数字的逆序对。。。一直找到n个数字。

class Solution
{
public:
    //使用归并，从小范围到大范围的找出逆序对
    int InversePairs(vector<int>data)
    {
        int length = data.size();
        if(length<=0)
            return 0;
        vector<int> copy;
        for(int i=0;i<length;i++)
            copy.push_back(data[i]);
        long long count = InversePairsCore(data,copy,0,length-1);
        return count%100000007;
    }

    long long InversePairsCore(vector<int>& data,vector<int>& copy,int start,int end)
    {
        if(start == end)
            {
                copy[start] = data[start];
                return 0;
            }
        int length=(end-start)/2;
        long long left = InversePairsCore(copy,data,start,start+length);
        long long right = InversePairsCore(copy,data,start+length+1,end);

//开始归并
        int i=start + length;
        int j = end;
        int indexcopy = end;//每次都是从最后一点开始放元素
        long long count;
        while(i>=start&&j>=start+length+1)
        {
            if(data[i]>data[j])
            {
                copy[indexcopy--] = data[i--];
                count = count+j-start-length;//比这个范围内的数字都大。
            }
            else//如果data i 小于data j，那就没有逆序对
                copy[indexcopy--] = data[j--];
        }
        for(;i>=start;i--)
            copy[indexcopy--] = data[i];
        for(;j>=start+length+1;j--)
            copy[indexcopy--] = data[j];
        return left+right+count;
    }
}