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

import java.util.Arrays;

public class BM20 {
// 保存最后结果
static int result = 0;

public static int InversePairs(int[] array) {
    sort(array, 0, array.length - 1);
    return result;
}

//归并排序，分治
static void sort(int[] array, int l, int r) {
    if (l >= r)
        return;
    int mid = (l + r) / 2;
    sort(array, l, mid);
    sort(array, mid + 1, r);

    if (array[mid] > array[mid + 1]) {
        result += merge(array, l, mid, r);
        if (result > 1000000007)
            result -= 1000000007;
    }

}

/**
 * 合并左右两边，在合并的过程中求出 逆序数对 个数,并返回该值。
 */
static int merge(int[] array, int l, int mid, int r) {
    int tc = 0;
    int c = 0;
    int[] temp = Arrays.copyOfRange(array, l, r + 1);
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) { //如果左边已经全部处理完
            array[k] = temp[j - l];
            j++;
        } else if (j > r) {//如果右边全部处理完
            array[k] = temp[i - l];
            c += tc;
            tc = 0;
            i++;
        } else if (temp[i - l] < temp[j - l]) {
            array[k] = temp[i - l];
            c += tc;
            tc = 0;
            i++;
        } else {
            array[k] = temp[j - l];
            tc += mid - i + 1;
            j++;

        }
    }
    return c;
}
}