第6 章、递归

6.1 、递归应用场景

看个实际应用场景，迷宫问题(回溯)， 递归(Recursion)

6.2、 递归的概念

• 简单的说: 递归就是方法自己调用自己,每次调用时传入不同的变量.递归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

6.3 、递归调用机制

列举两个小案例来理解递归

• 1) 打印问题
• 2) 阶乘问题
• 3) 使用图解方式说明了递归的调用机制

打印问题的代码实现：

/**
 * description
 * 递归案例测试--打印问题
 *
 * @author
 * @since 2022/11/18 11:12
 */
public class RecursionTest {
    public static void main(String[] args) {
        //通过打印的案例了解递归的调用机制
        test(4);
    }

    public static void test(int n){
        if (n> 2){
            test(n -1);
        }
        System.out.println("n=" + n);
    }
}

代码分析：程序执行时会先进入主方法

• 根据Java虚拟机的结构分为三个部分 ---栈、堆、代码区（常量也是放在这的）

• 当程序执行到主方法时，首先会在栈里开辟一个独立的空间

• 由此得出递归调用规则

  • 1、当程序执行到一个方法时，就会开辟一个独立的空间（栈）
  • 2、 每个空间的数据（局部变量）是独立的

  

  图解：首先当程序走到main方会在栈内开辟相应的独立空间执行到相应的独立空间时都会执行一条打印语句直至退出

2）通过阶乘问题来了解递归机制

以下是代码实现

/**
 * description
 * 递归案例测试--阶乘问题
 *
 * @author
 * @since 2022/11/18 11:12
 */
public class RecursionTest {
    public static void main(String[] args) {
        int result = factorial(3);
        System.out.println("result=" +result);
    }

    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        } else {
            return factorial(n - 1) * n;
        }
    }
}

代码分析：当程序执行到主方法时，首先会在栈里开辟一个独立的空间，且每个空间的数据（局部变量）是独立的

• 那么我们可以结合案例得出结论
• 代码中n = 3显然是大于1的，所以只有2和3进入到else，进入后变成了两个个整体，即factorial（2-1） factorial（3-1） n ，得出表达式就是 1 2 3 ，结果自然是六
• 大白话理解就是，栈都还是那个栈，但是局部变量都是独立的

6.4 、递归能解决什么样的问题

递归用于解决什么样的问题

1) 各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大赛)

2) 各种算法中也会使用到递归，比如快排，归并排序，二分查找，分治算法等.

3) 将用栈解决的问题-->第归代码比较简洁

6.5 、递归需要遵守的重要规则

递归需要遵守的重要规则

• 1) 执行一个方法时，就创建一个新的受保护的独立空间(栈空间)
• 2) 方法的局部变量是独立的，不会相互影响, 比如 n 变量
• 3) 如果方法中使用的是引用类型变量(比如数组)，就会共享该引用类型的数据.
• 4) 递归必须向退出递归的条件逼近，否则就是无限递归,出现 StackOverflowError，死龟了:)
• 5) 当一个方法执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当方法执行完毕或者返回时，该方法也就执行完毕

6.6 、递归-迷宫问题

6.6.1、迷宫问题

6.6.2、代码实现:

/**
 * description
 * 使用递归解决迷宫回溯问题
 *
 * @author
 * @since 2022/11/19 8:35
 */
public class Maze {
    public static void main(String[] args) {
        //先创建一个二维数组，模拟迷宫
        int[][] map = new int[8][7];
        //使用1表示墙,上下全部置为1
        for (int i = 0; i < 7; i++) {
            map[0][i] = 1;
            map[7][i] = 1;
        }
        //把左右的墙也置为1
        for (int i = 0; i < 8; i++) {
            map[i][0] = 1;
            map[i][6] = 1;
        }

        //设置相应的挡板
        map[3][1] = 1;
        map[3][2] = 1;

        //输出这个地图
        System.out.println("当前地图情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }

        //使用递归回溯给小球找路
        setWay(map,1,1);
        //输出新的地图，小球走过并标示过的地图
        System.out.println("小球走过并标示过的地图情况");
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 7; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println();
        }
    }

    /**
     * 说明：
     * 1、map表示地图
     * 2、i，j 表示地图的哪个位置开始出发(1,1)
     * 3、如果小球能到 map[6][5]位置，则说明通路找到
     * 4、约定：当map[i][j] 为0时表示还没有走过，当为1时表示墙，若为2表示通路可以走；若为3表示走过的路
     * 5、在走迷宫之前需要提前确定路线：依照顺序依次走  下→右→上→左，如果该点走不通再回溯
     * 使用递归回溯来给小球找路
     *
     * @param map 表示地图
     * @param i   从哪个位置开始找
     * @param j   同上
     * @return 如果找到路了返回true，反之返回false
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) { //通路已经找到
            return true;
        } else {
            if (map[i][j] == 0) { //如果当前点还没有走过
                //按照策略走下→右→上→左
                map[i][j] = 2;  //假定该点是可以走通的
                if (setWay(map, i + 1, j)) {  //向下走
                    return true;
                } else if (setWay(map, i, j + 1)) {
                    return true;
                } else if (setWay(map, i - 1, j)) {
                    return true;
                } else if (setWay(map, i, j - 1)) {
                    return true;
                } else {
                    //说明该点是死路，走不通
                    map[i][j] = 3;
                    return false;
                }
            } else { //如果map[i][j]!=0 ,可能是1，2，3
                return false;
            }
        }
    }
}

代码说明：

• 1、map表示地图
• 2、i，j 表示地图的哪个位置开始出发(1,1)
• 3、如果小球能到 map [ 6 ] [ 5 ] 位置，则说明通路找到
• 4、约定：当map [ i ] [ j ] 为0时表示还没有走过，当为1时表示墙，若为2表示通路可以走；若为3表示走过的路
• 5、在走迷宫之前需要提前确定路线：依照顺序依次走 下→右→上→左，如果该点走不通再回溯
• 6、小球的走的路径与定制的策略有关

6.7 、递归-八皇后问题(回溯算法)

6.7.1、八皇后问题介绍

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848 年提出：在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即：任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法(92)。

6.7.2、八皇后问题算法思路分析

1) 第一个皇后先放第一行第一列

2) 第二个皇后放在第二行第一列、然后判断是否 OK， 如果不 OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适

3) 继续第三个皇后，还是第一列、第二列……直到第 8 个皇后也能放在一个不冲突的位置，算是找到了一个正确解

4) 当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到. 5) 然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4 的步骤

6) 思路分析

• 1、 第一个皇后先放第一行第一列
• 2、第二个皇后放在第二行第一列、然后判断是否OK[即判断是冲突]， 如果不OK，继续放在第二列、第三列、依次把所有列都放完，找到一个合适
• 3、继续第三个皇后，还是第一列、第二列……直到第8个皇后也能放在一个不冲突的位置，算是找到了一个正确解
• 4、当得到一个正确解时，在栈回退到上一个栈时，就会开始回溯，即将第一个皇后，放到第一列的所有正确解，全部得到
• 5、然后回头继续第一个皇后放第二列，后面继续循环执行 1,2,3,4的步骤

• 说明：
  • 理论上应该创建一个二维数组来表示棋盘，但是实际上可以通过算法，用一个一维数组即可解决问题. arr[8] ={0 , 4, 7, 5, 2, 6, 1, 3} //对应 arr 下标 表示第几行，即第几个皇后，arr[i] = val , val 表示第i+1 个皇后，放在第i+1行的第 val+1 列

6.7.3、八皇后问题算法代码实现

/**
 * description
 * 使用回溯算法解决八皇后问题
 *
 * @author
 * @since 2022/11/20 9:35
 */
public class Queue {

    //1、先定义一个max表示共有多少个皇后
    int max = 8;
    //2、再定义一个数组array,用于保存放置皇后位置的结果
    int[] array = new int[max];

    //3、定义一个变量count来同居共有多少种写法
    static int count = 0;

    public static void main(String[] args) {
        //测试一把
        Queue queue = new Queue();
        queue.check(0);
        System.out.printf("一共有%d种解法", count);
    }

    //3、编写一个方法，放置第n个皇后
    private void check(int n) {
        if (n == max) {  //n =8
            point();
            return;
        }
        //3.1、依次放入皇后并判断是否冲突
        for (int i = 0; i < max; i++) {
            //3.2、先把当前皇后 n ，放到该行的第一列
            array[n] = i;
            //3.3、判断当放置第n个皇后到i列时是否冲突
            if (judge(n)) {  //不冲突
                //3.3、接着放n+1个皇后，即开始递归
                check(n + 1);
            }
            //3.4、如果冲突就继续执行array[n] = i,即将第n个皇后放置在本行的后移的一个位置
        }
    }

    /**
     * 4、定义一个方法查看当我们放置第n个皇后，就去检测该皇后是否和前面已经摆放的皇后冲突
     *
     * @param n 表示第n个皇后
     * @return
     */
    private boolean judge(int n) {
        for (int i = 0; i < n; i++) {
            /**
             *  4.1、array[i] == array[n] 表示判断第n个皇后是否和前面的n-1个皇后在同一列
             *  4.2、Math.abs(n-i) == Math.abs(array[n] - array[i] 表示判断第n个皇后是否和第i个皇后是否在同一斜线
             */
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) {
                return false;
            }
        }
        return true;
    }

    //4、定义一个方法，将皇后摆放的位置输出
    private void point() {
        count++;
        for (int j : array) {
            System.out.print(j + " ");
        }
        System.out.println();
    }
}

七、排序算法

7.1 、排序算法的介绍

• 排序也称排序算法(Sort Algorithm)，排序是将一组数据，依指定的顺序进行排列的过程

7.2 、排序的分类：

1) 内部排序: 指将需要处理的所有数据都加载到内部存储器(内存)中进行排序。

2) 外部排序法： 数据量过大，无法全部加载到内存中，需要借助外部存储(文件等)进行排序。

3) 常见的排序算法分类(见右图):

7.3 、算法的时间复杂度

7.3.1、度量一个程序(算法)执行时间的两种方法

• 1) 事后统计的方法 这种方法可行, 但是有两个问题：一是要想对设计的算法的运行性能进行评测，需要实际运行该程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素, 这种方式，要在同一台计算机的相同状态下运行，才能比较哪个算法速度更快
• 2) 事前估算的方法:通过分析某个算法的时间复杂度来判断哪个算法更优

7.3.2、时间频度

• 基本介绍

时间频度：一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为 T(n)。

• 比如计算 1-100 所有数字之和, 我们设计两种算法：

• 忽略常数项

结论:

1) 2n+20 和 2n 随着 n 变大，执行曲线无限接近, 20 可以忽略

2) 3n+10 和 3n 随着 n 变大，执行曲线无限接近, 10 可以忽略

• 忽略低次项

结论:

1) 2n^2+3n+10 和 2n^2 随着 n 变大, 执行曲线无限接近, 可以忽略 3n+10

2) n^2+5n+20 和 n^2 随着 n 变大,执行曲线无限接近, 可以忽略 5n+20

• 忽略系数

结论:

1) 随着 n 值变大，5n^2+7n 和 3n^2 + 2n ，执行曲线重合, 说明 这种情况下, 5 和3 可以忽略。

2) 而 n^3+5n 和 6n^3+4n ，执行曲线分离，说明多少次方式关键

7.3.3、时间复杂度

1) 一般情况下，算法中的基本操作语句的重复执行次数是问题规模 n 的某个函数，用T(n)表示，若有某个辅助函数 f(n)，使得当 n 趋近于无穷大时，T(n) / f(n) 的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作 T(n)=Ｏ( f(n) )，称Ｏ( f(n) ) 为算法的渐进时间复杂度，简称时间复杂度。

2) T(n) 不同，但时间复杂度可能相同。 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为 O(n²)。

3) 计算时间复杂度的方法：

• 用常数 1 代替运行时间中的所有加法常数 T(n)=n²+7n+6 => T(n)=n²+7n+1
• 修改后的运行次数函数中，只保留最高阶项 T(n)=n²+7n+1 => T(n) = n²
• 去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)

7.3.4、常见的时间复杂度

1) 常数阶 O(1)

2) 对数阶 O(log2n)

3) 线性阶 O(n)

4) 线性对数阶 O(nlog2n)

5) 平方阶 O(n^2)

6) 立方阶 O(n^3)

7) k 次方阶 O(n^k)

8) 指数阶 O(2^n)

常见的时间复杂度对应的图:

说明：

1) 常见的算法时间复杂度由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(nk) ＜Ο(2n) ，随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法的执行效率越低

2) 从图中可见，我们应该尽可能避免使用指数阶的算法

• 1、常数阶 O(1)
  • 无论代码执行力多少行，只要是没有循环等复杂结构，那么走过代码的时间复杂度就都是O(1)

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万行甚至几十万行，都可以用O(1)来表示它的时间复杂度

• 2、 对数阶 O(log2n)

说明：在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2n也就是说当循环 log2n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(log2n) 。 O(log2n) 的这个2 时间上是根据代码变化的，i = i * 3 ，则是 O(log3n) .

如果N=a(a>0,a*1)，即a的x次方等于N (a>0，且af1)，那么数x叫做以a为底N的对数(lgarithm)，记作log。 。其中，a叫做对数的底数，N叫做真数，x叫做"以a为底N的对数”。

• 3、线性阶O(n)

说明：这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度

• 4、线性对数阶O(nlogN)

说明：线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)

• 5)平方阶O(n²)

说明：平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²)，这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(nn)，即 O(n²) 如果将其中一层循环的n改成m，那它的时间复杂度就变成了 O(mn)

• 6、立方阶O(n³)、K次方阶O(n^k)

说明：参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似

7.3.5、平均时间复杂度和最坏时间复杂度

1) 平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间。

2) 最坏情况下的时间复杂度称最坏时间复杂度。一般讨论的时间复杂度均是最坏情况下的时间复杂度。这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限，这就保证了算法的运行时间不会比最坏情况更长。

3) 平均时间复杂度和最坏时间复杂度是否一致，和算法有关(如表所示:)。

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n²)	O(n²)	稳定	O(1)	n小时较好
交换	O(n²)	O(n²)	不稳定	O(1)	n小时较好
选择	O(n²)	O(n²)	不稳定	O(1)	n小时较好
插入	O(n²)	O(n²)	稳定	O(1)	大部分已排序时较好
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9),R是基数(个十百)
Shell	O(nlogn)	O(n²) 1< s <2	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好

7.4 、算法的空间复杂度简介

7.4.1、基本介绍

1) 类似于时间复杂度的讨论，一个算法的空间复杂度(Space Complexity)定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。

2) 空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模 n 有关，它随着 n 的增大而增大，当 n 较大时，将占用较多的存储单元，例如快速排序和归并排序算法, 基数排序就属于这种情况

3) 在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品(redis, memcache)和算法(基数排序)本质就是用空间换时间.

7.5 、冒泡排序

7.5.1、基本介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒

优化： 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)

7.5.2、演示冒泡过程的例子(图解)

小结：

• (1) 一共进行 数组的大小-1 次 大的循环
• (2)每一趟排序的次数在逐渐的减少
• (3) 如果我们发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。这个就是优化

举一个具体的案例来说明冒泡法。我们将五个无序的数：3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。

7.5.3、冒泡排序应用实例

• 将五个无序的数：3, 9, -1, 10, -2 使用冒泡排序法将其排成一个从小到大的有序数列。 代码实现如下

/**
 * description
 * 冒泡排序的案例——将五个无序数组进行排序
 *
 * @author
 * @since 2022/11/21 12:31
 */
public class BubbleSort {
    public static void main(String[] args) {
        //首先定义一个一维数组，并定义五个无序数字
        int[] arr = {3, 9, -1, 10, -2};
        int temp = 0; //临时变量
        for (int i = 0; i < arr.length - 1; i++) {
            //第一趟排序，将最大的数排在最后
            for (int j = 0; j < arr.length -1 - i; j++) {
                //如果前面的数比后面的数大，则进行交换，否则不进行处理
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            System.out.println("第"+ (i+1) + "排序后的数组");
            System.out.println(Arrays.toString(arr));
        }
    }

代码执行结果：

冒泡排序执行完毕，还可以进行优化，优化思路如下：

• 优化： 因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志 flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排序写好后，在进行)
• 代码实现如下：

/**
 * description
 * 冒泡排序的案例——将五个无序数组进行排序
 *
 * @author
 * @since 2022/11/21 12:31
 */
public class BubbleSort {
    public static void main(String[] args) {
        //首先定义一个一维数组，并定义五个无序数字
        int[] arr = {3, 9, -1, 10, -2};
        System.out.println("排序前=" + Arrays.toString(arr));
        //测试冒泡排序
        bubbleSort(arr);
        System.out.println("排序后=" + Arrays.toString(arr));
    }

    //将冒泡排序封装成一个方法
    public static void bubbleSort(int[] arr) {
        int temp = 0; //临时变量
        boolean flag = false;  //标识变量，标识是否进行过交换
        for (int i = 0; i < arr.length - 1; i++) {
            //第一趟排序，将最大的数排在最后
            for (int j = 0; j < arr.length - 1 - i; j++) {
                //如果前面的数比后面的数大，则进行交换，否则不进行处理
                if (arr[j] > arr[j + 1]) {
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag) { //在一趟排序中，一次交换都没有发生过
                break;
            } else {
                flag = false;  //重置flag，进行下一次判断
            }
        }
    }
}

7.5.4、冒泡排序的力扣练习题——移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

思路分析

• 这里参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。
• 这里我们可以用0当做这个中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。
  这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]
• 请对照动态图来理解：

代码实现

/**
 * 力扣练习题：移动零
 * 思路参考笔记...
 */
public class BubbleSort {
    
    
    public void moveZeroes(int[] nums) {
    
    
        if (nums == null) {
    
    
            return;
        }
        //两个指针i和j
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
    
    
            //当前元素!=0，就把其交换到左边，等于0的交换到右边
            if (nums[i] != 0) {
    
    
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }
}