数据结构与算法（Java语言版）课件 第3、4章 递归算法、数组与Arrays类

第3章递归算法2024/11/91主要内容● 递归算法● 递归的复杂度● 问题与子问题● 递归与迭代● 多重递归● 经典递归● 优化递归递归算法是非常最重的算法，是很多算法的基础算法。递归算法不仅能使得代码优美简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，而且具有很好的可读性。和排序算法不同，许多经典的排序算法已经是玲珑剔透、日臻完善，在许多应用中只要选择一种排序算法直接使用即可（见第4章和第12章），而对于递归算法，真正理解递归算法内部运作机制的细节、才能真对实际问题正确的使用递归算法或写出正确的递归算法。3.1递归算法递归算法是指一个方法在执行过程中又调用了自身、形成了递归调用，这样的方法被称为递归方法或递归算法。2024/11/92

2024/11/933.1递归算法递归过程中的压栈、弹栈方法f递归过程是，第k次调用f需要等待第k+1次调用f结束执行过程后才能结束执行过程。那么第R(n)次（最后一次）调用f结束执行过程后，就会依次使得第k次调用结束执行过程。方法被调用时，方法的（入口）地址会被压入栈（栈是一种先进后出的结构）中，称为压栈操作，同时方法的局部变量被分配内存空间。

……调用调用调用调用调用结束

结束

结束

结束结束

图3.1递归执行过程第1次调用第R(n)次调用2024/11/943.1递归算法递归过程中的压栈、弹栈方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。递归过程的压栈操作可以让栈的长度不断增加，而弹栈操作会让栈的长度变小，最终使栈的长度为0。…………

第1次弹栈第m次弹栈第k次弹栈第1次压栈第m次压栈第k次压栈2024/11/953.1递归算法时间复杂度方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。要针对具体的递归方法，来计算该递归方法的时间复杂度。递归方法是一个递归过程，从递归开始到递归结束，方法被调的总数R(n)是依赖于一个正整数n的函数。那么递归方法中基本操作被执行的总数T(n)就依赖递归的总数R(n)和每次递归时基本操作被执行的总数。2024/11/963.1递归算法空间复杂度方法调用结束，会进行弹栈，称为弹栈操作，同时释放方法的局部变量所占的内存。递归会让栈的长度不断发生变化，如果栈的长度较大可能导致栈溢出，使得进程（运行的程序）被操作系统终止。递归过程的压栈操作增加栈的长度、弹栈操作减小栈的长度。递归过程中可能交替地进行压栈操作和弹栈操作，直至栈的长度为0（见例子2）。计算出递归过程中，某一时刻（某一次递归）栈出现的最大长度和每次递归中方法的局部变量所占的内存空间，即计算出栈最大长度以及局部变量所占的全部内存空间和所依赖的正整数的关系，才可以知道空间复杂度。2024/11/973.2线性递归与非线性递归●线性递归线性递归是指，每次递归时，方法调用自身一次。

如果我们忘记了今天是星期几，就需要知道昨天是星期几，如此这般地向前（过去）翻日历（相当于递归里的压栈，导致栈的长度在增加），等到能翻到某个日历页上显示了星期几，就结束翻阅日历（相当于结束压栈），然后再一页一页的撕掉日历（相当于弹栈），日历上神奇地出现了星期数，即方法依次计算出自己的返回值。Week.java例子1Example3_1.java2024/11/983.2线性递归与非线性递归●线性递归递归方法f(intn)的递归的总次数：R(n)=n，而每次递归的基本操作只有2个基本操作，因此时间复杂度是O(n)。向下方向的弧箭头表示方法被调用，向上方向的直箭头表示方法调用结束。例子1压栈操作过程中得到的栈的最大长度是R(n)=n，空间复杂度是O(n)。2024/11/993.2线性递归与非线性递归●非线性递非线性递归是指，每次递归时方法，调用自身2次或2次以上。

Fibonacci.java例子2Example3_2.java2024/11/9103.2线性递归与非线性递归●非线性递例子2递归过程中，每次递归时方法调用自身2次，使得每次递归出现了2个递归“分支”，然后选择一个分支，继续递归，直到该分支递归结束，再沿着下一分支继续递归，当2个分支都递归结束，递归过程才结束，而且递归过程交替地进行压栈和弹栈操作，直至栈的长度为0。

2024/11/9113.3问题与子问题将规模大的问题，使用递归算法逐步分解成规模小的问题，最终解决规模大的问题。一个问题的子问题就是数据规模比此问题的规模更小的问题。当一个问题，可以分解成许多子问题时就可以考虑用递归算法来解决这个问题。2024/11/9123.3问题与子问题

SumMulti.java例子3Example3_3.java2024/11/9133.3问题与子问题

Reverse.java例子4Example3_4.javaMaxInArray.java2024/11/9143.4递归与迭代递归的思想是根据上一次操作的结果，确定当前操作的结果。迭代的思想是，根据当前操作的结果，确定下一次操作的结果。对于解决相同的问题，递归代码简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，具有很好的可读性。由于迭代不涉及方法的递归调用，所以，通常情况下递归算法的空间复杂度会大于迭代的复杂度，当递归过程的递归总数比较大时，会导致栈溢出。2024/11/9153.4递归与迭代例子5中ComputePI类中的recursionMethod(intn)方法和iterationMethod(intn)都是通过计算级数的近似值返回圆周率的近似值，recursionMethod(intn)使用的是递归，iterationMethod(intn)使用的是迭代。ComputePI.java例子5Example3_5.java2024/11/9163.4递归与迭代

SearchNumber.java例子6Example3_6.java

2024/11/9173.4递归与迭代Euclidean.java例子7Example3_7.java

2024/11/9183.5多重递归所谓多重递归，是指一个递归方法调用另一个或多个递归方法，称该递归方法多重递归方法。

不要求输出含有偶数多个6的数。

2024/11/9193.5多重递归

2024/11/9203.6经典递归选择三个经典的递归：杨辉三角形、老鼠走迷宫和汉诺塔，进一步体会递归算法不仅能使得代码优美简练，容易理解解决问题的思路或发现数据的内部的逻辑规律，而且具有很好的可读性。特别是汉诺塔递归，通过其递归算法，洞悉其数据规律，给出相应的迭代算法。经典的递归：杨辉三角形，老鼠走迷宫，汉诺塔2024/11/9213.6经典递归杨辉三角

最早出现于中国南宋数学家杨辉1261年所著的《详解九章算法》中。法国数学家帕斯卡（Pascal）在1654年发现该三角形，所以又称帕斯卡三角形。

2024/11/9223.6经典递归杨辉三角最早出现于中国南宋数学家杨辉1261年所著的《详解九章算法》中。法国数学家帕斯卡（Pascal）在1654年发现该三角形，所以又称帕斯卡三角形。

2024/11/9233.6经典递归PascalTriangle.java例子9Example3_9.java杨辉三角

YanhuiTriangle.java

2024/11/9243.6经典递归老鼠走迷宫老鼠首先向东走，如果走到出口结束递归，否则向南…向西…向北。

2024/11/9253.6经典递归老鼠走迷宫例子10的主类Example3_10使用move(int[][]a,inti,intj)方法走迷宫。其中，用int型二维数组模拟迷宫，二维数组元素值是1表示墙，0表示路，2表示出口。老鼠走过迷宫后，输出老鼠走过的路时，用☆表示老鼠走过的路，■表示墙，★表示出口，□表示老鼠未走过的路。Mouse.java例子10Example3_10.java2024/11/9263.6经典递归汉诺塔（递归算法）汉诺塔(HanoiTower)问题是来源于印度的一个古老问题。有名字为A，B，C的三个塔，A塔上有从小到大64个盘子，每次搬运一个盘子，最后要把64个盘子搬运到C塔。在搬运盘子的过程中，可以把盘子暂时放在3个塔中的任何一个上，但不允许大盘放在小盘上面。3个盘子的汉诺塔

2024/11/9273.6经典递归汉诺塔（递归算法）3个盘子的汉诺塔

HannoiTower.java例子11Example3_11.java2024/11/9283.6经典递归汉诺塔（迭代算法）

这些规律是通过研究汉诺塔的递归算法发现的。就像本章一开始说的，递归可以发现数据的内部的逻辑规律。2024/11/9293.6经典递归汉诺塔（迭代算法）

一个偶数通过不断地右位移可计算出尾部连续的0的个数，例如：8的二进制1000右位移3次，得到奇数，因此知道8的二进制尾部连续0的个数是3。这些规律是通过研究汉诺塔的递归算法发现的。就像本章一开始说的，递归可以发现数据的内部的逻辑规律。2024/11/9303.6经典递归汉诺塔（迭代算法）这些规律是通过研究汉诺塔的递归算法发现的。就像本章一开始说的，递归可以发现数据的内部的逻辑规律。

HanoiTowerIterator.java例子12ZeroCount.javaExample3_12.java2024/11/931计算Fibonacci序列的递归过程中需要将f(n-1)分支进行完毕，再进行f(n-2)分支。需要注意到的是，在进行f(n-1)分支递归时，会完成了f(n-2)分支递归，那么再进行f(n-2)分支就是一个重复的递归过程。简而言之，优化递归就是避免重复子递归。优化递归就是在每次递归开始前，首先到某个对象中，通常为散列表对象，也可以是数组，查找本次递归是否已经被实施完毕，即是否已经有了递归结果，如果散列表对象中已经有了本次递归的结果，就直接使用这个结果，不再浪费时间进行本次递归，否则就进行本次递归，并将递归结果保存到散列表对象。3.7优化递归2024/11/9323.7优化递归

OptimizeFibonacci.java例子13Example3_13.javaOptimizeFibonacci类的散列表是静态成员变量，会不断累积子递归的结果，尽管会浪费内存空间，但会使得后面的递归速度越来越快。2024/11/9333.7优化递归

OptimizePascalTriangle.java例子14Example3_14.javaOptimizePascalTriangle类的散列表是静态成员变量，会不断累积子递归的结果，尽管会浪费内存空间，但会使得后面的递归速度越来越快。第4章数组与Arrays类2024/11/934主要内容● 数组的引用● 数组的排序● 数组的二分查找●数组的复制● 数组的比较● 数组的匹配● 公共子数组● 数组的更新● 数组的前缀运算● 数组的动态遍历● 数组与洗牌● 数组与生命游戏

数组是最常用的一种线性数据结构，数组一旦被创建，那么数组的长度（数组的元素的个数）就不可以再发生变化，即不可以对数组进行删除，添加或插入操作。关于数组的算法还是非常多的，比如排序，复制，二分查找，动态遍历等。4.1引用与参数存值

2024/11/9352024/11/9364.1引用与参数存值1.数组的引用数组属于引用型数据，即数组中存放着一个引用值，数组使用下标运算访问自己的元素（下从0开始，每个元素的下标等于它前面的元素的个数）。可以让System类调用静态方法intidentityHashCode(Objectobject)返回（得到）数组a的引用：intaddress=System.identityHashCode(a);也可以让数组a调用inthashCode()方法返回（得到）数组的引用：intaddress=a.hashCode();两个类型相同的数组，一旦二者的引用相同，二者就具有相同的元素。2024/11/9374.1引用与参数存值1.数组的引用数组属于引用型数据，即数组中存放着一个引用值，数组使用下标运算访问自己的元素（下从0开始，每个元素的下标等于它前面的元素的个数）。例子1中的主类Example4_1使用了intidentityHashCode()方法和inthashCode()方法，注意例子1的输出结果，特别是数组b的值（b的引用）赋值给数组a之后，程序的输出结果。例子1Example4_1.java2024/11/9384.1引用与参数存值2.参数存值使用参数存储值就是一个方法可以将某些数据存放在参数中，如果参数是引用类型，比如数组，那么方法执行完毕，保存在参数中的值一直还存在、不会消失。例子2Example4_2.java当a，b，c构成等边三角形时返回3，将三角形面积存放在数组area的元素中，构成等腰三角形时（不是等边）返回2，将三角形面积存放在数组area的元素中，构成三角形时（不是等边，也不是等腰）返回1，将三角形面积存放在数组area的元素中，不构成三角形时返回0，将Double.NaN（没有值）存放在数组area的元素中。Triangle.java2024/11/9394.1引用与参数存值2.参数存值使用参数存储值就是一个方法可以将某些数据存放在参数中，如果参数是引用类型，比如数组，那么方法执行完毕，保存在参数中的值一直还存在、不会消失。例子3Example4_3.java例子3中char型数组的元素值是某个小写英文字母，FindLetters类中的findMaxCountLetters(char[]english,int[]saveCount)方法返回char型数组中出现次数最多的字母之一，并将这个字母出现的次数存放到参数指定的int型数组的元素中。FindLetters.java4.2数组与排序2024/11/940排序算法是重要的基础算法。各种排序算法都是非常成熟的算法，Arrays类封装了快速排序和归并排序，编写程序时直接使用即可。2024/11/9414.2数组与排序1.快速排序

双轴快速排序不是稳定排序。稳定排序是指，数组里大小一样的数据，排序后，保持原始的先后顺序不变。起泡法是稳定排序，而选择法是不稳定排序。如果是给对象排序（非基本类型数据），那么创建对象类需要实现Comparable<T>泛型接口来指定对象的大小关系，否则，sort()方法将按对象的引用排序对象，这种排序往往没有什么实际意义（就像生活中，很少按人的身份证排序）。快速排序是一种基于递归的经典排序算法。它的思路是选定一个基准元素，然后把比这个元素小的元素放在它左边，比它大的元素放在它右边。再分别对它左边和右边的元素进行递归处理，直到排序完成。2024/11/9424.2数组与排序1.快速排序

例子4Example4_4.javaStudent.java

主类Example4_4分别使用Arrays类的sort(Object[]a)方法和我们自己定义的BasicSort类中的方法，按身高（height）排序Student类的对象。BasicSort.java2024/11/9434.2数组与排序2.归并排序例子5Example4_5.javaMerge.java

例子5里，我们依然给出了归并排序算法，其目的是体现递归算法的重要性（归并排序使用了递归算法），在实际应用中，完全没必要这样做，只需用Arrays类的parallelSort()方法即可，让你的代码更加简练有效。归并排序算法如下：①将待排序数组分成两个子数组，每个子数组通过递归进行排序。②将两个排好序的子数组合并成一个有序数组。4.3数组的二分查找2024/11/944二分法可用于查找一个数据是否在一个升序数组中。我们曾在第2章的例子9，第3章的例子6介绍过二分法。因为二分法是成熟的经典算法，所以Java将其作为一个方法封装在Arrays类中。在开发程序时，可以直接使用Arrays类即可，不必再像第2章例子9或第3章的例子6去编写算法的具体代码。2024/11/9454.3数组的二分查找1.二分法例子6Example4_6.java例子6的主类Example4_6，在循环10000次的循环语句的循环体中，每次使用Random对象得到1至7之间的一个数字。循环结束后输出1至7之间的各个数字出现的次数,该例子中使用了Arrays类中的binarySearch()方法。Arrays类中的binarySearch()方法是一个重载的方法，该方法使用二分法算法查找一个数据key是否在升序数组a中，如果在数组中，返回和key相等的数组元素的索引位置，如果不在数组中，返回一个负数（不一定是-1）2024/11/9464.3数组的二分查找1.二分法例子7Example4_7.javaFilterData.java例子7中的FilterData类的int[]filterArray(int[]arr,int[]filter)方法返回一个数组，该数组的元素值是数组arr经过数组filter过滤后的数据。过滤过程中，使用binarySearch()方法判断数组中哪些值不在filter中，然后通过保留不在filter中值，完成过滤过程。有时候想过滤数组arr，即想去掉数组arr中的某些值。为了过滤数组arr，可以用另外一个数组filer做过滤器，即数组filer中的元素值都是数组arr准备去掉的值。4.4数组的复制2024/11/947数组属于引用型变量，两个类型相同的数组，比如数组a和数组b，如果将a的引用赋值给b，那么二者的元素就完全相同了（见4.1节）。如果想得到一个数组b，b的元素值和a的相同，但二者的引用不同，就需要使用复制的办法，即把数组a的元素值赋值到数组b的元素中，而不是将a的引用赋值给b。2024/11/9484.4数组的复制1.复制数组的方法例子8Example4_8.javaGetRondomNumber.javacopyOf(int[]a,intnewLength)把数组a中从索引0开始的newLength多个元素值赋值到一个新数组中，并返回新数组的引用。如果newLength的值大于数组a的长度，新数组从newLength索引位置开始的元素值都是默认值。比如对于int型数组，默认是就是0。copyOfRange(int[]a,intfrom,intto)把数组a中从索引from开始的到索引位置to结束的元素值（但不包括索引位置是to的元素值）赋值到一个新数组中，并返回新数组的引用。用区间法表示就是把索引范围是半闭半开区间[from,to)的元素值赋值到一个新数组中，并返回新数组的引用。2024/11/9494.4数组的复制1.复制数组的方法例子9Example4_9.javaLeaveOneAround.java围圈留一是一个古老的问题（也称约瑟夫问题）：若干个人围成一圈，从某个人开始顺时针（或逆时针）数到第3个人，该人从圈中退出，然后继续顺时针（或逆时针）数到第3个人，该人从圈中退出，依此类推，程序输出圈中最后剩下的一个人。围圈留1问题可以简化为旋转数组（向左或向右旋转数组），旋转数组2次即可确定出退出圈中的人，即此时数组首元素中的号码就应该是要退出圈中的人。例子9中，LeaveOneAround类的leaveOne(int[]people)方法通过旋转数组确定数组people中出圈的元素，并用copyOfRange()方法保留剩余的元素。2024/11/9504.4数组的复制2.处理重复数据例子9Example4_10.javaHandleRecurring.java有时候需要处理数组中重复的数据，即让重复的数据只保留一个。例子10中，HandleRecurring类的handleRecurring(int[]arr)方法处理数组arr中重复的数据，该方法返回的数组中的数据是arr中去掉重复数据后的数据（重复的数据只保留一个）。4.5数组的比较2024/11/951Arrays类中的静态方法intcompare()和booleanequals()都是重载的方法，用于比较两个数组，二者的区别仅仅是返回值的类型不同。2024/11/9524.5数组的比较例子11Example4_11.javaFindWord.java例子11中，FindWord类的findWord(Stringstr,Stringword)方法输出str中出现的word并返回word出现的次数。例子11的主类Exmple4_11输出一段英文中出现的girl和girl出现的次数4.6公共子数组2024/11/953如果数组a的某个子数组和数组b的某个子数组的长度相同（不要求两个子数组的起始索引相同），所包含的元素值也依次相同，就称二者有公共子数组。2024/11/9544.6公共子数组让长度小的数组，比如b的首单元和数组a的未单元对齐，数组b一直向左移动，直到数组b的尾部a的首单元对齐。向左滑动法那么在左移的过程中，数组a和数组b二者的所有公共子数组一定会出现左对齐的情况。数组a数组b2024/11/9554.6公共子数组例子12Example4_12.javaFindZeroCount.java让长度小的数组，比如b的首单元和数组a的未单元对齐，即b的左端和a的右端对齐，然后进行异或运算，运算结果存放到一个其它数组c中，让数组b按一个单元（元素）为单位向左依次移动（滑动），每移动一个单元，进行异或运算，运算结果存放到数组c中。数组b一直向左移动，直到数组b的尾部，即最后一个单元和数组a的首单元对齐。向左滑动法那么在左移的过程中，数组a和数组b二者的所有公共子数组一定会出现左对齐的情况。由异或运算法则可知，相同的整数异或的结果是0，那么只要根据数组c中连续出现的0的个数，就可以找到一个最大的公共子数组。MaxCommon.java4.7数组的更新2024/11/956Arrays类提供了对数组整体更新的方法：fill()和setAll()。1.整体更新为单值：voidfill(int[]a,intval)该方法将参数数组a的每个元素的而值都设置为参数val指定的值。2.动态更新setAll()方法是一个重载方法，例如：publicstaticvoidsetAll(double[]a,IntToDoubleFunctiongenerator)将参数数组a的每个元素的值都设置为参数generator的计算结果。2024/11/9574.7数组的更新例子13Example4_13.javapublicstaticvoidsetAll(int[]a,IntUnaryOperatorgenerator)IntUnaryOperator是一个函数接口，其中的抽象方法的参数是int型，返回值是int型。可以将一个Lambda表达式传递给generator，该Lambda表达式必须是1个int型参数，Lambda表达式中必须有return语句，返回的值是int型数据。setAll()方法会使用Lambda表达式依次设置数组a的元素的值。例子13中，主类Example4_13使用fill()和setAll()方法整体更新数组的元素的值.4.8数组的前缀算法2024/11/958数组a的前缀算法是：①i初始化0，进行②。②如果i的值满足结束条件，进行③，否则将某个运算结果赋值到数组的第i+1个元素中（通常是a[i]与a[i+1]参与的运算）。i++，执行②。③结束2024/11/9594.8数组的前缀算法例子14Example4_14.javapublicstaticvoidparallelPrefix(int[]a,IntBinaryOperatorop)IntBinaryOperator是一个函数接口，其中的抽象方法的是2个int参数，返回值是int型。可以将一个Lambda表达式传递给op，该Lambda表达式必须是2个int型参数，Lambda表达式中必须有return语句，返回的值是int型数据。例如：IntBinaryOperatorop=(i,j)->{returni+j;};Arrays.parallelPrefix(arr,op);parallelPrefix()在执行过程中，让i取数组的第i个元素的值，j取数组的第i+1个元素的值，将Lambda表达式中return语句的返回值设置为数组第j个元素的值后，然后i再自增，再重复前面的计算。。4.9动态遍历2024/11/960遍历数组的方法（算法）在遍历数组时，让数组的每个元素参与某种运算，并输出运算后的结果，称这样的遍历方法为动态遍历方法。①将数组a的全部元素或部分元素封装到Spliterator.OfInt对象中。②Spliterator.OfInt对象调用voidforEachRemaining(IntConsumerconsumer)方法遍历Spliterator.OfInt对象中封装的数组元素。2024/11/9614.9动态遍历例子15Example4_15.javaforEachRemaining(IntConsumerconsumer)方法遍历Spliterator.OfInt对象中封装的数组元素。该方法的参数intConsumer是一个函数接口，该接口中的抽象方法的参数是int型，返回类型是void型。那么在调用forEachRemaining(IntConsumerconsumer)方法时，可以将一个Lambda表达式传递给consumer，该Lambda表达式必须是1个int型参数，不需要return语句（如果有return，不允许返回任何值）。比如，可以将下列Lambda表达式(value)->{System.out.println(value);}传递给consumer，forEachRemaining(IntConsumerconsumer)方法在执行过程中将使用这个Lambda表达式，让Lambda表达式的参数valule依次取Spliterator.OfInt对象中封装的数组元素1.动