剑指35-数组中的逆序对

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

class Solution {
public:
    int InversePairs(vector<int> data) {
        mergeSort(data, 0, data.size()-1);
        return res;
    }

    void mergeSort(vector<int> &data, int start, int end)
    {
        if (start >= end) return;
        int n = end - start + 1;
        int middle = start + (end - start) /2;

        mergeSort(data, start, middle); //递归
        mergeSort(data, middle + 1, end);

        vector<int> newList(n); //开辟新空间
        int pivot =0, l=start, r=middle+1;
        while (l <= middle && r <= end)
        {
            if(data[l] >= data[r])
            {
                newList[pivot++]=data[r++];
                res+=middle-l+1;
                res=res%1000000007;
            }
            else
            {
                newList[pivot++]=data[l++];
            }
        }
        while (l <= middle) //加上剩余的值
        {
            newList[pivot++] = data[l++];
        }
        while (r <= end)
        {
            newList[pivot++] = data[r++];
        }
        for (int i = 0; i < n; i++) //修改原数组的值
        {
            data[start++] = newList[i];
        }
    }
private:
    int res=0;
};