每日算法之数组中的逆序对

JZ51 数组中的逆序对

题目

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
方法1：暴力

思路

算法实现
两个for循环，如果前面的数大于后面的计数加1即可
问题
当输入数过大时，需要的时间会很长，所以此方法不行
代码

1. package mid.JZ51数组中的逆序对;
3. import java.util.ArrayList;
5. public class Solution {
6.      public int InversePairs1(int[] array) {
7.             int k = 1000000007;
8.             if (array.length <= 1) return 0;
9.             int res = 0;
10.    
11.             for (int i = 1; i < array.length; i++) {
12.                 for (int j = i - 1; j >= 0; j--) {
13.                     if (array[i] < array[j])
14.                         res++;
15.                 }
16.             }
17.             return res % k;
18.         }
19. }

复制代码

方法2 归并排序思想

思路

• 先分：分呢，就是将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止！
  
• 后并：并呢，就是从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组！
  
• 归并统计法，关键点在于合并环节，在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。
  

代码

[code]package mid.JZ51数组中的逆序对;import java.util.Arrays;public class Solution {    /**     * 分治     *     * @param array     * @return     */    public int count = 0;    public int InversePairs(int[] array) {        divMerge(array, 0, array.length-1);        return count;    }    public void divMerge(int[] array, int left, int right) {        if (left >= right) return;        int mid = left + (right - left) / 2;        //分左边        divMerge(array, left, mid);        //分右边        divMerge(array, mid + 1, right);        //合并        int i = left;        int j = mid + 1;        //临时数组        int[] tmp = new int[right - left + 1];        int k = 0;        while (i