剑指offer（35）数组中的逆序对

//思路与归并排序相似

public class Solution {
    public int InversePairs(int [] array) {
        if(array == null || array.length == 0){
            return 0;
        }
        int[] copy = new int[array.length];
        for(int i = 0;i < array.length;i++){
            copy[i] = array[i];
        }
        int count = InversePairsCore(array, copy, 0, array.length - 1);
        return count;
    }
    public int InversePairsCore(int[] array, int[] copy, int start, int end){
        if(start == end){
            return 0;
        }
        int mid = (start + end) >> 1;
        int leftCount = InversePairsCore(array, copy, start, mid) % 1000000007;
        int rightCount = InversePairsCore(array, copy, mid + 1, end) % 1000000007;
        int copyIndex = end;
        int i = mid;
        int j = end;
        int count = 0;
        while(i >= start && j > mid){
            if(array[i] > array[j]){
                count += j - mid;
                copy[copyIndex--] = array[i--];
                if(count >= 1000000007){
                    count = count % 1000000007;
                }
            }else{
                copy[copyIndex--] = array[j--];
            }
        }
        for(;i >= start;i--){
            copy[copyIndex--] = array[i];
        }
        for(;j > mid;j--){
            copy[copyIndex--] = array[j];
        }
        for(int s = start;s <= end;s++){//递归中，不一定是0到最后，还有可能递归到更小的范围，strat和end都是不同的，
            array[s] = copy[s];
        }
        return (leftCount + rightCount + count) % 1000000007;//因为如果前几次求余时，被除数没有大于1000000007，即还是本身，所以还要进行一次求余
    }
}