题解 | #数组中的逆序对#归并排序

采用归并排序的方法统计数组中逆序对的个数：
先对数组进行递归划分，划分为一个个的子数组，然后统计出相邻子数组之间的逆序对的数量，在统计逆序对的过程中，还需要对数组进行排序，这是为了防止在以后的统计过程中出现重复统计的情况以及计算逆序对的数目方便。

统计两个子数组之间的逆序对的数量的过程如下：
1、使用两个指针分别指向两个子数组的末尾，每次比较两个指针指向的数字。
（1）如果第一个子数组中的数字大于第二个子数组中的数字，则构成逆序对，逆序对的数目等于第二个子数组中指针左边剩余数字的个数。
（2）如果第一个子数组中的数字小于等于第二个子数组中的数字，则不构成逆序对。
2、每次比较的时候，都需要将较大的数字复制到辅助数组中，确保辅助数组中的元素是递增有序的。将较大的数字复制到辅助数组以后，其对应的指针和辅助数组的指针向前移动一个位置。
3、最后需要将辅助数组中的元素复制给原数组，否则将产生重复。

public class Solution {
    public int InversePairs(int [] array) {

        if (array == null || array.length == 0){
            return 0;
        }
        int[] temp = new int[array.length];
        return sort(array,temp,0,array.length - 1);
    }

    private int sort(int[] arr,int[] temp,int left,int right){

        if (left < right){

            int mid = (right - left) / 2 + left;
            int count = 0;
            count += sort(arr,temp,left,mid);
            count += sort(arr,temp,mid+1,right);


            // i 为左半部分的最后一个元素的下标
            int i = mid;
            // j 为右半部分的最后一个元素的下标
            int j = right;
            // t 为辅助数组的待存放元素位置的下标
            int t = right;

            while (i >= left && j >= mid + 1){

                if (arr[i] > arr[j]){

                    temp[t--] = arr[i--];
                    count = (count + j - mid)%1000000007;
                }else {

                    temp[t--] = arr[j--];
                }

            }

            while (i >= left){

                temp[t--] = arr[i--];
            }

            while (j >= mid + 1){

                temp[t--] = arr[j--];
            }

            t = right;

            while (right >= left){

                arr[right--] = temp[t--];
            }

            return count;
        }

        return 0;
    }
}