算法思想：分治 （Divide and Conquer）

分治的核心就是分而治之。是一种逐步把大问题拆解成小问题，通过解决小问题从而解决大问题的思想。

分治通常会使用递归实现，问题求解过程更加直观。分治算法的递归实现中，每一层递归都会涉及这样三个操作：

• 分解：将原问题分解成一系列子问题；
• 解决：递归地求解各个子问题，若子问题足够小，则直接求解；
• 合并：将子问题的结果合并成原问题。

思想

分治算法能解决的问题，一般需要满足下面这几个条件：

• 原问题与分解成的小问题具有相同的模式；
• 原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别；
• 具有分解终止条件，也就是说，当问题足够小时，可以直接求解；
• 可以将子问题合并成原问题，而这个合并操作的复杂度不能太高，否则就起不到减小算法总体复杂度的效果了。

统计逆序对的数目

问题描述：

给出一个int数组nums，求此数组的逆序对个数

最容易想到的方法是，遍历数组，对每个元素和其后面的每个元素相互比较，统计以该元素为首元素的逆序对个数：

public static int resolveCycle(int[] nums){  
    int sum = 0;  
    for (int i = 0; i < nums.length; i++){  
        for (int j = i + 1; j < nums.length; j++){  
            if (nums[i] > nums[j]){  
                sum ++;  
            }  
        }  
    }  
    return sum;  
}

此方法的时间复杂度是O(n^2).

我们也可以现将集合拆分成左右两部分，分别统计左右两部分的逆序对个数P(left)，P(right)。然后再统计左右合并部分的逆序对个数P(merge)，那么合并总的逆序对个数就是

P = P(left) + P(right) + P(merge)

实现：

package cn.lishiyuan.leetcode;  
  
/**  
 * 逆序对统计  
 *  
 */public class InversionPair {  
  
    /**  
     * 循环统计  
     * @param nums  
     * @return  
     */  
    public static int resolveCycle(int[] nums){  
        int sum = 0;  
        for (int i = 0; i < nums.length; i++){  
            for (int j = i + 1; j < nums.length; j++){  
                if (nums[i] > nums[j]){  
                    sum ++;  
                }  
            }  
        }  
        return sum;  
    }  
  
  
    /**  
     * 分治法解决  
     * @param nums  
     * @return  
     */  
    public static int resolveDAC(int[] nums){  
        return dac(nums,0,nums.length-1);  
    }  
  
      
    private static int dac(int[] nums,int start,int end){  
        if (end <= start){  
            return 0;  
        }  
        int mid = start + (end - start)/2;  
        int pL= dac(nums,start,mid);  
        int pR= dac(nums,mid+1,end);  
        int pM= merge(nums,start,mid,end);  
        return pL+pR+pM;  
    }  
  
    private static int merge(int[] nums, int start, int mid, int end) {  
        int count = 0;  
  
        int i = start;  
        int j = mid + 1;  
        int[] l = new int[(end - start) + 1];  
        for(int k = 0; k < l.length; k++){  
            // 如果左边已经完全到达末尾则将右边放进去就行  
            if(i > mid){  
                l[k] = nums[j];  
                j++;  
                continue;            }  
            // 如果右边已经完全到达末尾则将左边放进去就行  
            if(j > end){  
                l[k] = nums[i];  
                i++;  
                continue;            }  
            // 将小的那个放入  
            if (nums[i] <= nums[j]) {  
                l[k] = nums[i];  
                i++;  
            }else {  
                l[k] = nums[j];  
                // 逆序了统计逆序个数  
                // 由于左右两边都是有序的，如果i位置大于当前元素，那么i之后的所有元素都大于这个元素，也就是逆序的  
                count += (mid - i + 1);  
                j++;  
            }  
        }  
  
        // 将有序的元素放入原合集  
        System.arraycopy(l, 0, nums, start, l.length);  
  
        return count;  
    }  
  
  
}

实际上就是再归并排序过程中添加了统计逆序对的操作。

// 逆序了统计逆序个数  
// 由于左右两边都是有序的，如果i位置大于当前元素，那么i之后的所有元素都大于这个元素，也就是逆序的  
count += (mid - i + 1);