剑指OfferJZ35：数组中的逆序对-java版

JZ35：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007 对于50%50%的数据,size\leq 10^4size≤104 对于100%100%的数据,size\leq 10^5size≤105

暴力解法使用两个for循环会超出时间限制 我们考虑用归并排序（归并排序是稳定排序，是一种十分高效的排序）

归并排序：是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)

如图：将数组[8,4,5,7,1,3,6,2]变成有序数组 分：先按下标将数组从分成左右两部分（如果数组元素个数是奇数个，那就左边比右边多一个元素），接着对于左右两个子数组采取同样的操作，直到将整个数组完全肢解，全部分成只有一个元素的数组

治：将每一步分开的子数组排序后再原样进行合并； 比如图中的最后一次合并，是将[4,5,7,8]和[1,2,3,6]两个已经有序的子数组再进行排序后合并为最终的有序数组[1,2,3,4,5,6,7,8]

本题只是在归并合并的基础上多了一步，进行合并的同时统计逆序对个数

基本思路有了，那么要想解出这道题，必需要把归并排序的过程掌握清楚。 以下图为例： 分：划分区间 以数组元素的下标来划分，首先将数组的首元素下标用l标记，尾元素下标用r标记，mid=(l+r)/2

• 第一次划分：l=0,r=8,mid=(0+8)/2=4 区间[9，5，2，7，12，4，3，1，11]分成 左区间：l~mid 即[9，5，2，7，12] 右区间：mid+1~r 即[4，3，1，11]
• 第二次划分：同理，区间[9，5，2，7，12]分成 左区间：[9，5，2] 右区间：[7，12]
• 第三次划分：同理，区间[4，3，1，11]分成 左区间：[4，3] 右区间：[1，11]
• 第四次划分：同理，区间[9，5，2]分成 左区间：[9，5] 右区间：[2]
• 第五次划分：同理，区间[7，12]分成 左区间：[7] 右区间：[12]
• 第六次划分：同理，区间[4，3]分成 左区间：[4] 右区间：[3]
• 第七次划分：同理，区间[1，11]分成 左区间：[1] 右区间：[11]
• 第八次划分：同理，区间[9，5]分成 左区间：[9] 右区间：[5]

直到划分的所有区间长度为1时划分结束

 //分：划分区间
    private void divide(int l, int r, int[] array) {
        if(l!=r){
            int mid=(l+r)>>1;//(l+r)>>1 代表 l+r的值右移1位，相当于l+r的值除以2取整
            divide(l,mid,array);//左区间
            divide(mid+1,r,array);//右区间
            merge(l,r,mid,array);//治
        }
    }

治：合并两个子区间

用i表示左区间的下标，用j表示右区间的下标，其中i=l,j=mid+1分别定为左右区间的起始下标 接着建立一个长度等于原数组长度的临时数组，用于存放临时合并的数组，避免递归过程中频繁开辟空间

• 如果左右区间都有数字（即i