数组中的逆序对（归并排序）

3.第三次做：归并排序思路+求余

知道这道题考的不是大数之后就没太注意，只是在最后mod了一下，加上两处中间计算结果的求余之后就可以通过了。

res += mergeSort(array, start, mid);
res += mergeSort(array, mid+1, end);
res += merge(array, start, mid, end);
res = res % 1000000007;

count += mid-c1+1;
count = count % 1000000007;

2.第二次做：归并排序思路

（1）归并排序先将数组不断二等分成左右两边各1个元素, 比较这两个元素判断是否构成逆序对, 并将这个两个元素合并成一个有序的数组, 归并后的数组因为是递增排序的,所以不再包含逆序对。
（2）接着比较长度为2的两个数组, 首先这两个数组内部没有逆序对了, 所以只有在合并两个数组的过程中包含逆序对。、
代码：只是在归并排序的基础代码上加入了一行count的计算，提交只能通过50%的测试样例。进一步分析一下还有哪个细节没有思考到位。

public class Solution {
    public int InversePairs(int[] array){
        int res = mergeSort(array, 0, array.length-1);
        return res%1000000007;
    }
    public int mergeSort(int[] array, int start, int end){
        int res = 0;
        if(start<end){
            int mid = (start+end)/2;
            res += mergeSort(array, start, mid);
            res += mergeSort(array, mid+1, end);
            res += merge(array, start, mid, end);
        }
        return res;
    }

    public int merge(int[] array, int start, int mid, int end){
        int[] newarray = new int[end-start+1];
        int c1 = start, c2 = mid+1;
        int pos = 0, count = 0;
        while(c1<=mid && c2<=end){
            if(array[c1]<array[c2]){
                newarray[pos++] = array[c1++];
            }
            else{
               //说明c2比前半部分剩下的元素都小
                count += mid-c1+1;
                newarray[pos++] = array[c2++];
            }
        }
        //处理剩余段
        while(c1<=mid)
            newarray[pos++] = array[c1++];
        while(c2<=end)
            newarray[pos++] = array[c2++];
        //复制回原数组
        for(int i = start; i<=end; i++)
            array[i] = newarray[i-start];
        return count;
    }

}

1.第一次做：暴力求解思路：

暴力求解感受一波。搜索逆序对,时间复杂度：O(n^2)，复杂度过大没有通过

public class Solution {
    /*1.暴力解法：逆序对判断 O(n^2)--有不必要的比较可以优化
    */
    public int InversePairs(int[] array){
        int count = 0;
        if(array==null)    return 0;
        for(int i = 0; i<array.length; i++){
            for(int j = i; j<array.length; j++){
                if(array[i]>array[j])
                    count++;
            }
        }
        return count%1000000007;
    }
}