逆序对

最简单的方法，根本过不了。

public class Solution {
    public int InversePairs(int [] array) {
        int l = array.length;
        int sum = 0;
        for(int i=0;i<l-1;i++){
            for(int j=i+1;j<l;j++){
                if(array[i]>array[j]){
                    sum++;
                }
            }
            sum = sum % 1000000007;
        }
        return sum;
    }
}

看大佬们的题解 大部分都是归并排序来做的，归并排序（升序）的时候遇到左边需要调整到右边去的元素时既可以计算逆序对的个数了，
本身左边和右边都是有序的，所以当左边的i比右边的j要大时，左边比i大的数一定也比右边的j要大，这样就有 i-mid+1 个逆序对了。继续合并继续计算其他的逆序对

public class Solution {
    public int sum = 0;
    public void mergeSort(int[] array, int start, int end){
        if(start>=end){
            return;
        }
        int mid = (start+end)/2;
        mergeSort(array, start, mid);
        mergeSort(array, mid+1, end);
        merge(array, start, mid, end);
    }
    public void merge(int[] array, int start, int mid, int end){
        // 存合并之后的数组的
        int l = end-start+1;
        int[] temp = new int[l];
        // 前面数组的起始
        int i = start;
        // 后面数组的起始
        int j = mid+1;
        // temp的下标
        int k = 0;
        // 把小的往前放。
        while(i<=mid&&j<=end){
            // 把小的存到前面
            if(array[i]<=array[j]){
                temp[k] = array[i];
                i++;
            }else {
                temp[k] = array[j];
                j++;
                // 如果当前i的元素大于后面的元素，那么当前i元素之后的(从i到mid)所有元素都能和j指向的元素构成逆序对。
                sum = (sum+(mid-i+1))%1000000007;
            }
            k++;
        }

        // 剩下哪个数组没合并完，就把它全拷贝到后面
        while(i<=mid){
            temp[k] = array[i];
            i++;
            k++;
        }
        while(j<=end){
            temp[k] = array[j];
            j++;
            k++;
        }
        // 合并完的拷贝回去
        for(k=0;k<l;k++){
            array[start+k] = temp[k];
        }

    }
    public int InversePairs(int [] array) {
        mergeSort(array, 0, array.length-1);
        return sum;
    }
}