分治算法的思想

分治算法（divide and conquer）的核心思想其实就是四个字，分而治之 ，也就是将原问题划分成n个规模较小，并且结构与原问题相似的子问题，递归地解决这些 子问题，然后再合并其结果，就得到原问题的解。 这个定义看起来有点类似递归的定义。

关于分治和递归的区别，分治算法是一种处理问题的思想，递归是一种编程技巧。分治算法一般都比较适合用递归来实现。

分治算法的递归实现中，每一层递归都会涉及这样三个操作:

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

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

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

在归并排序的同时, 求原数组有多少个逆序对

public class LeetCode {

    public static void main(String[] args) {
        Merge merge = new Merge();
        int[] a = new int[]{1,5,6,2,3,4};
        merge.mergeStart(a);
        // 排序好的数组
        System.out.println(Arrays.toString(a));
        // 逆序对数
        System.out.println(merge.num);
    }
}

class Merge {
    /**
     * 存储原始数组有多少个逆序对
     */
    public int num = 0;
    
    public void mergeStart(int[] a) {
        merge(a, 0, a.length - 1);
    }

    private void merge(int[] a, int l, int r) {
        // l >= r代表当前已经无法分割
        if (l >= r) return;

        int mid = (l + r) / 2;

        merge(a, l, mid);
        merge(a, mid + 1, r);

        int left = l;
        int right = mid + 1;
        // 临时数组用来存储排序好的元素
        int[] tmp = new int[r - l + 1];
        // 临时数组下标
        int k = 0;
        // 当左指针和右指针后面还都有元素的时候
        while (left <= mid && right <= r) {
            if (a[left] < a[right]) {
                // 左指针数比右指针数小, 把左指针数放到临时数组
                tmp[k++] = a[left++];
            } else {
                tmp[k++] = a[right++];
                // 否则就是逆序对, 这时候左边数组里, 左指针后面的所有元素都比a[right]要大, 所以都是逆序对
                num += (mid - left + 1);
            }
        }
        // 处理左边剩下的数
        while (left <= mid) {
            tmp[k++] = a[left++];
        }
        // 处理右边剩下的数
        while (right <= r) {
            tmp[k++] = a[right++];
        }
        // 把排序好的数组赋值给原数组
        for (int i = 0; i < tmp.length; i++) {
            a[l + i] = tmp[i];
        }
    }
}