第12章_缩小规模算法

1、2020/7/15,1,第12章 缩小规模算法,2020/7/15,2,第12章 缩小规模算法,二分搜索技术 归并排序 快速排序 习题,2020/7/15,3,二分搜索技术（二分查找、折半查找）,要求线性表是顺序存储结构的有序表。 n个记录R0Rn-1按关键字key递增有序,在n个记录中找出关键字的值为x的记录。,2020/7/15,4,算法的基本思想： （1）先求位于查找区间正中的记录的下标mid： mid= (low+high)/2 （2）用其关键字与给定值x比较: 如果 x = = Rmid.key，则查找成功，返回mid值 如果 x Rmid.key，则在右区间继续查找，置low=mi

2、d+1 (3) 重复计算mid 以及Rmid.key与x比较，每比较一次，查找区间缩小一半。当lowhigh时，表明查找不成功，查找结束，返回-1。,2020/7/15,5,查找成功的例子 查找失败的例子,2020/7/15,6,折半查找算法 int BinSearch(DateType R ,KeyType x) int low,high,mid; /low、high表示当前查找区间的下界、上界 low = 0; high = n-1; /设置查找区间下界、上界的初值 while (low = high) /当前查找区间非空 mid = (low+high)/2; /取当前查找区间的中点 i

3、f (x=Rmid.key) return mid; /查找成功，返回 else if(xRmid.key) high = mid-1; /在左区间查找 else low = mid+1; /在右区间查找 return -1; /查找失败 ,2020/7/15,7,对于有序序列：-1、0、1、3、4、6、8、10、12，折半查找判定树：,树中每个圆形结点表示一个记录，结点的位序是该记录在表中的位置。所有结点的空指针域相当于指向一个方形结点，称为外部结点。 用当前查找区间的中间位置上的记录作为根，左区间和右区间中的记录分别作为根的左、右子树。,不妨设结点总数 n = 2h-1，则描述折半查找的判

4、定树是高度为 h 的满二叉树。2h = n+1, h = log2(n+1)。深度h不计外部结点。 第1层结点有1个，查找第1层结点要比较1次；第2层结点有2个，查找第2层结点要比较2次；。查找成功，最多比较h次。时间复杂度为O(log2n),2020/7/15,8,对于有序序列：-1、0、1、3、4、6、8、10、12，描述折半查找过程的判定树及查找6和5的过程：,查找成功的情形 查找不成功的情形,查找成功的过程就是走了一条从根结点到该结点的路径，经历比较关键字的次数恰为该结点在树中的层数。 查找不成功的过程是一条从根结点到外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。,20

5、20/7/15,9,归并排序,算法思想假设初始表含有n个记录，则可看成是n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2个长度为2或1的有序子表，再两两归并，如此重复，直至得到一个长度为n的有序子表为止。 归并的过程 将两个有序子表合并为一个有序子表的过程类似于玩扑克牌：假设桌上有两堆面朝上的牌，最小的排在上面，现要将这两堆牌（看作输入）合并成一堆有序的牌（看作输出）。基本步骤是比较两输入堆顶上的两张牌，取出较小的那张牌将它面朝下放到输出堆中。重复这一步骤，直至某一输入堆为空，这是将另一输入堆中剩余的牌面朝下全部放入到输出堆中即可。如图所示：,2020/7/15,10,设两个有序子

6、表（相当于输入堆）放在同一向量中相邻的位置上：Rlow.mid,Rmid+1.high，先将它们合并到一个局部的暂存变量R1（相当于输出堆）中，待合并完成后将R1复制回Rlow.high中。,2020/7/15,11,二路归并算法（MergeSort）调用一趟归并算法（MergePass），一趟归并算法（MergePass）调用归并算法（Merge）。,2020/7/15,12,归并算法 void MERGE(rectype R,int low,int mid,int high) /* Rlow.mid与Rmid+1.high是两个有序子表，结果为一个有序子表Rlow.high */ int

7、i=low,j=mid+1,k=0;rectype*R1=(rectype*)malloc(high-low+1)*sizeof(rectype);if(!R1) printf(“申请空间不成功”); exit(0); while (i=mid) /归并完成后将结果复制回Rlow.high ,2020/7/15,13,二路归并排序 第1趟归并排序时，将R1.n看成是 n 个长度为 1 的有序子序列 (归并项)，先做两两归并，得到 n / 2 个长度为 2 的归并项 (如果 n 为奇数，则最后一个有序子序列的长度为1)；再做两两归并，如此重复，最后得到一个长度为 n 的有序序列。,2020/7/

8、15,14,归并排序过程,21,25,25*,25*,93,62,72,08,37,16,54,49,21,25,49,62,93,08,72,16,37,54,21,25,25*,49,08,62,72,93,16,37,54,08,08,21,16,25,21,25*,25,49,25*,62,37,72,49,93,54,16,37,54,62,72,93,len=1,len=2,len=4,len=8,len=16,2020/7/15,15,一趟归并 在给出二路归并排序算法之前，必须先解决一趟归并问题。在某趟归并中，设各子表长度为length（最后一个子表的长度可能小于length），

9、则归并前R1.n中共有n /length个有序子表：R1.length,Rlength+1.2*length,R(n /length-1)*length+1.n 调用归并操作将相邻的一对子表进行归并时，必须对子表的个数可能是奇数，以及最后一个子表的长度小于lehgth这两种特殊情况进行特殊处理：若子表的个数为奇数，则最后一个子表无须和其它子表归并（即本趟轮空）；若子表的个数为偶数，则要注意最后一对子表中的后一个子表的区间上界是n。,2020/7/15,16,一趟归并算法 void MERGEPASS(rectype R , int length) / 对R1.n做一趟归并，length是本趟归

10、并的有序子表的长度 int i,j; i=1 ; / i指向第一对子表的起始点 while (i+2length1=n); /归并长度为length的两个子表 MERGE(R,i,i+length1,i+2length1); i=i+2length; / i指向下一对子表的起始点 if(i+length1)n) /剩下两个子表，其中后一个长度小于length MERGE(R,R1,i,i+length1,n); /归并最后两个子表 / 若in且i+length-1n时，子表个数为奇数，无须归并 ,2020/7/15,17,二路归并算法 二路归并排序须调用“一趟归并”对R1.n进行log2n趟归

11、并，每趟归并后，有序子表的长度均扩大一倍（最后一个可能例外）。其算法如下： void MERGESORT(rectype R ) / 对R进行二路归并排序 int length; length=1; while (lengthn) /进行log2n趟归并 MERGEPASS(R, length); length=2length; /有序子表长度n是结束循环 ,2020/7/15,18,归并排序算法分析 长度为n的表，共进行log2n趟归并，每趟归并的时间为O(n)，所以归并排序的时间复杂度为O(nlog2n)。 归并排序占用附加存储较多，需要另外一个与原待排序记录数组同样大小的辅助数组，空间复

12、杂度为O(n)。这是归并排序算法的缺点。 归并排序是一个稳定的排序方法。,2020/7/15,19,快速排序,快速排序方法的基本思想是任取待排序记录序列中的某个记录 (例如取第一个记录) 作为枢轴(pivot)，以该记录的关键字作为基准，将整个记录序列划分为左右两个子序列： 左侧子序列中所有记录的关键字都小于或等于枢轴记录的关键字 右侧子序列中所有记录的关键字都大于枢轴记录的关键字 枢轴记录则排在这两个子序列中间(这也是该记录最终应安放的位置)。 然后分别对这两个子序列重复施行上述方法，直到所有的记录都按关键字有序排在相应位置上为止。,2020/7/15,20,快速排序算法 采用快速排序方法对

13、n个记录排序，只须调用QuickSort(R,1,n)，即可完成对R1.n的排序。快速排序算法如下： void QUICKSORT(rectype R ,int s1,int t1); /对Rs1到Rt1做快速排序 int i; if (s1t1) / 只有一个记录或无记录时无须排序 i=PARTITION(R,s1,t1); / 对Rs1到Rt1做划分，i作为枢轴的位置 QUICKSORT(R,s1,i1); / 递归处理左区间 QUICKSORT(R,i+1,t1); / 递归处理右区间 ,2020/7/15,21,快速排序算法须调用划分算法对无序区按基准进行划分。划分算法如下： int PARTITION(rectype R ,int l,int h) /对无序区R1.h做划分，返回划分后被定位的基准记录(枢轴）的位置 int i,j; rectype te