《第12章_缩小规模算法.ppt》由会员分享，可在线阅读，更多相关《第12章_缩小规模算法.ppt（24页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、电子工程学院电子工程学院电子工程学院电子工程学院第第12章章 缩小规模算法缩小规模算法12/31/20221电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录第第12章章 缩小规模算法缩小规模算法1.1.二分搜索技术二分搜索技术2.2.归并排序归并排序3.3.快速排序快速排序4.4.习题习题12/31/20222电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录二分搜索技术（二分查找、折半查找）二分搜索技术（二分查找、折半查找）n要求线性表是顺序存储结构的有序表。要求线性表是顺序存储结构的有序表。nn n个记录个记录R0R0Rn-1Rn-1按关键字按关键字k
2、eykey递增递增有序有序,在在n n个记录中找出关键字的值为个记录中找出关键字的值为x x的的记录。记录。12/31/20223电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n算法的基本思想：算法的基本思想：算法的基本思想：算法的基本思想：（1 1）先求位于查找区间正中的记录的下标）先求位于查找区间正中的记录的下标）先求位于查找区间正中的记录的下标）先求位于查找区间正中的记录的下标midmid：mid=(low+high)/2mid=(low+high)/2 （2 2）用其关键字与给定值用其关键字与给定值用其关键字与给定值用其关键字与给定值x x x x比较比较比较比较
3、:vv 如果如果如果如果 x=x=Rmid.keyRmid.key，则查找成功，返回，则查找成功，返回，则查找成功，返回，则查找成功，返回midmid值值值值vv 如如如如果果果果 x x Rmid.keyRmid.key，则则则则在在在在右右右右区区区区间间间间继继继继续续续续查查查查找找找找，置置置置low=mid+1low=mid+1 (3)(3)重重重重复复复复计计计计算算算算mid mid 以以以以及及及及Rmid.keyRmid.key与与与与x x比比比比较较较较，每每每每比比比比较较较较一一一一次次次次，查查查查找找找找区区区区间间间间缩缩缩缩小小小小一一一一半半半半。当当当当
4、lowhighlowhigh时时时时，表表表表明明明明查查查查找找找找不成功，查找结束，返回不成功，查找结束，返回不成功，查找结束，返回不成功，查找结束，返回-1-1。12/31/20224电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录查找成功的例子查找成功的例子 查找失败的例子查找失败的例子12/31/20225电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录 n n折半查找算折半查找算折半查找算折半查找算法法法法intintintint BinSearch(DateTypeBinSearch(DateTypeBinSearch(DateTypeBi
5、nSearch(DateType R,R,R,R,KeyTypeKeyTypeKeyTypeKeyType x)x)x)x)intintintint low,high,midlow,high,midlow,high,midlow,high,mid;/low/low/low/low、highhighhighhigh表示当前查找区间的下界、上界表示当前查找区间的下界、上界表示当前查找区间的下界、上界表示当前查找区间的下界、上界 low=0;high=n-1;low=0;high=n-1;low=0;high=n-1;low=0;high=n-1;/设置查找区间下界、上界的初值设置查找区间下界、上界
6、的初值设置查找区间下界、上界的初值设置查找区间下界、上界的初值 while(low=high)while(low=high)while(low=high)while(low=high)/当前查找区间非空当前查找区间非空当前查找区间非空当前查找区间非空 mid=(low+high)/2;mid=(low+high)/2;mid=(low+high)/2;mid=(low+high)/2;/取当前查找区间的中点取当前查找区间的中点取当前查找区间的中点取当前查找区间的中点 if(x=if(x=if(x=if(x=Rmid.keyRmid.keyRmid.keyRmid.key)return mid;
7、)return mid;)return mid;)return mid;/查找成功，返回查找成功，返回查找成功，返回查找成功，返回 else else else else if(xif(xif(xif(x Rmid.keyRmid.keyRmid.keyRmid.key)high=mid-1;)high=mid-1;)high=mid-1;)high=mid-1;/在左区间查找在左区间查找在左区间查找在左区间查找 else low=mid+1;else low=mid+1;else low=mid+1;else low=mid+1;/在右区间查找在右区间查找在右区间查找在右区间查找 retur
8、n-1;return-1;return-1;return-1;/查找失败查找失败查找失败查找失败 12/31/20226电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n对于有序序列：对于有序序列：对于有序序列：对于有序序列：-1-1-1-1、0 0 0 0、1 1 1 1、3 3 3 3、4 4 4 4、6 6 6 6、8 8 8 8、10101010、12121212，折半查找判定树：折半查找判定树：折半查找判定树：折半查找判定树：vv树中每个圆形结点表示一个树中每个圆形结点表示一个树中每个圆形结点表示一个树中每个圆形结点表示一个记录，记录，记录，记录，结点的位序是该记
9、录结点的位序是该记录结点的位序是该记录结点的位序是该记录在表中的位置在表中的位置在表中的位置在表中的位置。所有结点的。所有结点的。所有结点的。所有结点的空指针域相当于指向一个方空指针域相当于指向一个方空指针域相当于指向一个方空指针域相当于指向一个方形结点，称为外部结点。形结点，称为外部结点。形结点，称为外部结点。形结点，称为外部结点。vv用当前查找区间的中间位置用当前查找区间的中间位置用当前查找区间的中间位置用当前查找区间的中间位置上的记录作为根，左区间和上的记录作为根，左区间和上的记录作为根，左区间和上的记录作为根，左区间和右区间中的记录分别作为根右区间中的记录分别作为根右区间中的记录分别作
10、为根右区间中的记录分别作为根的左、右子树。的左、右子树。的左、右子树。的左、右子树。vv不妨设结点总数不妨设结点总数不妨设结点总数不妨设结点总数 n n n n=2=2=2=2h h h h-1-1-1-1，则描述折半查找的判定树是高度为，则描述折半查找的判定树是高度为，则描述折半查找的判定树是高度为，则描述折半查找的判定树是高度为 h h h h 的满二叉树。的满二叉树。的满二叉树。的满二叉树。2 2 2 2h h h h =n n n n+1+1+1+1,h h h h=log=log=log=log2 2 2 2(n n n n+1)+1)+1)+1)。深度。深度。深度。深度h h h
11、h不计外部结点。不计外部结点。不计外部结点。不计外部结点。vv 第第第第1 1 1 1层结点有层结点有层结点有层结点有1 1 1 1个，查找第个，查找第个，查找第个，查找第1 1 1 1层结点要比较层结点要比较层结点要比较层结点要比较1 1 1 1次；第次；第次；第次；第2 2 2 2层结点有层结点有层结点有层结点有2 2 2 2个，个，个，个，查找第查找第查找第查找第2 2 2 2层结点要比较层结点要比较层结点要比较层结点要比较2 2 2 2次；次；次；次；。查找成功，最多比较查找成功，最多比较查找成功，最多比较查找成功，最多比较h h h h次次次次。时间复。时间复。时间复。时间复杂度为杂
12、度为杂度为杂度为O(logO(logO(logO(log2 2 2 2n)n)n)n)12/31/20227电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n对于有序序列：对于有序序列：对于有序序列：对于有序序列：-1-1-1-1、0 0 0 0、1 1 1 1、3 3 3 3、4 4 4 4、6 6 6 6、8 8 8 8、10101010、12121212，描述折半查找过程的判定树及查找描述折半查找过程的判定树及查找描述折半查找过程的判定树及查找描述折半查找过程的判定树及查找6 6 6 6和和和和5 5 5 5的过程：的过程：的过程：的过程：查找成功的情形查找成功的情形
13、 查找不成功的情形查找不成功的情形vv查找成功的过程就是走了一条查找成功的过程就是走了一条查找成功的过程就是走了一条查找成功的过程就是走了一条从根结点到该结点的路径从根结点到该结点的路径从根结点到该结点的路径从根结点到该结点的路径，经历，经历，经历，经历比较关键字的次数恰为该结点在树中的层数比较关键字的次数恰为该结点在树中的层数比较关键字的次数恰为该结点在树中的层数比较关键字的次数恰为该结点在树中的层数。vv查找不成功的过程是一条查找不成功的过程是一条查找不成功的过程是一条查找不成功的过程是一条从根结点到外部结点的路径从根结点到外部结点的路径从根结点到外部结点的路径从根结点到外部结点的路径，所
14、需的，所需的，所需的，所需的关键字比较次数是该路径上内部结点的总数关键字比较次数是该路径上内部结点的总数关键字比较次数是该路径上内部结点的总数关键字比较次数是该路径上内部结点的总数。12/31/20228电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录归并排序归并排序n算法思想算法思想算法思想算法思想假设初始表含有假设初始表含有n n个记录，则可看成是个记录，则可看成是n n个有序的子表，个有序的子表，每个子表的长度为每个子表的长度为1 1，然后两两归并，得到，然后两两归并，得到 n/2n/2 个长度个长度为为2 2或或1 1的有序子表，再两两归并，的有序子表，再两两归并，
15、如此重复，直如此重复，直至得到一个长度为至得到一个长度为n n的有序子表为止。的有序子表为止。n归并的过程归并的过程归并的过程归并的过程 将两个有序子表合并为一个有序子表的过程类似于玩将两个有序子表合并为一个有序子表的过程类似于玩扑克牌：假设桌上有两堆面朝上的牌，最小的排在上扑克牌：假设桌上有两堆面朝上的牌，最小的排在上面，现要将这两堆牌（看作输入）合并成一堆有序的面，现要将这两堆牌（看作输入）合并成一堆有序的牌（看作输出）。基本步骤是比较两输入堆顶上的两牌（看作输出）。基本步骤是比较两输入堆顶上的两张牌，取出较小的那张牌将它面朝下放到输出堆中。张牌，取出较小的那张牌将它面朝下放到输出堆中。重
16、复这一步骤，直至某一输入堆为空，这是将另一输重复这一步骤，直至某一输入堆为空，这是将另一输入堆中剩余的牌面朝下全部放入到输出堆中即可。如入堆中剩余的牌面朝下全部放入到输出堆中即可。如图所示：图所示：12/31/20229电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n n设两个有序子表（相当于输入堆）放在同一向量中相设两个有序子表（相当于输入堆）放在同一向量中相设两个有序子表（相当于输入堆）放在同一向量中相设两个有序子表（相当于输入堆）放在同一向量中相邻的位置上：邻的位置上：邻的位置上：邻的位置上：Rlow.mid,Rmid+1.highRlow.mid,Rmid+1.h
17、ighRlow.mid,Rmid+1.highRlow.mid,Rmid+1.high，先将它，先将它，先将它，先将它们合并到一个局部的暂存变量们合并到一个局部的暂存变量们合并到一个局部的暂存变量们合并到一个局部的暂存变量R1R1R1R1（相当于输出堆）中，（相当于输出堆）中，（相当于输出堆）中，（相当于输出堆）中，待合并完成后将待合并完成后将待合并完成后将待合并完成后将R1R1R1R1复制回复制回复制回复制回Rlow.highRlow.highRlow.highRlow.high 中。中。中。中。R Ri ji jlow highlow highk kR1R1low mid mid+low
18、mid mid+1 1 high high说明：加说明：加“*”区分两个区分两个252512/31/202210电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录 二路归并算法（二路归并算法（MergeSortMergeSort）调用）调用一趟归并算法（一趟归并算法（MergePassMergePass），一），一趟归并算法（趟归并算法（MergePassMergePass）调用归）调用归并算法（并算法（MergeMerge）。）。12/31/202211电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n归并算法归并算法归并算法归并算法void void
19、void void MERGE(rectypeMERGE(rectypeMERGE(rectypeMERGE(rectype R,intR,intR,intR,int low,intlow,intlow,intlow,int mid,intmid,intmid,intmid,int high)high)high)high)/*/*/*/*Rlow.midRlow.midRlow.midRlow.mid 与与与与Rmid+1.highRmid+1.highRmid+1.highRmid+1.high是两个有序子表，结果为一个有序子表是两个有序子表，结果为一个有序子表是两个有序子表，结果为一个有序
20、子表是两个有序子表，结果为一个有序子表Rlow.highRlow.highRlow.highRlow.high*/*/*/*/intintintint i=i=i=i=low,jlow,jlow,jlow,j=mid+1,k=0;=mid+1,k=0;=mid+1,k=0;=mid+1,k=0;rectyperectyperectyperectype*R1=(*R1=(*R1=(*R1=(rectyperectyperectyperectype*)malloc(high-low+1)*)malloc(high-low+1)*)malloc(high-low+1)*)malloc(high-lo
21、w+1)*sizeof(rectypesizeof(rectypesizeof(rectypesizeof(rectype););););if(!R1)if(!R1)if(!R1)if(!R1)printfprintfprintfprintf(“申请空间不成功申请空间不成功申请空间不成功申请空间不成功”);exit(0););exit(0););exit(0););exit(0);while(i=mid)&(j=high)while(i=mid)&(j=high)while(i=mid)&(j=high)while(i=mid)&(j=high)if(Ri.keyif(Ri.keyif(Ri.
22、keyif(Ri.key=Rj.keyRj.keyRj.keyRj.key)R1k+=)R1k+=)R1k+=)R1k+=RiRiRiRi+;+;+;+;else R1k+=else R1k+=else R1k+=else R1k+=RjRjRjRj+;+;+;+;/取小者复制到取小者复制到取小者复制到取小者复制到R1kR1kR1kR1k while(iwhile(iwhile(iwhile(i=mid)R1k+=mid)R1k+=mid)R1k+=mid)R1k+=RiRiRiRi+;+;+;+;/复制第一个子表的剩余记录复制第一个子表的剩余记录复制第一个子表的剩余记录复制第一个子表的剩余记
23、录 while(jwhile(jwhile(jwhile(j=high)R1k+=high)R1k+=high)R1k+=high)R1k+=RjRjRjRj+;+;+;+;/复制第二个子表的剩余记录复制第二个子表的剩余记录复制第二个子表的剩余记录复制第二个子表的剩余记录 for(kfor(kfor(kfor(k=0,i=0,i=0,i=0,i=low;ilow;ilow;ilow;i=high;k+,ihigh;k+,ihigh;k+,ihigh;k+,i+)+)+)+)RiRiRiRi=R1k;=R1k;=R1k;=R1k;/归并完成后将结果复制回归并完成后将结果复制回归并完成后将结果复制
24、回归并完成后将结果复制回Rlow.highRlow.highRlow.highRlow.high 12/31/202212电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n二路归并排序二路归并排序 第第1 1趟归并排序时，将趟归并排序时，将R1.nR1.n看成是看成是 n n 个个长度为长度为 1 1 的有序子序列的有序子序列 (归并项归并项)，先做两两，先做两两归并，得到归并，得到 n n/2/2 个长度为个长度为 2 2 的归并项的归并项 (如果如果 n n 为奇数，则最后一个有序子序列的长为奇数，则最后一个有序子序列的长度为度为1)1)；再做两两归并，；再做两两归并，
25、如此重复，最后，如此重复，最后得到一个长度为得到一个长度为 n n 的有序序列。的有序序列。12/31/202213电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录归并排序过程归并排序过程lenlen=1=1lenlen=2=2lenlen=4=4lenlen=8=8lenlen=16=1612/31/202214电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n一趟归并一趟归并 在给出二路归并排序算法之前，必须先解决一趟在给出二路归并排序算法之前，必须先解决一趟在给出二路归并排序算法之前，必须先解决一趟在给出二路归并排序算法之前，必须先解决一趟归并问题
26、。在某趟归并中，设各子表长度为归并问题。在某趟归并中，设各子表长度为归并问题。在某趟归并中，设各子表长度为归并问题。在某趟归并中，设各子表长度为lengthlengthlengthlength（最后一个子表的长度可能小于（最后一个子表的长度可能小于（最后一个子表的长度可能小于（最后一个子表的长度可能小于lengthlengthlengthlength），则归并前），则归并前），则归并前），则归并前R1.nR1.nR1.nR1.n中共有中共有中共有中共有 n n n n/length/length/length/length 个有序子表：个有序子表：个有序子表：个有序子表：R1.length,R
27、length+1.2*length,R1.length,Rlength+1.2*length,R1.length,Rlength+1.2*length,R1.length,Rlength+1.2*length,R(R(R(R(n n n n /length/length/length/length -1)*length+1.n-1)*length+1.n-1)*length+1.n-1)*length+1.n 调用归并操作将相邻的一对子表进行归并时，必须对调用归并操作将相邻的一对子表进行归并时，必须对调用归并操作将相邻的一对子表进行归并时，必须对调用归并操作将相邻的一对子表进行归并时，必须对子
28、表的个数可能是奇数，以及最后一个子表的长度小子表的个数可能是奇数，以及最后一个子表的长度小子表的个数可能是奇数，以及最后一个子表的长度小子表的个数可能是奇数，以及最后一个子表的长度小于于于于lehgthlehgthlehgthlehgth这两种特殊情况进行特殊处理：若子表的个这两种特殊情况进行特殊处理：若子表的个这两种特殊情况进行特殊处理：若子表的个这两种特殊情况进行特殊处理：若子表的个数为奇数，则最后一个子表无须和其它子表归并（即数为奇数，则最后一个子表无须和其它子表归并（即数为奇数，则最后一个子表无须和其它子表归并（即数为奇数，则最后一个子表无须和其它子表归并（即本趟轮空）；若子表的个数为
29、偶数，则要注意最后一本趟轮空）；若子表的个数为偶数，则要注意最后一本趟轮空）；若子表的个数为偶数，则要注意最后一本趟轮空）；若子表的个数为偶数，则要注意最后一对子表中的后一个子表的区间上界是对子表中的后一个子表的区间上界是对子表中的后一个子表的区间上界是对子表中的后一个子表的区间上界是n n n n。12/31/202215电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n一趟归并算法一趟归并算法一趟归并算法一趟归并算法void void void void MERGEPASS(rectypeMERGEPASS(rectypeMERGEPASS(rectypeMERGEPA
30、SS(rectype R,R,R,R,intintintint length)length)length)length)/对对对对R1.nR1.nR1.nR1.n做一趟归并，做一趟归并，做一趟归并，做一趟归并，lengthlengthlengthlength是本趟归并的有序子表的长度是本趟归并的有序子表的长度是本趟归并的有序子表的长度是本趟归并的有序子表的长度 intintintint i,ji,ji,ji,j;i=1;i=1;i=1;i=1;/i/i/i/i指向第一对子表的起始点指向第一对子表的起始点指向第一对子表的起始点指向第一对子表的起始点 while(i+2while(i+2while
31、(i+2while(i+2 lengthlengthlengthlength 1=n);1=n);1=n);1=n);/归并长度为归并长度为归并长度为归并长度为lengthlengthlengthlength的两个子的两个子的两个子的两个子表表表表 MERGE(R,i,i+length MERGE(R,i,i+length MERGE(R,i,i+length MERGE(R,i,i+length 1,i+21,i+21,i+21,i+2 lengthlengthlengthlength 1);1);1);1);i=i+2 i=i+2 i=i+2 i=i+2 length;length;len
32、gth;length;/i/i/i/i指向下一对子表的起始点指向下一对子表的起始点指向下一对子表的起始点指向下一对子表的起始点 if(i+lengthif(i+lengthif(i+lengthif(i+length 1)n)1)n)1)n)1)n)/剩下两个子表，其中后一个长度小于剩下两个子表，其中后一个长度小于剩下两个子表，其中后一个长度小于剩下两个子表，其中后一个长度小于lengthlengthlengthlength MERGE(R,R1,i,i+length MERGE(R,R1,i,i+length MERGE(R,R1,i,i+length MERGE(R,R1,i,i+leng
33、th 1,n);1,n);1,n);1,n);/归并最后两个子表归并最后两个子表归并最后两个子表归并最后两个子表 /若若若若inininin且且且且i+length-1ni+length-1ni+length-1ni+length-1n时，子表个数为奇数，无须归并时，子表个数为奇数，无须归并时，子表个数为奇数，无须归并时，子表个数为奇数，无须归并 12/31/202216电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n二路归并算法二路归并算法二路归并算法二路归并算法 二路归并排序须调用二路归并排序须调用二路归并排序须调用二路归并排序须调用“一趟归并一趟归并一趟归并一趟归并
34、”对对对对R1.nR1.nR1.nR1.n进行进行进行进行 loglogloglog2 2 2 2n n n n 趟归并，每趟归并后，有序子表的长度均扩大趟归并，每趟归并后，有序子表的长度均扩大趟归并，每趟归并后，有序子表的长度均扩大趟归并，每趟归并后，有序子表的长度均扩大一倍（最后一个可能例外）。其算法如下：一倍（最后一个可能例外）。其算法如下：一倍（最后一个可能例外）。其算法如下：一倍（最后一个可能例外）。其算法如下：void void void void MERGESORT(rectypeMERGESORT(rectypeMERGESORT(rectypeMERGESORT(rectyp
35、e R)/R)/R)/R)/对对对对R R R R进行二路归进行二路归进行二路归进行二路归并排序并排序并排序并排序 intintintint length;length;length;length;length=1;length=1;length=1;length=1;while(lengthn)while(lengthn)while(lengthn)while(lengthn)/进行进行进行进行 loglogloglog2 2 2 2n n n n 趟归并趟归并趟归并趟归并 MERGEPASS(R,length);MERGEPASS(R,length);MERGEPASS(R,length)
36、;MERGEPASS(R,length);length=2 length=2 length=2 length=2 length;length;length;length;/有序子表长度有序子表长度有序子表长度有序子表长度n n n n是结束循环是结束循环是结束循环是结束循环 12/31/202217电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n归并排序算法分析归并排序算法分析长长长长度度度度为为为为n n n n的的的的表表表表，共共共共进进进进行行行行 loglogloglog2 2 2 2n n n n 趟趟趟趟归归归归并并并并，每每每每趟趟趟趟归归归归并并并并的的
37、的的时时时时间间间间为为为为O(nO(nO(nO(n)，所以归并排序的时间复杂度为，所以归并排序的时间复杂度为，所以归并排序的时间复杂度为，所以归并排序的时间复杂度为O(nlogO(nlogO(nlogO(nlog2 2 2 2n)n)n)n)。归归归归并并并并排排排排序序序序占占占占用用用用附附附附加加加加存存存存储储储储较较较较多多多多，需需需需要要要要另另另另外外外外一一一一个个个个与与与与原原原原待待待待排排排排序序序序记记记记录录录录数数数数组组组组同同同同样样样样大大大大小小小小的的的的辅辅辅辅助助助助数数数数组组组组，空空空空间间间间复复复复杂杂杂杂度为度为度为度为O(nO(nO
38、(nO(n)。这是归并排序算法的缺点。这是归并排序算法的缺点。这是归并排序算法的缺点。这是归并排序算法的缺点。归并排序是一个稳定的排序方法。归并排序是一个稳定的排序方法。归并排序是一个稳定的排序方法。归并排序是一个稳定的排序方法。12/31/202218电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录快速排序快速排序n n快速排序方法的基本思想是任取待排序记录序列中的快速排序方法的基本思想是任取待排序记录序列中的快速排序方法的基本思想是任取待排序记录序列中的快速排序方法的基本思想是任取待排序记录序列中的某个记录某个记录某个记录某个记录 (例如取第一个记录例如取第一个记录例如
39、取第一个记录例如取第一个记录)作为枢轴作为枢轴作为枢轴作为枢轴(pivot)(pivot)，以，以，以，以该记录的关键字作为基准，将整个记录序列划分为左该记录的关键字作为基准，将整个记录序列划分为左该记录的关键字作为基准，将整个记录序列划分为左该记录的关键字作为基准，将整个记录序列划分为左右两个子序列：右两个子序列：右两个子序列：右两个子序列：uu 左侧子序列中所有记录的关键字都小于或等于枢轴左侧子序列中所有记录的关键字都小于或等于枢轴左侧子序列中所有记录的关键字都小于或等于枢轴左侧子序列中所有记录的关键字都小于或等于枢轴记录的关键字记录的关键字记录的关键字记录的关键字uu 右侧子序列中所有记
40、录的关键字都大于枢轴记录的右侧子序列中所有记录的关键字都大于枢轴记录的右侧子序列中所有记录的关键字都大于枢轴记录的右侧子序列中所有记录的关键字都大于枢轴记录的关键字关键字关键字关键字n n枢轴记录则排在这两个子序列中间枢轴记录则排在这两个子序列中间枢轴记录则排在这两个子序列中间枢轴记录则排在这两个子序列中间(这也是该记录最终这也是该记录最终这也是该记录最终这也是该记录最终应安放的位置应安放的位置应安放的位置应安放的位置)。n n然后分别对这两个子序列重复施行上述方法，直到所然后分别对这两个子序列重复施行上述方法，直到所然后分别对这两个子序列重复施行上述方法，直到所然后分别对这两个子序列重复施行
41、上述方法，直到所有的记录都按关键字有序排在相应位置上为止。有的记录都按关键字有序排在相应位置上为止。有的记录都按关键字有序排在相应位置上为止。有的记录都按关键字有序排在相应位置上为止。12/31/202219电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n快速排序算法快速排序算法快速排序算法快速排序算法采采采采 用用用用 快快快快 速速速速 排排排排 序序序序 方方方方 法法法法 对对对对 n n n n个个个个 记记记记 录录录录 排排排排 序序序序，只只只只 须须须须 调调调调 用用用用QuickSort(R,1,n)QuickSort(R,1,n)QuickSort
42、(R,1,n)QuickSort(R,1,n)，即即即即可可可可完完完完成成成成对对对对R1.nR1.nR1.nR1.n的的的的排排排排序序序序。快快快快速速速速排排排排序序序序算法如下：算法如下：算法如下：算法如下：void void void void QUICKSORT(rectypeQUICKSORT(rectypeQUICKSORT(rectypeQUICKSORT(rectype R,R,R,R,intintintint s1,int t1);s1,int t1);s1,int t1);s1,int t1);/对对对对RsRsRsRs1 1 1 1 到到到到RtRtRtRt1 1
43、1 1 做快速排序做快速排序做快速排序做快速排序 intintintint i;i;i;i;if(s1t1)if(s1t1)if(s1t1)if(s1=temp.key)&(itemp.key)&(itemp.key)&(itemp.key)&(ij)j)j)j)j j j j;/从右向左扫描，查找第一个关键字小于从右向左扫描，查找第一个关键字小于从右向左扫描，查找第一个关键字小于从右向左扫描，查找第一个关键字小于temp.keytemp.keytemp.keytemp.key的记录的记录的记录的记录 if(iif(iif(iif(ij)j)j)j)RiRiRiRi+=+=+=+=RjRjRj
44、Rj;/交换交换交换交换RiRiRiRi 和和和和RjRjRjRj while(Ri.keywhile(Ri.keywhile(Ri.keywhile(Ri.key=temp.key)&(itemp.key)&(itemp.key)&(itemp.key)&(ij)j)j)j)i+;i+;i+;i+;/从左向右扫描，查找第一个关键字大于从左向右扫描，查找第一个关键字大于从左向右扫描，查找第一个关键字大于从左向右扫描，查找第一个关键字大于temp.keytemp.keytemp.keytemp.key的记录的记录的记录的记录 if(iif(iif(iif(ij)j)j)j)RjRjRjRj=Ri
45、RiRiRi;/交换交换交换交换RiRiRiRi 和和和和RjRjRjRj while(iwhile(iwhile(iwhile(i!=j);!=j);!=j);!=j);RiRiRiRi=temp;=temp;=temp;=temp;/基准基准基准基准temptemptemptemp已被最后定位已被最后定位已被最后定位已被最后定位 return i;return i;return i;return i;12/31/202221电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录第一次划分的过程第一次划分的过程电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录各趟排序之后的状态各趟排序之后的状态电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录习题习题n设顺序表为设顺序表为22、5 5、7 7、1010、1414、1515、1818、2323、3535、4141、52 52，画出折半查找判定树，计算，画出折半查找判定树，计算查找查找1515、7 7、1414、1212所需的比较次数分别是所需的比较次数分别是多少？多少？n对关键字序列对关键字序列1919，1111，2727，1818，3333进行快速进行快速排序，写出每一趟的排序结果。排序，写出每一趟的排序结果。12/31/202224