数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

思路：

使用归并排序，在归并的过程，统计逆序对的数量。比如两个待归并的数组为l=[5,6,12],r=[1,9,10]。归并的时候从右到左归并。12比10大，此时统计逆序对的数量，显然此时逆序对的数量是r的长度。把12放到排序数组的最末端。然后比较6和10，此时逆序对的数量为0，把10放入排序数组，在12的前面，接着比较6和9，逆序对的数量为0，把9放入排序数组，放在10的前面。比较6和1，此时逆序对的数量为1，把6放入排序数组，放在9的前面。接着比较5和1，此时逆序对的数量为1，把5放入排序数组，放在6的前面。最后把1放入排序数组，最左边的位置，排好序，同时，逆序对的数量也统计好了。

代码：

class Solution {
public:

    int reversePairsRecursive(vector<int>& nums, vector<int>& copy, int start, int end) {
        if(start == end) {
            copy[start] = nums[start];
            return 0;
        }
        //分解
        int mid = (end - start) / 2;
        int left = reversePairsRecursive(copy, nums, start, start + mid);
        int right = reversePairsRecursive(copy, nums, start + mid + 1, end);
        //归并
        int i = start + mid;
        int j = end;
        int indexCopy = end;
        int count = 0;
        while(i >= start && j >= start + mid + 1) {
            if(nums[i] > nums[j]) {
                copy[indexCopy--] = nums[i--];
                count += j - start - mid;
            }
            else {
                copy[indexCopy--] = nums[j--];
            }
        }

        for(; i >= start; --i)
            copy[indexCopy--] = nums[i];

        for(; j >= start + mid + 1; --j)
            copy[indexCopy--] = nums[j];

        return left + right + count;
    }

    int reversePairs(vector<int>& nums) {
        int len = nums.size();
        if(len == 0)
            return 0;
        vector<int> copy(len);
        for(int i = 0; i < len; ++i)
            copy[i] = nums[i];
        return reversePairsRecursive(nums, copy, 0, len - 1);
    }
};