一、递归算法

1.1 实例代码

递归算法的求解过程是将整个问题划分为若干个子问题，然后分别求子问题，最后获得整个问题的解。这是一种分而治之的思路，通常由整个问题划分的若干子问题的求解是独立的，所以求解过程对应一颗递归树

示例：求arr[L…R]上的最大值

思路：先求出中点，把数组分为两个区域，arr[L]-arr[mid]和arr[mid+1]-arr[R]

/*
* 递归算法
* 实例：得到一个最大值
* */
public class Recursion {
    public static int getMax(int[] arr){
        return process(arr,0,arr.length-1);
    }

    //arr[L..R]范围上求最大值
    public static int process(int[] arr, int L, int R) {
        if (L == R){  //只有一个数的时候直接返回
            return arr[L];
        }
        int mid = L+((R - L) >> 1);  //>>:右移一位，相当于除2
        int leftMax = process(arr, L, mid);  //左部分
        int rightMax = process(arr,mid+1,R);  //右部分
        return Math.max(leftMax,rightMax);
    }

    public static void main(String[] args) {
        int[] arr ={3,2,5,6,7,4};
        System.out.println(Recursion.getMax(arr));
    }
/*
* master算法
* 原理：T(N)=aT(N/b)+O(N^d)  子函数范围要相等
* a:调了几次子函数 b:子函数的范围 d:看其他执行的时间复杂度
* 判断master递归
* logb^a<d     o(N^d)
* logb^a>d     o(N^(logb^a))
* logb^a=d     o(N^d*logN)
* */
}

1.2 中点溢出问题

上面代码求中点是这行代码

int mid = L+((R - L) >> 1);
//等同于
int mid = L + (R-L)/2

为什么要这样用呢？可以不可以这样写？

int mid=（L+R）/2；

如果是这样求中点的话，会存在一个问题，如果数组的长度比较大，L+R可能会溢出

1.3 递归结构

假设测试的数组是[3,2,5,6,7,4]

运行结果：:

7

递归的每次往底层调用是这样的结构图

从这个递归结构图可以看出，所有的子节点汇总之后才能得到最终的P（0,5）。所以递归过程实际上就是用系统栈把整个过程压栈了，假设P（0,5）进栈，遇到调用P（0,2），将P（0,2）信息进栈，执行时又遇到P（0,1），再将P（0,1）进栈，以此类推。栈的空间就是整棵树的高度。

这其实就是二叉树遍历的过程。

经过调试就会发现，每一层递归得到的结果都返回给上一层，所以可以将其看做从底部不断往上汇总的一个过程

二、Master公式

Master公式是用来解决递归问题时间复杂度的公式。

公式如下：

T[N] = aT[N/b] + O(N^d)

注意：适用范围为子过程规模相等的情况，否则不适用。

分解看

T[n]：母问题的数据的规模是N

T[n/b]：子问题的规模都是N/b

a：子问题被调用的次数

O(N^d)：除去子问题调用之外过程的时间复杂度

用上面求解最大数的递归解法来看

T[N] = aT[N/b] + O(N^d)

=2T[N/2] + O(1)<–两个数最后比大小，时间复杂度为O(1)

所以上面的函数满足master公式，可以直接得到时间复杂度

①当d<log(b)a时，时间复杂度为O(N^(log(b)a))

②当d=log(b)a时，时间复杂度为O((N^d)*logN)

③当d>log(b)a时，时间复杂度为O(N^d)

证明过程略

三、归并排序

3.1 实例代码

1）整体就是一个简单递归，左边排好序、右边排好序、让其整体有序

2）让其整体有序的过程用了排外序方法

3）利用master公式来求解时间复杂度

4）归并排序的实质

时间复杂度O(N*logN)，额外空间复杂度O(n)

/*
 * 归并（合并）排序，整体就是一个简单递归，左边排好序，右边排好序，让其整体有序
 * 左右两边都有一个指向第一个数的指针，每次进行比较，小的数放进（新）数组中，
 * 一样大，默认放左边，如果哪侧越界了，就把剩下的部分拷贝过来就行了
 * */
public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    //递归
    private static void process(int[] arr, int L, int R) {
        if (L == R) {
            return;
        }
        int mid = L + ((R - L) >> 1);
        process(arr, L, mid);
        process(arr, mid + 1, R);
        merge(arr, L, mid, R);
    }
    //归并
    private static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int i = 0;
        int p1 = L;   //指向左边的第一个指针1
        int p2 = M + 1;  //指向右边的第一个指针2
        while (p1 <= M && p2 <= R) {  //如果指针1和指针2没有越界
            //新数组里依次放入，哪边指针的值小哪边放进去
            help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {   //如果p2指针（右半边）越界了，就把左半边的值全部放进去
            help[i++] = arr[p1++];
        }
        while (p2 <= R) {  //如果p1指针越界了（左半边），就把右半边所有的值全部放进去
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {  //把新数组的值
            arr[L + i] = help[i];
        }
    }
}

归并步骤如下：

1、在process(arr,L,mid);里让左边有序

2、在process(arr,mid+1,R);里让左边有序

3、用merge方法得到新排序好的数组

很多人不太明白为什么process里面就已经排好序了。这里依然用是递归方法，所以还是用结构图来解释

调用时merge()是在process()里面的，所以每次递归的时候都会调用merge()，所以排序实际上是在每次递归调用merge()里进行的。

例如：第一次递归调用到merge()时是左部分P(0,0)和P(1,1)，也就是子问题的相对左边(3)和相对右边(2)进行归并。通过算法得2先放进新数组help[]中，3再放入。所以传递给P(0,1)父问题的时候就已经排好序了---->[2,3]---->以此类推，最终汇总到P(0,5)的时候就是所有数有序

3.2 时间复杂度

所以说归并排序就是一个简单的递归，在此题中也是满足master公示的，它的时间复杂度为：

T(N) = 2T(N/2) + O(N)

a=2 b=2 d=1 ---->d=log(b)a

所以时间复杂度为O(N*logN)

3.3 额外空间度复杂度

归并排序的额外空间复杂度是O(N)

因为最多只用N的额外空间，每一次merge的时候都准备了一个空间，然后自动释放了（java里会自动释放）。所以最多申请一个长度为N的空间就可以了，不断复用，其额外空间复杂度就是O(N)

3.4 小和问题

问题描述：在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和。

例子：[1,3,4,2,5]

1左边比1小的数，没有；

3左边比3小的数，1；

4左边比4小的数，1、3；

2左边比2小的数，1；

5左边比5小的数，1、3、4、2；

所以小和为1+1+3+1+1+3+4+2=16

实现O(N*logN)

解题思路：把题目转换为，右边有多少个数比该数大，则产生多少该小和

例如：

1右边比1大的数，4个，产生4个1小和；

3右边比3大的数，2个，产生2个3小和；

…

然后用归并的方法，在左右两边，对比得到需产生的小和数（具体见代码）

/*
 * 小和问题
 * 在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和。求一个数组的小和
 * */
class SmallSum {
    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 2,5};
        System.out.println(SmallSum.smallSum(arr));
    }

    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    //arr[L,R]既要排好序，也要求小和
    private static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        return process(arr, l, mid)  //左侧排序并且求小和的数量
                + process(arr, mid + 1, r) //右侧排序求小和的数量
                + merge(arr, l, mid, r);  //左右都排好merge时候产生小和的数量
    }
    public static int merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            //左组比右组小？是，就把把右组后面所有数的个数（r-p2+1）乘以左组，即这次比较的小和数
            //这里要知道，左右两边都是有序排好了的，才可以这样
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            //左组小，左边指针移动，否则右边指针移动
            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 (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
        return res;
    }
}

运行结果：

16

四、快速排序3.0

4.1 实例代码

package Algorithm;
//快速排序3.0
public class QuickSort {
    public static void quickSort(int[] arr){
        if (arr == null || arr.length < 2){
            return;
        }
        quickSort(arr,0,arr.length -1);
    }
    //arr[1...r]排好序
    public static void quickSort(int[] arr,int L,int R){
        if (L<R){
            swap(arr,L+(int)(Math.random()*(R-L+1)),R); //等概率随机选一个位置，跟最右位置做交换
            int[] p = partition(arr,L,R); //返回两个值，划分区域的边界
            quickSort(arr,L,p[0]-1); //<区
            quickSort(arr,p[1]+1,R);// >区
        }
    }
    //这是一个处理arr[1...r]的函数
    //默认以arr[r]做划分，arr[r]->p    <p   ==p   >p
    //返回等与区域（左边界，右边界），所以返回一个长度为2的数组res,res[0] res[1]
    private static int[] partition(int[] arr, int L, int R) {
        int less = L -1; //<区右边界
        int more = R;  //>区左边界
        while (L < more){
            if (arr[L] < arr[R]){
                swap(arr,++less,L++);
            }else if (arr[L] > arr[R]){
                swap(arr,--more,L);
            }else {
                L++;
            }
        }
        swap(arr,more,R);
        return new int[]{less+1,more};
    }
//随机选的数和最右侧的数交换位置
    private static void swap(int[] arr, int random, int R) {
        int temp = arr[R];
        arr[R] = arr[random];
        arr[random] = temp;
    }
}

总结

这节课主要学习了递归算法，归并排序，用来计算递归算法时间复杂度的master公式和快速排序