数组中的逆序对

剑指offer35 数组中的逆序对

问题分析

暴力是第一个想法，但是一定是行不通的，那么必须想办法去解决一个复杂度问题，既然是逆序对，那么就会想到归并排序的想法。

归并排序

1. 将数组等分成两份，并且不断等分，直到只有一个元素的时候，那么不再进行等分，也就是达到 left(数组的左边起点) == mid(等分的点)，直接return，不再分解
2. 等分的每一份是要进行排序的，比如现在等分的数据是[6,9],[10,8],我们按照升序排列，那么结果是[6,9],[9,10] 才是我们想要的结果
3. 合并阶段，如何合并呢，我们需要辅助数组temp来记录正确的顺序，还是上面的例子，我们需要三个索引来完成这个工作。
   • p1为[6,9]的起点，p2为[8,10]的起点，mid为[6,9,10,8]划分两份时的切割点。
   • 如果array[p1]>array[p2]，那么temp存array[p2]的值，然后p2++，向后移动索引。
   • 反之，也是一样的，temp存array[p1]的值，p1++，向后移动索引
   • 最后一步，循环把temp覆盖到原来数组的位置

基于归并继续分析

我们看到了合并阶段的过程，那么p1，p2索引到的值的比较，也正是逆序对的比较，那么在这个阶段，我们需要给总和加上这个数，可以在代码中看到。

需要理解的一点是，由于先进行数组的划分，再进行排序，那么到排序阶段是可以理解划分两半的数组为是有序的。

代码

private int res = 0 ; //记录统计结果

    public int InversePairs(int [] array) {

        Merge_Array(array,0,array.length-1);

        return res ;
    }

    public void Merge_Array(int[] array,int origin,int end){

        if (origin>=end){ //只有一个值吗，不再进行归并
            return;
        }

        int mid = (origin + end) / 2 ;
        //左归并
        Merge_Array(array,origin,mid);
        //右归并
        Merge_Array(array,mid+1,end);
        // 排序统计
        Merge(array,origin,end,mid);

    }

    public void Merge(int[] array,int orgin,int end,int mid){

        int[] temp = new int[end-orgin+1] ; //辅助数组
        int i = 0 ; //temp数组添加新结果，向后移动
        int p1 = orgin ; // 左边数组的起点
        int p2 = mid+1 ; // 右边数组的起点

        // p1 , p2 比较哪个小把哪个放到temp
        while (p1<=mid && p2 <=end){
            if (array[p1]<=array[p2]){
                temp[i++] = array[p1++] ;
            }else {
                temp[i++] = array[p2++] ;
                this.res = (this.res + mid - p1 + 1) % 1000000007;
                /**
                 * 数组A【7，8，9，10，11，12】
                 * 数组B【1，2，3，4，5，6】
                 * 
                 * 如果A[pa] > B[pb]
                 * 就说明 mid-pa+1个逆序数对
                 */
            }
        }

        if (p1>mid){  //说明左边全部添加到temp中，继续添加右边
            while (p2<=end){
                temp[i++] = array[p2++] ;
            }
        }

        if (p2>end){ //说明右边全部添加到temp中，继续添加左边
            while (p1<=mid){
                temp[i++] = array[p1++] ;
            }
        }

        //在原数组中用有序的值覆盖掉原来无序的值
        for (int j=0;j<temp.length;j++){
            array[orgin+j] = temp[j] ;
        }



    }