第5章_减治法(完)

1、算法设计与分析算法设计与分析清华大学出版社清华大学出版社第第5章章 减治法减治法 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 2第5章 减治法 5.1 减治法的设计思想 5.2 查找问题中的减治法5.3 排序问题中的减治法5.4 组合问题中的减治法算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 3 规模为规模为n的原问题的解与较小规模（通常是的原问题的解与较小规模（通常是n/2）的子问题的解之间具有关系：的子问题的解之间具有关系：（1）原问题的解）原问题的解只存在于其中一个只存在于其中一

2、个较小规模的子问较小规模的子问题中；题中；（2）原问题的解与其中一个较小规模的解之间存在）原问题的解与其中一个较小规模的解之间存在某种对应关系。某种对应关系。 由于原问题的解与较小规模的子问题的解之间由于原问题的解与较小规模的子问题的解之间存在这种关系，所以，存在这种关系，所以，只需求解其中一个较小规模只需求解其中一个较小规模的子问题就可以得到原问题的解。的子问题就可以得到原问题的解。5.1 5.1 减治法的设计思想减治法的设计思想 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 4 子问题子问题 的规模是的规模是n/2 子问题的解子问题的解

3、 原问题的解原问题的解 原问题原问题 的规模是的规模是n5.1 5.1 减治法的设计思想减治法的设计思想 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 5例：计算例：计算an的值，的值，应用应用减治技术减治技术得到如下计算方法：得到如下计算方法：应用应用分治法分治法得到得到an的计算方法是：的计算方法是： 1122naanaannnO (log2n)O (nlog2n) - -且是奇数且是奇数且是偶数且是偶数1)(1)(122) 1(22naananaannn5.1 5.1 减治法的设计思想减治法的设计思想 算法设计与分析算法设计与分析清华

4、大学出版社清华大学出版社2021-10-30第5章 减治法Page 6111)2/(0)(nnnTnT 所以，通常来说，应用减治法处理问题的效率所以，通常来说，应用减治法处理问题的效率是很高的，是很高的，一般是一般是O( (log2n) )数量级数量级。 减治法只对一个子问题求解，并且不需要进行减治法只对一个子问题求解，并且不需要进行解的合并。解的合并。应用减治法（例如减半法）得到的算法应用减治法（例如减半法）得到的算法通常具有如下递推式：通常具有如下递推式： 5.1 5.1 减治法的设计思想减治法的设计思想 对比分治法：对比分治法： 足够小nnfnTngnT)()2/(2)()(算法设计与分

5、析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 75.1 5.1 减治法的设计思想减治法的设计思想 一个简单的例子一个简单的例子两个序列的中位数两个序列的中位数问题描述：一个长度为问题描述：一个长度为n（n1）的）的升序序列升序序列S，处在，处在第第n/2个个位置位置的数称为序列的数称为序列S的中位数的中位数 。两个序列的中。两个序列的中位数是他们所有元素的升序序列的中位数。现有两个位数是他们所有元素的升序序列的中位数。现有两个等长升序序列等长升序序列A和和B，试设计一个在时间和空间两方面，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列的中

6、位数。都尽可能高效的算法，找出两个序列的中位数。A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，则中位数为，则中位数为13算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 85.1 5.1 减治法的设计思想减治法的设计思想 想法：想法：分别求出两个序列的中位数，记为分别求出两个序列的中位数，记为a和和b；比较；比较a和和b，有下列三种情况：，有下列三种情况： a = b：则：则a即为两个序列的中位数；即为两个序列的中位数； a b：则中位数只能出现在：则中位数只能出现在b和和a之间，在序列之间，在序列A中舍中舍

7、弃弃a之后的元素得到序列之后的元素得到序列A1，在序列，在序列B中舍弃中舍弃b之前的元之前的元素得到序列素得到序列B1；在在A1和和B1中分别求出中位数，重复上述过程，直到两中分别求出中位数，重复上述过程，直到两个序列中只有一个元素，则较小者即为所求。个序列中只有一个元素，则较小者即为所求。算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 95.1 5.1 减治法的设计思想减治法的设计思想 对于两个给定的序列对于两个给定的序列A=11, 13, 15, 17, 19, B=2, 4, 10, 15, 20，求序列，求序列A和和B的中位数的过程。

8、的中位数的过程。步骤步骤操作说明操作说明序列序列A序列序列B1初始序列初始序列11, 13, 15, 17, 192, 4, 10, 15, 202分别求中位数分别求中位数11, 13, 15, 17, 192, 4, 10, 15, 2031510，结果在，结果在10, 15之间之间舍弃舍弃15之后元素，之后元素，11,13,15舍弃舍弃10之前元素，之前元素，10,15,204分别求中位数分别求中位数11,13,1510,15,2051315，结果在，结果在11, 15之间之间舍弃舍弃13之前元素，之前元素，13,15舍弃舍弃15之后元素，之后元素，10,156分别求中位数分别求中位数13

9、,1510,1571013，结果在，结果在10, 13之间之间舍弃舍弃13之后元素，之后元素，13舍弃舍弃10之前元素，之前元素，158长度为长度为1，较小者为所求，较小者为所求1315算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 105.1 5.1 减治法的设计思想减治法的设计思想 1. 循环直到序列循环直到序列A和序列和序列B均只有一个元素均只有一个元素 1.1 a = 序列序列A的中位数；的中位数； 1.2 b = 序列序列B的中位数；的中位数； 1.3 比较比较a和和b，执行下面三种情况之一：，执行下面三种情况之一： 1.3.1 若

10、若a=b，则返回，则返回a，算法结束；，算法结束； 1.3.2 若若ab，则在序列，则在序列A中舍弃中舍弃a之后的元素，之后的元素，在序列在序列B中舍弃中舍弃b之前的元素，转步骤之前的元素，转步骤1； 2. 序列序列A和序列和序列B均只有一个元素，返回较小者；均只有一个元素，返回较小者；算法设计与分析算法设计与分析清华大学出版社清华大学出版社int SearchMid(int A , int B , int n)int s1 = 0, e1 = n - 1, s2 = 0, e2 = n-1; /初始化两个序列的上下界初始化两个序列的上下界int mid1, mid2;while (s1 e1

11、 & s2 e2) /循环直到区间只有一个元素循环直到区间只有一个元素mid1= (s1 + e1)/2; /序列序列A的中位数的下标的中位数的下标mid2 = (s2 + e2)/2; /序列序列B的中位数的下标的中位数的下标if (Amid1 = Bmid2) return Amid1; /第种情况第种情况if (Amid1 Bmid2) /第种情况第种情况if (s1 + e1) % 2 = 0) s1 = mid1;else s1 = mid1 + 1;e2 = mid2;算法设计与分析算法设计与分析清华大学出版社清华大学出版社elseif (s2 + e2) % 2 = 0)

12、 s2 = mid2;elses2 = mid2 + 1;e1 = mid1;if (As1 Bs2) return As1; /较小者为所求较小者为所求else return Bs2;算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 135.2.1 折半查找折半查找 5.2.2 二叉查找树二叉查找树5.2.3 选择问题选择问题5.2 5.2 查找问题中的减治法查找问题中的减治法 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 14q基本思想：在基本思想：在有序表有序表中，中，取中间记录作为比

13、较对象，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。功，或所查找的区域无记录，查找失败。 r1 rmid- -1 rmid rmid+1 rn （mid=( (1+n) )/2）如果如果krmid查找

14、这里查找这里 k5.2.1 5.2.1 折半查找折半查找 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 15例：查找值为例：查找值为14的记录的过程：的记录的过程： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 14 18 21 23 29 31 35 38 42 46 49 52low=1high=13mid=7 high=6 mid=3 high=2 mid=1 31141814714low=2mid=2 14=14查找成功！查找成功！算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5

15、章 减治法Page 16算法算法5.1折半查找折半查找 1. low=1；high=n； /设置初始查找区间设置初始查找区间 2. 测试查找区间测试查找区间low，high是否存在，是否存在， 若不存在，则查找失败；若不存在，则查找失败； 否则否则 3. 取中间点取中间点mid=( (low+high) )/2; 比较比较k与与rmid，有以下三种情，有以下三种情况：况： 3.1 若若krmid，则，则low=mid+1；查找在右半区进行，转；查找在右半区进行，转2； 3.3 若若k=rmid，则查找成功，返回记录在表中位置，则查找成功，返回记录在表中位置mid；算法设计与分析算法设计与分析清

16、华大学出版社清华大学出版社2021-10-30第5章 减治法Page 17判定树判定树描述折半查找的判定过程。描述折半查找的判定过程。长度为长度为n的判定树的构造方法为：的判定树的构造方法为： （1）当）当n=0时，判定树为空；时，判定树为空；（2）当）当n0时，判定树的根结点是有序表中序号时，判定树的根结点是有序表中序号为为mid=(n+1)/2的记录，根结点的左子树是与有序的记录，根结点的左子树是与有序表表r1 rmid-1相对应的判定树，根结点的右子相对应的判定树，根结点的右子树是与树是与rmid+1 rn相对应的判定树。相对应的判定树。算法设计与分析算法设计与分析清华大学出版社清华大学

17、出版社2021-10-30第5章 减治法Page 18具有具有11个结点的判定树个结点的判定树6312548111079 在表中查找任一记录的过程，即是判定树中从根结点到在表中查找任一记录的过程，即是判定树中从根结点到该记录结点的路径，该记录结点的路径，和给定值的比较次数等于该记录结点在和给定值的比较次数等于该记录结点在树中的层数树中的层数。具有。具有n个结点的判定树的深度为个结点的判定树的深度为 ，所以，查找成功时进行的比较次数最多为所以，查找成功时进行的比较次数最多为1log2n1log2n算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page

18、19以深度为以深度为k的的满二叉树满二叉树（n=2k-1）为例，假设表中）为例，假设表中每个记录的查找概率相等，即每个记录的查找概率相等，即pi=1/n，而树的第，而树的第i层层上有上有2i-1个结点，则折半查找的平均查找长度为：个结点，则折半查找的平均查找长度为：所以，折半查找的时间复杂度为：所以，折半查找的时间复杂度为：O(log2n)算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 20q二叉查找树二叉查找树，又称，又称二叉排序树二叉排序树，是具有下列性质的，是具有下列性质的二叉树：二叉树：（1）若它的左子树不空，则左子树上所有结点的值）

19、若它的左子树不空，则左子树上所有结点的值均小于根结点的值；均小于根结点的值；（2）若它的右子树不空，则右子树上所有结点的值）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；均大于根结点的值；（3）它的左右子树也都是二叉排序树。）它的左右子树也都是二叉排序树。5.2.2 5.2.2 二叉查找树二叉查找树 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 21(a) 按按63,90,55,58,70,42,10,45,83,67 (b) 按按55,42,10,70,63,58,83,67,90,45 的顺序构造的二叉排序树的顺序构造的二叉

20、排序树 的顺序构造的二叉排序树的顺序构造的二叉排序树5842709063455583671010836370554542675890算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 22 由二叉排序树的定义，在二叉排序树由二叉排序树的定义，在二叉排序树root中查找给定中查找给定值值k的过程是：的过程是： 若若root是空树，则查找失败；是空树，则查找失败； 若若k根结点的值，则查找成功；根结点的值，则查找成功； 否则，若否则，若k根结点的值，则在根结点的值，则在root的左子树上查找；的左子树上查找； 否则，在否则，在root的右子树上查找；

21、的右子树上查找； 上述过程一直持续到上述过程一直持续到k被找到或者待查找的子树为空，被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。如果待查找的子树为空，则查找失败。v二叉排序树的查找效率就在于只需要查找两个子树之一。二叉排序树的查找效率就在于只需要查找两个子树之一。 5.2.2 5.2.2 二叉查找树二叉查找树 算法设计与分析算法设计与分析清华大学出版社清华大学出版社在二叉查找树中查找关键字值为在二叉查找树中查找关键字值为35，95的过程：的过程：5030208090858840353250302080908588403532二叉查找树查找二叉查找树查找实例实例简述查找过程？简

22、述查找过程？算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 24二叉排序树的结点结构为：二叉排序树的结点结构为：struct BiNode int data; /结点的值，假设查找集合的元素为整型结点的值，假设查找集合的元素为整型 BiNode *lchild, *rchild; /指向左、右子树的指针指向左、右子树的指针;算法算法5.2二叉排序树的查找二叉排序树的查找 BiNode * SearchBST(BiNode *root, int k) if (root= =NULL) return NULL； else if (root-dat

23、a=k) return root; else if (kdata) return SearchBST(root-lchild, k); else return SearchBST(root-rchild, k); 算法设计与分析算法设计与分析清华大学出版社清华大学出版社BiNode *insertBST(BiNode *root, int data)if(root = NULL)root = new BiNode;root-data = data;root-lchild = NULL;root-rchild = NULL;return root;if(data data)root-lchild

24、 = insertBST(root-lchild, data);elseroot-rchild = insertBST(root-rchild, data);return root;BiNode *createBST(int a, int n)BiNode *T = NULL;for (int i=0; i n; i+)T = insertBST(T, ai);return T;建立一棵二叉查找树建立一棵二叉查找树算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 26 在二叉排序树上查找关键码等于给定值的结点的过程，在二叉排序树上查找关键码等于

25、给定值的结点的过程，恰好走了一条从根结点到该结点的路径，恰好走了一条从根结点到该结点的路径，和给定值的比较和给定值的比较次数等于给定值的结点在二叉排序树中的层数次数等于给定值的结点在二叉排序树中的层数，比较次数，比较次数最少为最少为1次（即整个二叉排序树的根结点就是待查结点），次（即整个二叉排序树的根结点就是待查结点），最多不超过树的深度。最多不超过树的深度。具有具有n个结点的二叉树的深度至少个结点的二叉树的深度至少是是 ，至多是，至多是n，所以，二叉排序树的查找性能所以，二叉排序树的查找性能在在O( (log2n) )和和O( (n) )之间。之间。 1log2n算法设计与分析算法设计与分析

26、清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 27设无序序列设无序序列 T =(r1, r2, , rn)，T 的第的第k（1kn）小）小元素定义为元素定义为T按升序排列后在第按升序排列后在第k个位置上的元素。个位置上的元素。给定一个序列给定一个序列T和一个整数和一个整数k，寻找，寻找 T 的第的第k小元素小元素的问题称为的问题称为选择问题选择问题。特别地，将寻找第。特别地，将寻找第n/2小元素小元素的问题称为的问题称为中值问题中值问题。 5.2.3 5.2.3 选择问题选择问题算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法

27、Page 28（1）若）若k=s，则，则rs就是第就是第k小元素；小元素；（2）若）若ks，则第，则第k小元素一定在序列小元素一定在序列rs+1 rj中；中； ri rk rs- -1 rs rs+1 rj 均均rs 轴值轴值 均均rs ri rs- -1 rs rs+1 rk rj 均均rs 轴值轴值 均均rs(a) 若若ks，则，则rk在右半区在右半区 考虑快速排序中的划分过程，一般情况下，设待划分考虑快速排序中的划分过程，一般情况下，设待划分的序列为的序列为ri rj，选定一个轴值将序列，选定一个轴值将序列ri rj进行划分，使进行划分，使得比轴值小的元素都位于轴值的左侧，比轴值大的元素

28、都得比轴值小的元素都位于轴值的左侧，比轴值大的元素都位于轴值的右侧，假定轴值的最终位于轴值的右侧，假定轴值的最终位置位置是是s，则：，则： 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 29选择问题的例子选择问题的例子: : 50 30 80 10 40 60 90 20 70 选择问题的查找过程示例（选择问题的查找过程示例（查找第查找第4小元素）小元素）以以50为轴值划分序列为轴值划分序列42，只在右侧查找，只在右侧查找以以40为轴值划分序列为轴值划分序列44，轴值即为第，轴值即为第4小元素小元素20 30 40 10 50 60 90

29、80 7020 30 40 10 10 20 40 30 40 30 30 40 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 30算法算法选择问题选择问题 1. i=1; j=n; /设置初始查找区间设置初始查找区间 2. 以以ri为轴值对序列为轴值对序列rirj进行一次划分，得到轴值的进行一次划分，得到轴值的位置位置s; 3. 将轴值位置将轴值位置s与与k比较比较 3.1 如果如果k=s，则将，则将rs作为结果返回；作为结果返回； 3.2 否则，如果否则，如果ks，则，则j=s-1，转步骤，转步骤2； 3.3 否则，否则，i=s+1，转

30、步骤，转步骤2；算法设计与分析算法设计与分析清华大学出版社清华大学出版社int Partition(int r , int low, int high) /划分划分int i = low, j=high; /初始化待划分区间初始化待划分区间while (i j) while (i j & ri = rj) j-; /右侧扫描右侧扫描if (i j) int temp = ri; ri = rj; rj = temp; /将较小记录交换到前面将较小记录交换到前面i+; while (i j & ri = rj) i+; /左侧扫描左侧扫描if (i k)return MinK(r

31、, low, s-1, k);elsereturn MinK(r, s+1, high, k); 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 33最好情况最好情况：每次划分的轴值恰好是序列的中值，则可以保每次划分的轴值恰好是序列的中值，则可以保证处理的区间比上一次减半，由于在一次划分后，只需处证处理的区间比上一次减半，由于在一次划分后，只需处理一个子序列，所以，比较次数的递推式是：理一个子序列，所以，比较次数的递推式是： )()()2()(nOnOnTnT最坏情况最坏情况：每次划分的轴值恰好是序列中的最大值或最每次划分的轴值恰好是序列中的

32、最大值或最小值，则处理区间只能比上一次减少小值，则处理区间只能比上一次减少1个，所以，比较次个，所以，比较次数的递推式是：数的递推式是：平均情况平均情况：假设每次划分的轴值是划分序列中的一个随机：假设每次划分的轴值是划分序列中的一个随机位置的元素，则处理区间按照一种随机的方式减少，可以位置的元素，则处理区间按照一种随机的方式减少，可以证明，算法的平均时间是证明，算法的平均时间是O(n) 。 )2()() 1()(nOnOnTnT-算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 345.3.1 堆排序堆排序 5.3.2 插入排序插入排序5.3

33、5.3 排序问题中的减治法排序问题中的减治法 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 35q堆的定义堆的定义堆是一棵堆是一棵完全完全二叉树，任一结点关键字小于等于二叉树，任一结点关键字小于等于（或大于等于）（或大于等于）其孩子结点其孩子结点的关键字。的关键字。n个关键字序列个关键字序列K1,K2,Kn称为堆，当且仅当该序称为堆，当且仅当该序列满足：列满足：KiK2i且且KiK2i+1 (1i n/2 )或者或者KiK2i且且KiK2i+1 (1i n/2 )小根堆小根堆 大根堆大根堆 5.3.1 5.3.1 堆排序堆排序 算法设计与分

34、析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 36小根堆 816 9 1 6 2 1110 5 4大根堆16 9 810 6 2 11 1 5 4 1 6 811 916 2 10 4 5 1 9 810 616 2 11 5 4不是堆不是堆算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 37堆和序列的关系堆和序列的关系将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。5038454028363220182850 38 45 32 36 40 28 20 18 2

35、81 2 3 4 5 6 7 8 9 10采用顺序存储采用顺序存储思考：树中的结点与数组下标有什思考：树中的结点与数组下标有什么关系？么关系？若父结点下标为若父结点下标为i，则左孩子，则左孩子为为2i，右孩子为，右孩子为2i+1；若某结点下标为若某结点下标为i，则其父亲，则其父亲下标为下标为 i/2 。算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 38 以结点的编号作为下标，将堆用顺序存储结构（即数组）以结点的编号作为下标，将堆用顺序存储结构（即数组）来存储，则堆对应于一组序列。来存储，则堆对应于一组序列。 (a) 大根堆及其对应的序列大根

36、堆及其对应的序列(b) 小根堆及其对应的序列小根堆及其对应的序列47 35 26 20 18 7 13 107 10 13 18 35 26 47 204735261318207102610134735187205.3.1 5.3.1 堆排序堆排序 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 39 堆排序的基本思想是：首先将待排序的记录序列构造成堆排序的基本思想是：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，一个堆，此时，选出了堆中所有记录的最大者即堆顶记录，然后将它从堆中移走（通常将堆顶记录和堆中最后

37、一个记录然后将它从堆中移走（通常将堆顶记录和堆中最后一个记录交换），并将剩余的记录再调整成堆，这样又找出了次大的交换），并将剩余的记录再调整成堆，这样又找出了次大的记录，以此类推，直到堆中只有一个记录为止。记录，以此类推，直到堆中只有一个记录为止。 r1 r2 ri ri+1 rn- -1 rn 无序区无序区 有序区有序区 为一个堆为一个堆 已经位于最终位置已经位于最终位置 堆顶和堆中最后堆顶和堆中最后一个记录交换一个记录交换5.3.1 5.3.1 堆排序堆排序 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 40为保证时间性能，就要为保证时

38、间性能，就要利用已有结果利用已有结果，每次输出堆顶后，剩，每次输出堆顶后，剩下元素不是完全重建，应该在原堆上通过某些调整得到；下元素不是完全重建，应该在原堆上通过某些调整得到；为保证空间性能，为保证空间性能，输出的堆顶应利用原有空间，可将它与无输出的堆顶应利用原有空间，可将它与无序区最后记录交换位置。序区最后记录交换位置。排序过程中有序区在原记录区的尾部排序过程中有序区在原记录区的尾部逐步形成并向前扩大，和直接选择排序相反。逐步形成并向前扩大，和直接选择排序相反。两个问题：两个问题：（1）最初如何由一个无序序列建成一个堆？）最初如何由一个无序序列建成一个堆？（2）在输出堆顶元素后，如何调整剩余

39、元素成为一个新的堆？）在输出堆顶元素后，如何调整剩余元素成为一个新的堆？ 算法设计与分析算法设计与分析清华大学出版社清华大学出版社1 1、初始堆的建立、初始堆的建立2021-10-30第5章 减治法Page 41q把完全二叉树中以每一结点为根的子树都调整为堆。把完全二叉树中以每一结点为根的子树都调整为堆。q只有一个结点的树是堆，在完全二叉树中，所有序号只有一个结点的树是堆，在完全二叉树中，所有序号i n/2 的结点都是叶子，以这些结点为根的子树均已是堆。的结点都是叶子，以这些结点为根的子树均已是堆。q依次将以序号为依次将以序号为 n/2 ， n/2 1,1的结点作为根的子树都调的结点作为根的子

40、树都调整为堆。整为堆。q按该次序调整各结点时，其左、右子树均已是堆。按该次序调整各结点时，其左、右子树均已是堆。算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 421981061621145n=10，故从第，故从第 10/2 5个结点开始进行调整个结点开始进行调整 198106162115419810611216541981061121654算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 4319810611162541981062161154169810621115416981062111

41、541698162111054算法设计与分析算法设计与分析清华大学出版社清华大学出版社2 2、调整和重建、调整和重建2021-10-30第5章 减治法Page 44算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 45堆调整堆调整筛选法筛选法 关键问题：完全二叉树中，根结点的左右子树均是堆，关键问题：完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？如何调整根结点，使整个完全二叉树成为一个堆？ (a) 28与与35交换交换(b) 28与与32交换交换(c) 将将28筛到叶子筛到叶子2832182012182012

42、353218201235352832285.3.1 5.3.1 堆排序堆排序 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 46qRi左、右子树是堆，子树的根为各自子树中关键字最大者，左、右子树是堆，子树的根为各自子树中关键字最大者，q将将Ri和其左、右孩子中关键字最大者放到和其左、右孩子中关键字最大者放到Ri的位置。的位置。若若Ri是三者中的最大，则无需调整，以其为根的子树已是是三者中的最大，则无需调整，以其为根的子树已是堆；堆；否则，将否则，将Ri和具有最大关键字的左孩子和具有最大关键字的左孩子R2i或右孩子或右孩子R2i+1进行交换。

43、进行交换。q交换后以交换后以R2i和和R2i+1为根的子树可能不再是堆，但其左、为根的子树可能不再是堆，但其左、右子树仍然是堆，于是重复上述过程，右子树仍然是堆，于是重复上述过程，将子树调整为堆将子树调整为堆，如此逐层递推下去，最多可能一直调整到树叶。如此逐层递推下去，最多可能一直调整到树叶。q这一过程就像过筛子一样，把较小的关键字筛下去，而将最大这一过程就像过筛子一样，把较小的关键字筛下去，而将最大关键字一层层地选择上来。关键字一层层地选择上来。 堆调整堆调整筛选法筛选法算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 47198106216

44、1154大根堆169810621115416981062111541698162111054算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 48 假设当前要筛选结点的编号为假设当前要筛选结点的编号为k，堆中最后一个结点的，堆中最后一个结点的编号为编号为n，并且结点，并且结点k的左右子树均是堆（即的左右子树均是堆（即rk+1 rn满满足堆的条件），则筛选算法用伪代码可描述为：足堆的条件），则筛选算法用伪代码可描述为： 算法算法5.3筛选法调整堆筛选法调整堆 1. 设置设置i和和j，分别指向当前要筛选的结点和要筛选结点的左孩子；，分别指向当前要筛

45、选的结点和要筛选结点的左孩子； 2. 若结点若结点i已是叶子，则筛选完毕；否则，比较要筛选结点的左右已是叶子，则筛选完毕；否则，比较要筛选结点的左右 孩子结点，并将孩子结点，并将j指向关键码较大的结点；指向关键码较大的结点； 3. 将要筛选结点将要筛选结点i的关键码与结点的关键码与结点j的关键码进行比较，有以下两种的关键码进行比较，有以下两种情况：情况： 3.1 如果结点如果结点i的关键码大，则完全二叉树已经是堆；的关键码大，则完全二叉树已经是堆； 3.2 否则将否则将ri与与rj交换；令交换；令i=j，转步骤，转步骤2继续进行筛选；继续进行筛选；时间性能是时间性能是O(log2n)。 算法设

46、计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 49算法算法5.4筛选法调整堆筛选法调整堆 void SiftHeap( (int r , int k, int n) ) i=k; j=2*i; /置置i为要筛的结点，为要筛的结点，j为为i的左孩子的左孩子 while ( (j=n) ) /筛选还没有进行到叶子筛选还没有进行到叶子 if ( (jn & rjrj) ) /根结点已经大于左右孩子中的较大者根结点已经大于左右孩子中的较大者 break; else rirj; /将根结点与结点将根结点与结点j交换交换 i=j; j=2*i; /被

47、筛结点位于原来结点被筛结点位于原来结点j的位置的位置 算法设计与分析算法设计与分析清华大学出版社清华大学出版社void HeapSort(int r , int n) int i, temp;for (i = (n-1)/2; i = 0; i-) /初始建堆，从最后一个分支结点至根初始建堆，从最后一个分支结点至根结点结点SiftHeap(r, i, n) ; for (i = 1; i = n-1; i+) /重复执行移走堆顶及重建堆的操作重复执行移走堆顶及重建堆的操作temp = r0; r0 = rn-i; rn-i = temp;SiftHeap(r, 0, n-i); /只需调整根结

48、点只需调整根结点算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 5116169 98 81 16 62 2111110105 54 4交换交换筛选筛选交换交换筛选筛选4 49 98 81 16 62 2111110105 5161611119 98 81 16 62 210104 45 516162 29 98 81 16 6111110104 45 51616经过跟刚才一样的步骤经过跟刚才一样的步骤堆排序堆排序算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 52交换交换筛选筛选交换交换筛选

49、筛选10109 98 81 16 611115 54 42 216161 19 98 810106 611115 54 42 216169 98 81 110106 611115 54 42 216161 18 89 910106 611115 54 42 21616算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 53交换交换筛选筛选交换交换筛选筛选8 86 69 910101 111115 54 42 216161 16 69 910108 811115 54 42 216166 61 19 910108 811115 54 42 2161

50、62 21 19 910108 811115 54 46 61616算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 54交换交换筛选筛选交换交换筛选筛选5 51 19 910108 811114 42 26 616162 21 19 910108 811114 45 56 616164 41 19 910108 811112 25 56 616161 14 49 910108 811112 25 56 61616算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 55交换交换2 24 49 91

51、0108 811111 15 56 616161 14 49 910108 811112 25 56 61616算法设计与分析算法设计与分析清华大学出版社清华大学出版社堆排序小结堆排序小结（1）建堆）建堆/堆调整方法：堆调整方法：筛选法：将结点与其孩子结点比较。筛选法：将结点与其孩子结点比较。（2）堆排序方法：）堆排序方法：先建堆；先建堆；取出堆顶；取出堆顶；剩下元素再调整为堆；剩下元素再调整为堆；直至剩下一个元素为止。直至剩下一个元素为止。2021-10-30第5章 减治法Page 56算法设计与分析算法设计与分析清华大学出版社清华大学出版社5.3.2 插入排序插入排序 插入排序属于减治法的

52、减一技术插入排序属于减治法的减一技术2021-10-30第5章 减治法Page 57每次将无序区第每次将无序区第1条记录插入到有序区适当位置。初条记录插入到有序区适当位置。初始取第始取第1条记录为有序区，其它记录为无序区。随着条记录为有序区，其它记录为无序区。随着排序进行，有序区不断扩大，无序区不断缩小。最终排序进行，有序区不断扩大，无序区不断缩小。最终无序区为空，有序区包含了全部记录，排序结束。无序区为空，有序区包含了全部记录，排序结束。 有序区也可从排序表的尾部生成有序区也可从排序表的尾部生成 。算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Pa

53、ge 58在插入第在插入第 i（i1）个记录时，前面的）个记录时，前面的 i-1个记录已经个记录已经排好序。排好序。 有序序列有序序列无序序列无序序列r1r2ri-1rirnri+1r1r2ri-1rirnri+1（1）如何构造初始的有序序列？）如何构造初始的有序序列？（2）如何查找待插入记录的插入位置）如何查找待插入记录的插入位置?需解决的关键问题需解决的关键问题?算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 59 初始：（初始：（49）38 13 76 27 49 （38 49）13 76 27 49 （13 38 49）76 27 4

54、9 （13 38 49 76）27 49 （13 27 38 49 76 ）49 （13 27 38 49 49 76 ）算法设计与分析算法设计与分析清华大学出版社清华大学出版社插入排序过程示例插入排序过程示例 2021-10-30第5章 减治法Page 60r 0 1 2 3 4 5 6211825221025*212125插入排序插入排序i = 218221025*25i = 318221025*2225222110252115102525*2521151025*252118151018181025*i = 418i = 61825*i = 5r0的作用的作用?暂存单元暂存单元监视哨监视哨

55、25算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 61void InsertSort(int r,int n) /设置监视哨设置监视哨for(int i=2;i=n;i+)/进行进行n-1次插入，依次插入次插入，依次插入 /r2,r3,rn r0=ri; /r0是监视哨是监视哨 /顺序比较和移动，查找顺序比较和移动，查找ri的插入位置的插入位置 for(int j=i-1;r0rj;j-) rj+1=rj; /记录后移，继续向前搜索记录后移，继续向前搜索 rj+1=r0; /插入插入Ri r0为为监视哨监视哨（Sentinel），省略下标越

56、界检查），省略下标越界检查“j1”：一旦越：一旦越界，界，j=01，循环条件，循环条件r01) i=i/2; for (j=0; ji; j+) if (Comp(rj+i, rj) rj=rj+i; return r0; 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 66 因为因为n=2k，所以，外层的，所以，外层的while循环共执行循环共执行k次，次，在每一次执行时，内层的在每一次执行时，内层的for循环的执行次数分别循环的执行次数分别是是n/2，n/4，1，而函数，而函数comp可以在常数时间可以在常数时间内完成，因此，算法内完成，

57、因此，算法5.8的执行时间为：的执行时间为：)(1)211 (2)(1nOnnnnTkkii-算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 67 在在n枚外观相同的硬币中，枚外观相同的硬币中，有一枚是假币有一枚是假币，并，并且已知且已知假币较轻假币较轻。可以通过一架。可以通过一架没有刻度的没有刻度的天平来天平来任意比较两组硬币，从而得知两组硬币的重量是否任意比较两组硬币，从而得知两组硬币的重量是否相同，或者哪一组更轻一些，但不知道轻多少，假相同，或者哪一组更轻一些，但不知道轻多少，假币问题是要求设计一个高效的算法来检测出这枚假币问题是要求设

58、计一个高效的算法来检测出这枚假币。币。 5.4.2 5.4.2 假币问题假币问题 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 68 问题的解决是经过一系列比较和判断，可以用问题的解决是经过一系列比较和判断，可以用判定判定树树来描述这个判定过程。来描述这个判定过程。 解决这个问题的最自然的想法就是一分为二，也就解决这个问题的最自然的想法就是一分为二，也就是把硬币分成两组。把是把硬币分成两组。把n枚硬币分成两组，每组有枚硬币分成两组，每组有枚硬币，如果枚硬币，如果n为奇数，就留下一枚硬币，然后把两组为奇数，就留下一枚硬币，然后把两组硬币分别放

59、到天平的两端。如果两组硬币的重量相同，硬币分别放到天平的两端。如果两组硬币的重量相同，那么留下的硬币就是假币；否则，用同样的方法对较轻那么留下的硬币就是假币；否则，用同样的方法对较轻的那组硬币进行同样的处理，假币一定在较轻的那组里。的那组硬币进行同样的处理，假币一定在较轻的那组里。2n算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 69 在假币问题中，每次用天平比较后，只需解在假币问题中，每次用天平比较后，只需解决一个决一个规模减半规模减半的问题，所以，它属于一个的问题，所以，它属于一个减治减治算法。该算法在最坏情况下的时间性能有这样一算法。

60、该算法在最坏情况下的时间性能有这样一个递推式：个递推式： 11)2(10)(nnTnnT 应用扩展递归技术求解这个递推式，得到应用扩展递归技术求解这个递推式，得到T( (n)=)=O( (log2n) )。 算法设计与分析算法设计与分析清华大学出版社清华大学出版社2021-10-30第5章 减治法Page 70 考虑不是把硬币分成两组，而是分成三组，考虑不是把硬币分成两组，而是分成三组，前两组有前两组有 组硬币，其余的硬币作为第三组，组硬币，其余的硬币作为第三组，将前两组硬币放到天平上，如果他们的重量相同，将前两组硬币放到天平上，如果他们的重量相同，则假币一定在第三组中，用同样的方法对第三组则假币一定在第三组中，用同样的方