题解 | #数组中的逆序对#

按照归并排序的思想：

1. 划分
2. 归并排序每一部分
3. 合并并统计逆序数

逆序数分为3部分：

• 划分的左部分
• 划分的右部分
• 跨越划分点的，设j>i,此时排序已经完成，如果a[i]>a[j]，则左半部分剩余元素均大于a[j],也就是这部分的逆序数为 mid-i+1

对上述三部分求和即可得。

public class Solution {
     int mod = 1000000007;

    long mergeSort(int[] array, int left, int right) {
        if (left >= right) {
            return 0;
        }
        int mid = left + right >> 1;
        // 排序过程
        long res = mergeSort(array, left, mid) + mergeSort(array, mid + 1, right);
        int[] tmp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= right) {
            if (array[i] < array[j]) {
                tmp[k++] = array[i++];
            } else {
                tmp[k++] = array[j++];
                res += mid - i + 1;
            }
        }
        while (i <= mid) {
            tmp[k++] = array[i++];
        }

        while (j <= right) {
            tmp[k++] = array[j++];
        }
        for (k = 0, i = left; k < tmp.length; k++, i++) {
            array[i] = tmp[k];
        }
        return res;
    }

    public int InversePairs(int[] array) {
        return (int)(mergeSort(array, 0, array.length - 1) % mod);
    }
}