剑指Offer第三十五题：数组中的逆序对

题目描述
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

解答：
思路：采用归并排序的思想，按顺序两两比较，并排成新的有序数组后再两两比较，因为具有相似性，可以采用递归的写法。
举个例子：
1，8，9，2，5，3，4，7
两两比较并排序：
{1，8}，{2，9}，{3，5}，{4，7} 逆序数+2
两两比较并排序
{1，2，8，9}，{3，4，5，7} 逆序数+2
依次往下！
第二步：两个有序数组找逆序数相对简单：
比如{1，8} {2，9} ，先比较1和2，1<2那么第二个数组中的所有数都大于1，没有逆序对，1移出；再比较8和2，8>2那么2比第一个数组中剩余的数都小，逆序对数增加第一数组中剩余的个数，2移除；以上所有移除数都可以按顺序放置在新的合并数组中。。

public class Q_35 {

private int num = 0;

public int InversePairs(int[] array) {
    int[] result = getSortArray(array);
    return num;
}

public int[] getSortArray(int[] array) {
    if (array.length <= 1) {
        return array;
    }
    int[] left = Arrays.copyOfRange(array, 0, array.length / 2);
    int[] right = Arrays.copyOfRange(array, array.length / 2, array.length);
    left = getSortArray(left);
    right = getSortArray(right);
    //下面计算两个有序数组之间的逆序，并且合并成一个有序数组
    int i = 0, j = 0;
    int[] tmparr = new int[array.length];
    while (i < left.length && j < right.length) {
        if (left[i] > right[j]) {
            num = (num + left.length - i) % 1000000007;
            tmparr[i + j] = right[j];
            j++;
        } else {
            tmparr[i + j] = left[i];
            i++;
        }
    }
    if (i == left.length) {
        for (int m = j; m < right.length; m++) {
            tmparr[i + m] = right[m];
        }
    }
    if (j == right.length) {
        for (int n = i; n < left.length; n++) {
            tmparr[j + n] = left[n];
        }
    }
    return tmparr;
}

}