递归及归并排序

递归：

（1）master公式：，用于求解子问题规模相同的递归行为的时间复杂度，其时间复杂度根据 a，b，d之间的关系确定如下：

；

；

；

其中：N是母问题的规模，a是递归问题的调用次数，b是母问题被分解成了多少个等规模的子问题，第二个加数部分是除子问题外剩余部分的时间复杂度

归并排序：

整体外排序，即使用额外空间，排好序后，再将额外空间中的数据拷贝回原数组

 归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)

原理：将原数组分为左右两半，分别使左一半有序和右一半有序，然后再将这两半合并成一个有序的数组。使用递归，左一半还可以再分，右一半同理，直到每一半只剩下一个元素，然后向上返回，逐层的合并。

优势：相比于简单排序，归并排序没有在确定每一个元素的位置时浪费掉之前的比较结果，每一次比较也不是独立的，而是在每次的比较过程中将其转变成了整体有序的一部分，因此时间复杂度较低。

 //归并排序

    /**
     * 整体的归并排序框架，使用递归，时间复杂度 O(N*logN)
     * 可以规定要排序的范围[l,r]
     * 外排序，使用额外的空间然后在拷贝回来
     * 实质：每一次比较归并的部分都没有被浪费，都变成整体的一部分传递下去利用
     * @param arr：要排序的数组
     * @param l：要进行归并排序的左边的下标
     * @param r：要进行归并排序的右边的下标
     */
    public static void mergeSort(int[] arr, int l, int r){
        if(l == r) return;
        int mid = l + ((r - l) >> 1);
        mergeSort(arr, l, mid);//对左一半进行归并排序
        mergeSort(arr, mid + 1, r);//对右一半进行归并排序
        merge(arr, l, mid, r);//对排好序的左右两边进行合并
    }

    //归并

    /**
     * 对左右两半排好序的数组进行合并
     * @param arr：左右两半排好序的数组
     * @param l：arr的左边下标
     * @param m：arr的中间下标
     * @param r：arr的右边下标
     */
    public static void merge(int[] arr, int l, int m, int r){
        int[] help = new int[r - l + 1];//辅助数组，大小等于要排列的区间范围大小
        int i = 0;
        int p1 = l, p2 = m + 1;
        while(p1 <= m && p2 <= r){
            help[i++] = arr[p1] >= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while(p1 <= m){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){
            help[i++] = arr[p2++];
        }
        for(int j = 0; j < help.length; j++){
            arr[l + j] = help[j];//！！！！
        }
    }

应用：小和问题

找出给定范围中的每个数的左侧比自己小的数求和，然后再把这些和相加。

方法：归并找出每个数右侧比自己大的数的个数m，然后就有m个该数相加。从最下层只有一个元素开始依次归并，统计右侧比左侧大的数有几个，一遍归并排序，一遍求和

注意：和传统的归并排序不同的是，当左右两边的数相等时，先将右侧的数放在排好序的额外数组中。因为如果先放左边的数，由该数产生的小和就会被跳过计算。

求和的过程中，既不遗漏，也不重复。不遗漏是因为在归并的过程中依次从一个扩张合并到整体的，不重复是因为在求和完成合并成一个整体后，不会再计算一个整体中的小和了。

  //小和问题
    public static int smallSum(int[] arr, int l, int r){
        if(arr == null || arr.length < 2 || l == r) return 0;
        int m = l + ((r - l) >> 1);
        //左半部分求出来的小和+右半部分求出来的小和+当前左右两边合并求出来的小和
        return smallSum(arr, l, m) + smallSum(arr, m + 1, r) + smallSumMerge(arr, l, m, r);
    }

    public static int smallSumMerge(int[] arr, int l, int m, int r){
        int res = 0;
        int[] help = new int[r - l + 1];
        int i = 0, p1 = l, p2 = m + 1;
        while(p1 <= m && p2 <= r){
            res += arr[p2] > arr[p1] ? (r - p2 + 1) * arr[p1] : 0;//！！！！！因为这一半已经有序，因此r到p2范围的数都比当前的arr[p1]大，每个都要加一次arr[p1]
            help[i++] = arr[p2] > arr[p1] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m){
            help[i++] = arr[p1++];
        }
        while (p2 <= r){ //后半部分大数即使剩下也无需再加，因为在第一个循环中使用的是(r - p2 + 1)，已经加过了
            help[i++] = arr[p2++];
        }
        for(int j = 0; j < help.length; j++){
            arr[l + j] = help[j];
        }
        return res;
    }

逆序对问题：左边的数比右边的数大的构成逆序对（与小和相反）