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

思路：

1. 整体思路：按照归并排序的思路进行排序
2. 第一步：对左右两个分组进行排序
3. 第二步：合并两个已经排序的分组，左侧分组中大于右侧分组中数据，那么大于的逆序对个数就是count = count + mid-low+1, 然后对两个分组按照大小顺序合并成一个新分组。
4. 把合并后的新分组复制到要排序的数组中，返回count。

public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        if (array == null || array.length == 0) {
            return 0;
        }

        int low = 0;
        int high = array.length-1;
        inversePairs(array,low,high);
        return count;
    }

    private void inversePairs(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }

	  //这个地方要注意使用小括号括住
        int mid = low + ((high - low) >> 1);
        inversePairs(array, low, mid);
        inversePairs(array, mid + 1, high);

        int left = low;
        int right = mid + 1;
        int[] newArray = new int[high - low + 1];
        int index = 0;
        while (left <= mid && right <= high) {
            //左边最小的大于右边最小的，都是逆向对
            if (array[left] > array[right]) {
                count = (count + mid - left + 1) % 1000000007;
                newArray[index] = array[right];
                right++;
            } else {
			//否则，就进行复制
                newArray[index] = array[left];
                left++;
            }
            index++;
        }

        while (left <= mid) {
            newArray[index] = array[left];
            index++;
            left++;
        }
        while (right <= high) {
            newArray[index] = array[right];
            index++;
            right++;
        }

        left = low;
        for (int i = 0; i < newArray.length; i++) {
            array[left] = newArray[i];
            left++;
        }
    }
}