数据结构ppt 2016ppt 第5章

1、第5章 递归,5.1 递归基础 5.2 递归与分治 5.3 递归与迭代 5.4 广义表,1,引言,从认知事物的角度看，递归是一种定义方式，它与一般定义方式的不同之处在于“使用被定义对象的自身来为其下定义”。 在定义中使用自身进行递归描述的数据结构称为递归数据结构。 后面章节将介绍的二叉树和树等是典型的递归数据结构。对递归数据结构的常用操作都可以采用递归算法实现。,2,引言,从程序设计的角度看，递归是一种程序设计方法。 函数直接或间接地调用自身，称为递归调用。含有递归调用的函数称为递归函数。 递归调用是用相同的策略去解决规模更小的问题，直至问题规模小于或等于某个边界条件时，不再进行递归调用，而是

2、直接处理。,3,5.1 递归基础：汉诺塔问题描述,汉诺塔问题是一个源于印度古老传说的游戏： 有3根柱子A、B和C，还有一组数量为n、大小不一的圆盘。 开始时，所有圆盘从大到小叠放在A柱上。游戏的任务是将所有圆盘从A移到C，其中B柱可以作为临时的中转柱使用。游戏规则： （1）在任何时刻都不允许大盘子在小盘子之上。 （2）每次只能移动一个盘子。,4,汉诺塔示例：n = 3,A,C,B,5,汉诺塔示例：n = 3,A,C,B,6,汉诺塔程序,void hanoi(int n, char x, char y, char z) / 盘子个数 源柱 中转柱 目标柱 if(1 = n) move(x,1,z

3、); else hanoi(n1,x,z,y); move(x,n,z); hanoi(n1,y,x,z); ,x,z,y,/ 以y为中转柱，将n个盘从源柱x移到目标柱z,x,z,y,7,函数调用过程解析,void hanoi(int n, char x, char y, char z) if(1 = n) move(x,1,z); else hanoi(n1,x,z,y); move(x,n,z); hanoi(n1,y,x,z); void main( ) /第i-2行 hanio(3, A, B, C);/第i行 /第i+1行 ,首先观察一般的函数调用过程： 当函数M调用函数F时，系统会

4、暂停执行M，转去执行F 。 当F执行结束，则返回M继续执行，继续执行的程序地址称为返回地址，这里恰好在第i+1行。,函数调用的一般过程,当函数M调用函数F，在执行F之前，系统需要完成以下工作： （1）将实参、返回地址RA（Return address）等信息传给F。 （2）为F中的局部变量分配存储空间。 （3）转到F的第一条将要被执行的代码（入口代码）处，准备开始执行。,返址,实参/局部变量,发生函数调用时，会在工作栈栈顶开辟一段称为栈帧的存储空间，用于保存实参、局部变量和返回地址等。,函数调用的一般过程,当函数F执行完毕，在返回M之前，系统需要进行以下工作： （1）保存F的计算结果（如果有）

5、。 （2）释放F栈帧占用的空间，包括实参和局部变量占用的空间等。 （3）转到返回地址RA继续执行。,返址,实参/局部变量,当hanio栈帧出栈，则main栈帧处于栈顶，将继续main函数的第i+1行代码。,函数递归调用的嵌套层数称为递归层次。 规定：最开始时其它函数对递归函数的调用称为第0层调用。,递归函数调用,void hanoi(int n, char x, char y, char z) if(1 = n) move(x,1,z); else 4 hanoi(n1,x,z,y); 5 move(x,n,z); hanoi(n1,y,x,z); void main( ) /第i-1行 ha

6、nio(3, A, B, C); /第i+1行 ,i+1,第0层调用,第1层调用,hanio栈帧,5,Hanoi(3, A, B, C)执行过程,void hanoi(int n, char x, char y, char z ) 1 if(1 = n) 2 move(x,1,z); 3 else /实参： 4 hanoi(n1,x,z,y); 5 move(x,n,z); 6 hanoi(n1,y,x,z); 7 8,A,C,B,第0层调用,void hanoi(int n, char x, char y, char z ) 1 if(1 = n) 2 move(x,1,z); 3 else

7、 /实参： 4 hanoi(n1,x,z,y); /实参： 5 move( x,n,z); 6 hanoi(n1,y,x,z); 7 8,第1层调用,3,2,A,C,B,A,B,C,2,1,1,A,A,C,C,B,B,ri 3, A, B, C,r0 2, A, C, B,2,A,B,A,B,2,第1层hanoi,第0层hanoi,第2层hanoi, ,main栈帧,12,Hanoi(3, A, B, C)执行过程,void hanoi(int n, char x, char y, char z ) 1 if(1 = n) 2 move(x,1,z); 3 else /实参： 4 hanoi(

8、n1,x,z,y); 5 move(x,n,z); 6 hanoi(n1,y,x,z); 7 8,A,C,B,第0层调用,void hanoi(int n, char x, char y, char z ) 1 if(1 = n) 2 move(x,1,z); 3 else /实参： 4 hanoi(n1,x,z,y); /实参： 5 move( x,n,z); 6 hanoi(n1,y,x,z); 7 8,第1层调用,3,2,A,C,B,A,B,C,2,1,1,A,A,C,C,B,B,返址,实参,ri 3, A, B, C,r0 2, A, C, B,2,A,B,A,B,2,第1层栈帧,第0

9、层栈帧,第2层栈帧,13,5.2 递归与分治：分治法,具有以下特征的问题可应用分治法求解： （1）当问题规模小于一定程度时，可以直接求解； （2）当问题规模较大时，可以分解为若干个相互独立的子问题，这些子问题与原问题具有相同特征。若不能直接求解，则可分别递归求解。 （3）原问题的解是子问题解的组合，其组合方式由实际问题决定。,14,5.2 递归与分治：分治法,分治法（Divide and Conquer）的基本思想为：把规模为n的输入分割成k (2 k n)个子集，从而产生 l 个子问题（一般情况下l = k），分别求解得到l个子问题的解，并将子解组合成原问题的解。,15,分治法举例：汉诺塔问

10、题,利用分治法求解汉诺塔问题的要点有： （1）需求解的问题：将n个圆盘从源柱移动至目标柱。 （2）输入：规模为n的圆盘。 （3）规模分割：k = 2，其中一个子集规模为1，另一个为n-1。 在一般情况下，子问题的规模大致相等时，递归层次较小，求解效率更高。但由（3）可见，在实际处理中子问题的规模不一定相等。,16,分治法需要注意的问题,采用分治法时，需要注意以下几个方面： （1）规模为n的输入是被处理的对象。将其分割成k个子集后，有些子集可能对应多个子问题，因而最终产生的子问题数l可能会大于k。 例如汉诺塔，1至n-1圆盘这个子集对应2个子问题，分别为“将1至n-1圆盘从源柱移至中转柱”和“将

11、1至n-1圆盘从中转柱移至目标柱”。,17,分治法需要注意的问题（续1）,（2）确定递归边界，即确定当问题规模小到什么程度时，可以直接求解。 在汉诺塔问题中，递归边界是圆盘数量为1，此时只需直接将盘从源柱移到目标柱，而无需递归处理。,18,分治法需要注意的问题（续2）,（3）在问题规模大于递归边界时，由于处理策略是相同的，所以应信任递归调用可以胜任子问题的处理，而无需关注子问题的求解细节。 例如在函数hanoi(n, x, y, z)中，应信任hanoi(n-1, x, z, y)是能够将1至n-1号圆盘从x柱移到y柱的。 （4）要根据实际问题的特点决定解的组合方式。 例如，汉诺塔问题的解的形

12、式是move函数的调用序列。,19,分治法应用1：折半查找算法,折半查找是将顺序表分解为3个查找区间：前后两个区间的规模大致相等，中间区间长度为1。 （1）if (待查记录的关键字k1 = 中间区间记录的关键字k2)，则查找成功。 （2）else if (k1 k2)，说明待查记录只可能在前半区，则在前半区应用相同策略继续查找；,（3） else ，说明待查记录只可能在后半区，则在后半区应用相同策略继续查找；,k2,前,后,20,分治法应用1：折半查找算法（续）,不断缩小前半区或者后半区，并且继续查找的过程符合分治法的特征： （1）区间长度 1时，分解为3个子问题，这些子问题与原问题具有相同特

13、征。 （3）比较特殊的是：折半查找的解要么是其中一个子问题的解，要么无解，所以无需进行子解的组合。,21,折半查找算法举例,查找关键字：21,06,10,79,21,49,51,69,20,82,88,94,0,1,7,3,4,5,6,2,8,9,10,low,high,(low+high) / 2,mid =,前半区,后半区,中间区,22,折半查找算法举例,查找关键字：21,06,10,79,21,49,51,69,20,82,88,94,0,1,7,3,4,5,6,2,8,9,10,low,high,前半区,后半区,中间区,23,折半查找算法举例,查找关键字：21,06,10,79,21,

14、49,51,69,20,82,88,94,0,1,7,3,4,5,6,2,8,9,10,low,high,前半区,后半区,中间区,24,high,折半查找算法举例,int BinSearch(RcdType rcd, KeyType key, int low, int high) / 在有序序列rcdlow.high中折半查找目标关键字key int mid = (low + high) / 2; if(rcdmid.key = key) return mid; /查找成功，返回中间关键字的下标 else if(rcdmid.key key) / 在前半区折半查找 return BinaryS

15、earch(rcd, key, low, mid1); else / 在后半区折半查找 return BinarySearch(rcd, key, mid+1, high); ,low,high,mid,25,折半查找算法举例,查找关键字：85,06,10,79,21,49,51,69,20,82,88,94,0,1,7,3,4,5,6,2,8,9,10,low,high,(low+high) / 2,mid =,前半区,后半区,中间区,26,折半查找算法举例,查找关键字：85,06,10,79,21,49,51,69,20,82,88,94,0,1,7,3,4,5,6,2,8,9,10,lo

16、w,high,前半区,后半区,中间区,27,折半查找算法举例,查找关键字：85,06,10,79,21,49,51,69,20,82,88,94,0,1,7,3,4,5,6,2,8,9,10,high,前半区,后半区,中间区,low,28,int BinSearch(RcdType rcd, KeyType key, int low, int high) / 在有序序列rcdlow.high中折半查找目标关键字key int mid = (low + high) / 2; if(high key) / 在前半区折半查找 return BinarySearch(rcd, key, low, mi

17、d1); else / 在后半区折半查找 return BinarySearch(rcd, key, mid+1, high); ,折半查找算法举例,low,high,mid,29,分治法应用2：归并排序算法,归并：将两个或两个以上的有序表组合成一个新的有序表。 归并排序（Merging sort）：把无序的待排序序列分解成若干个有序子序列，并把有序子序列合并为整体有序序列的过程。 规定长度为1的序列是有序的。所以分解时，要一直分解到子序列长度为1时为止。 2-路归并排序：两两分解和两两合并的归并排序。,30,31,void Merge (RcdType SR, RcdType i=m , ,

18、32,if (i=m) TRk.n = SRi.m; / 将剩余的 SRi.m 复制到 TR,if (j=n) TRk.n = SRj.n; / 将剩余的 SRj.n 复制到 TR,归 并 排 序 算 法 举 例,第一层,86,15,42,30,69,98,86,15,57,分解,归并,第二层,分解,归并,第三层,分解,归并,33,34,先看更容易理解的实现，不考虑 节省存储空间,35,void Msort ( RcdType SR, RcdType else / Msort, ,36,m = (s+t)/2; / 将SRs.t平分为SRs.m和SRm+1.t,Msort (SR, TR2,

19、s, m); / 递归地将SRs.m归并为有序的TR2s.m Msort (SR, TR2, m+1, t); /递归地SRm+1.t归并为有序的TR2m+1.t,Merge (TR2, TR1, s, m, t); / 将TR2s.m和TR2m+1.t归并到TR1s.t,37,void MergeSort (RcdSqList / MergeSort,归并排序算法的实现,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t void MergeSort

20、(RcdSqList ,38,归并排序算法的实现,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t void MergeSort(RcdSqList ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,39,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); /

21、 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t); / 对区间m+1.t递归归并排序,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,R1,0,R2,1,7,L.rcd,R,42,57,69,98,86,15,30,1,40,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t); / 对区间

22、m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,R1,0,R2,1,7,L.rcd,R,30,86,69,98,15,57,42,41,归并排序算法的实现,m = (s+t)

23、/2; MSort(R1, R2, i+1, s, m); MSort(R1, R2, i+1, m+1, t); if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,0,R

24、2,1,7,L.rcd,R,42,57,69,98,86,15,30,3,42,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1,

25、 RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,0,R2,1,7,L.rcd,R,1,1,4,递归层次：0,43,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); /

26、将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,1,R2,1,4,L.rcd,R,1,1,4,2,1,2,递归层次：1,44,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1

27、, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s

28、=t) if(1=i%2) R2s = R1s; else ,R1,2,R2,1,2,L.rcd,R,2,1,2,3,1,1,递归层次：2,45,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.

29、t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,3,R2,1,1,L.rcd,R,3,1,1,1,42,递归层次：3,46,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=

30、i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,2,R2,1,2,L.rcd,R,3,2,2,递归层次：2,47,归并排序算法的实

31、现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若

32、i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,3,R2,2,2,L.rcd,R,30,递归层次：3,3,2,2,48,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2,

33、R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,2,R2,1,2,L.rcd,R,递归层次：2,30,42,49,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t )

34、; / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,1,R2,1,4,L.rcd,R,

35、2,4,3,递归层次：1,69,98,98,69,50,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2,

36、 int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,1,R2,1,4,L.rcd,R,2,4,3,递归层次：1,30,42,69,98,51,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); /

37、将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,0,R2,1,7,L.rcd,R,1,7,5,递归层次：0,86,15,86,15,57,57,15,86,57,52,归并排序算法的实现,m = (s+t)

38、/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记

39、录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,0,R2,1,7,L.rcd,R,1,7,5,递归层次：0,30,86,69,98,15,57,42,53,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序 MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Mer

40、ge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s; else ,R1,0,R2,1,7,L.rcd,R,1,7,4,递归层次：0,86,15,.,86,15,57,57,54,归并排序算法的实现,m = (s+t)/2; MSort(R1, R2, i+1, s, m); / 对区间s.m递归归并排序

41、MSort(R1, R2, i+1, m+1, t ); / 对区间m+1.t递归归并排序 if(1=i%2) / i为奇数 Merge(R1, R2, s, m, t); / 将R1s.m和R1m+1.t归并到R2s.t else / i为偶数 Merge(R2, R1, s, m, t); / 将R2s.m和R2m+1.t归并到R1s.t ,void MSort(RcdType R1, RcdType R2, int i, int s, int t) / 对R1s.t归并排序，若i为奇数，则排序后的记录存入R2s.t，否则R1s.t,if(s=t) if(1=i%2) R2s = R1s;

42、 else ,R1,3,R2,1,1,L.rcd,R,3,1,1,1,42,55,分治法应用3：快速排序算法,快速排序（Quicksort）是对冒泡排序的改进，常简称为快排。基本思想： （1）首先从待排序列中选定一个关键字，称之为枢轴。 （2）将待排序序列划分成位于枢轴前后的两个子序列： a. 枢轴之前的子序列的所有关键字都不大于枢轴； b. 枢轴之后的子序列的所有关键字都不小于枢轴； 此时枢轴已到位，再按同样方法对这两个子序列分别递归进行快速排序，最终使得整个序列有序。,42,57,69,98,86,15,30,1,7,3,4,5,6,2,56,分治法应用3：快速排序算法,一趟冒泡排序与快速

43、排序进行一次划分如下图所示：,57,每趟冒泡排序将无序序列划分为两部分：最大记录和其余记录。 对于快速排序（选定第1个记录为枢轴），经过一次划分之后，序列可划分为三部分：“比枢轴小”和“比枢轴大”的两个子序列，以及已排序到位的枢轴。,int Partition(RcdType rcd , int low, int high) / 对rcdlow.high 作一次划分，并返回枢轴记录应该所处的位置 rcd0 = rcdlow; / 将枢轴移至数组的闲置分量 while(low= rcd0.key) -high; rcdlow = rcdhigh; / 将比枢轴小的记录移到前端 while(low

44、high ,42,57,69,98,86,15,30,1,7,3,4,5,6,2,0,low,high,42,42 57,快速排序算法：一次划分,58,42,69,15,void QSort(RcdType rcd, int s, int t) / 对记录序列 rcds.t 进行快速排序 if(s t) / 长度大于1 / 对rcds.t一趟划分，并返回枢轴位置 int pivotloc = Partition(rcd, s, t); QSort(rcd, s, pivotloc-1); / 对前子序列递归进行排序 QSort(rcd, pivotloc+1, t); / 对后子序列递归进行排

45、序 ,57,98,86,30,s,t,s+1,快速排序算法：实现框架,42,42,69,15,57,98,86,30,42,42,86,15,98,57,69,30,pivotloc,15,98,59,void QSort(RcdType rcd, int s, int t) / 对记录序列 rcds.t 进行快速排序 if(s t) / 长度大于1 / 对rcds.t一趟划分，并返回枢轴位置 int pivotloc = Partition(rcd, s, t); QSort(rcd, s, pivotloc-1); / 对前子序列递归进行排序 QSort(rcd, pivotloc+1,

46、t); / 对后子序列递归进行排序 ,快速排序算法：调用接口,void QuickSort(RcdSqList ,60,5.3 递归与迭代,迭代法是一种反复利用变量的旧值递推出新值，从而完成问题求解的计算方法。 在每次计算中，都至少有一个变量需要使用该变量在上一轮中的旧值结果作为输入。 迭代和递归存在相似之处，在某些情况下甚至可以互相转换。,61,5.3 递归与迭代：迭代三要素,1、确定迭代变量。迭代变量可有多个，并在迭代中可由旧值直接或者间接地推出新值。 在某些问题中，迭代变量是最终的计算结果，例如求自然数阶乘n!问题。 2、建立迭代关系式。迭代关系式是指迭代变量的旧值与新值之间的变化规律。

47、 3、确定迭代结束条件。迭代结束条件通常有两种： 一种是完成了指定的迭代次数。例如在求自然数阶乘n!中，迭代次数为n1； 另一种是无法事前指定迭代次数，结束条件由实际情况确定。,62,折半查找算法的迭代实现,int BinSearch_ite(RcdType rcd, KeyType key, int low, int high) / 在有序序列rcdlow.high中折半查找目标关键字key int mid; while(low key) / 在低半区继续折半查找 high = mid-1; else low = mid+1; / 在高半区继续折半查找 return -1; / 找不到key

48、，返回-1 ,迭代变量,迭代关系式,迭代结束条件： low high,63,2-路归并排序算法的迭代实现,较难，见书本P111-112参考,迭代与递归的联系与区别,如果一个问题可以分解为若干个与初始问题形式相似的子问题，并且分解次数是有限的，则该问题可递归求解。 这类问题只要满足迭代三要素，则也可能用迭代方式求解。 对于同一个问题，其递归和迭代的求解思路不一定完全一致。 例如算法5.4和5.8是2-路归并算法的递归实现和迭代实现，它们的求解思路差别较大，不能简单认为他们是同一种求解思路在实现上的相互转化。,65,迭代与递归的联系与区别,递归的优点是程序的代码简洁，容易编程和理解。 在递归过程中会产生大量函数调用，既耗费较多的程序运行时间，也占用了大量的函数调用栈空间，极端情况下甚至会导致栈溢出。 例如对于折半查找的迭代实现和递归实现，在相同规模的输入下，递归实现求解所需的时间和空间开销都远比迭代要大。 如果递归和迭代求解的时间复杂度相同，可优先考虑采用迭代。,66,5.4 广义表,将线性表