剑指offer:数组中的逆排序

整体思想用的是归并排序，分两部分，右边第一个数看左边的数谁比它大就是逆排序，省的一个个比较了，把右边都走一遍

定义个数组nums，左右边界，左大于右输出零；取个中间值mid，把左右两边都进行归并，逆序数对++，用了一个缓存数组存放两个子数组中最小元素比较的最小进行存储，最后是已经从小到大排序好的。

#define MODNUM 1000000007
class Solution{
public:
int InversePairs(vector<int> data){
    return mergeSort(data , 0, data.size()-1);
}
int mergeSort(vector<int>& nums,int left,int right){
    if(left>=right) return 0;
    int mid = left+(right-left)/2;
    int count = mergeSort(nums,  left,  mid) + mergeSort( nums,  mid+1,  right);
    vector<int> cache(right-left+1);
    int i = left,j=mid+1,k=0;
    while(i<=mid and j<=right){
        if(nums[i]<=nums[j]){
            cache[k++] = nums[i++];

        }else{
            count =(count+mid-i+1)%1000000007;
            cache[k++] = nums[j++];

        }
    }
    while(i<=mid)   cache[k++] = nums[i++];
    while(j<=right)   cache[k++] = nums[j++];
    for(int i =left,k=0;i<=right;i++,k++){
        nums[i]=cache[k];
    }
    return count;
}
};