算法分析与设计第四章(分治法快速分类)课件

1、第四章 分治法2008-09-01版权所有：杨波，武汉科技大学理学院 4.5 快速分类1.划分与快速分类 快速分类是一种基于划分的分类方法； 划分：选取待分类集合A中的某个元素t，按照与t的大小关系重 新整理A中元素，使得整理后t被置于序列的某位置上， 而序列中所有在t以前出现的元素均小于等于t，而所有出 现在t以后的元素均大于等于t。这一元素的整理过程称为 划分（Partitioning）。 元素t称为划分元素。 快速分类：通过反复地对待排序集合进行划分达到分类目的的分类算法。2008-09-01版权所有：杨波，武汉科技大学理学院 快速分类的基本思想 对于输入的子数组am:p-1，按以下3个

2、步骤进行排序： 分解（divide）：以am为基准元素（假定第一个元素am是划分元素）将am:p-1分成3段am:q-1，aq和aq+1:p-1，使得am:q-1中任何元素小于等于aq，aq+1:p-1中任何元素大于等于aq，下标q 在划分过程中确定。 递归求解（conquer）：通过递归调用快速排序算法，分别对am:q-1和aq+1:p-1进行排序。 合并（merge）：由于对 am:q-1和aq+1:p-1的排序是就地进行的，所以在am:q-1和aq+1:p-1都已排好序后不需要执行任何计算，am:p-1就已排好序 。2008-09-01版权所有：杨波，武汉科技大学理学院 划分过程的算法描

3、述public static int Partition(int m,int p)/在am，am+1，ap-1中的元素按如下方式重新排列：如果最初t=am，则在重排完成之后， /对于m和p-1之间的某个q，有aq=t，并使得对于mkq，有ak t，而对于qkp，有ak t。 /退出时返回值为划分元素所在的下标位置 int i,v;/v为划分元素，i为从左到右计数，p从右到左计数 v=am;i=m+1;p=p-1; int temp;/临时交换单元 while(true) while(aiv) p-;/直到不大于v,p向左移动 if(ip) /ai与ap交换位置 temp=ai; ai=ap;

4、ap=temp; else break; am=ap;ap=v; /划分元素在位置p return p;ap被定义，但为一限界值apam ，不包含在实际的分类区间内。(技巧：假如是按照从大到小排列，经过Partition算法之后进行从小到大排列，引入ap则程序易于实现）算法对集合am:p-1进行划分元素am作为划分元素2008-09-01版权所有：杨波，武汉科技大学理学院 划分实例（1次划分）12345678910iP65707580856055504510000296545758085605550701000038654550808560557570100004765455055856080

5、757010000566545505560858075701000065604550556585807570100005Partition(m,p)=Partition(1,10)划分元素p=52008-09-01版权所有：杨波，武汉科技大学理学院 经过一次“划分”后，实现了对集合元素的调整： 以划分元素为界，左边子集合的所有元素均小于等于右边子集合的所有元素。 按同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类方法称为快速分类。2008-09-01版权所有：杨波，武汉科技大学理学院 快速分类算法public static

6、 void QuickSort(int p,int q)/将全程数组a1:n中的元素ap，aq按递增的方式分类。 /认为an+1已被定义，且大于或等于ap:q的所有元素；即an+1=+ int j; if(pq) j=q+1;/每次执行Partition时使用一个右侧附加空间p:q等同与m:p-1 /m=p;p-1=q; j=Partition(p,j);/j是划分元素的位置 QuickSort(p,j-1);/对左半段排序 QuickSort(j+1,q);/对右半段排序 2008-09-01版权所有：杨波，武汉科技大学理学院 全部分类过程12345678916570758085605550

7、4526045505565858075703554550606585807570450455560658580757054550556065858075706455055606585807570745505560657080758584550556065708075859455055606570758085104550556065707580852008-09-01版权所有：杨波，武汉科技大学理学院 快速分类分析统计的对象：元素的比较次数，记为：C(n)两点假设参加分类的n个元素各不相同Partition中的划分元素v是随机选取的（针对平均情况的分析）随机选取划分元素：在划分区间m,p-1随机

8、生成某一坐标：iRandom(m,p-1)；调换am与ai;vai;aiam;im+1; 作用：将随机指定的划分元素的值调换到 am位置。算法主体不变。之后，仍从am开始执行划分操作。2008-09-01版权所有：杨波，武汉科技大学理学院 递归层次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(j1+1,n)QuickSort(1,j21-1)QuickSort(j21+1, j1-1)QuickSort(j1+1,j22-1)QuickSort(j22+1,n)n个元素参加划分和分类去掉1个第一级的划分元素n-1个元素参加划分和分类去掉2个第二级的划分元素n

9、-3个元素参加划分和分类去掉4个第三级的划分元素第一层第二层第三层 设在任一级递归调用上，调用Partition处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1：理想情况，（与前一级相比）第二级少1，第三级少2，第四级少4， ；最坏情况，每次仅减少1（每次选取的划分元素刚好是当前集合中最小或最大者）2008-09-01版权所有：杨波，武汉科技大学理学院 最坏情况分析记最坏情况下的元素比较次数是Cw(n)；设r是在任一级递归上对Partition的所有调用的元素总数。在一级只有一次调用，执行Partition(1,n+1)，且r=n，因此

10、，比较数至多是n+1；在二级至多作两次调用（一次实际不做任何处理），且r=n-1，因此，比较数至多是n等等。因此，在递归的任意一级上，所有的Partition共作r+1次元素比较，而每一级的r，由于删去了前一级的划分元素，故比前一级的r至少要少1。Cw(n)是r由n变到2的和，即Cw(n)=O(n2)。2008-09-01版权所有：杨波，武汉科技大学理学院 最坏情况举例k01234n-1nn+1ak-n123n-2n-1渐近时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 最好情况下渐近时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 平均情况分析 平均情况是指

11、集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。 设调用Partition(m,p)时，所选取划分元素v恰好是am:p-1中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是am:j-1和aj+1:p-1的概率是：1/(p-m), mjp。 记平均情况下的元素比较次数是CA(n)；则有： 其中， n+1是Partition第一次调用时所需的元素比较次数。 CA(0) = CA(1) = 0(1)2008-09-01版权所有：杨波，武汉科技大学理学院 用n-1换(2)中的n (2)-(3) 即 反

12、复使用(4)代换CA(n-1)，CA(n-2)，得到 2008-09-01版权所有：杨波，武汉科技大学理学院 由于 所以 2008-09-01版权所有：杨波，武汉科技大学理学院 空间分析 最坏情况下，递归的最大深度为n-1. 需要栈空间：O(n) 使用一个迭代模型可以将栈空间总量减至O(logn)最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)2008-09-01版权所有：杨波，武汉科技大学理学院 快速分类算法的迭代模型处理策略：每次在Partition将文件A(p:q)分成两个文件A(p:j-1)和A(j+1,q)后，先对其中较小的子文件进行分类。

13、当小的子文件分类完成后，再对较 大的子文件进行分类。栈：需要一个栈空间保存目前暂不分类的较大子文件。并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一步分类。栈空间需求量：O(logn)算法终止：当栈空时，整个分类过程结束。2008-09-01版权所有：杨波，武汉科技大学理学院 QuickSort的迭代模型 public static void QuickSort2(int p,int q) int stack,top,j; stack=new int11; top=0; while(true) while(pq) j=q+1; j=Partition(p,j); if(j-pq-j

14、) stacktop+1=j+1; stacktop+2=q; q=j-1;/左半文件较小先处理 /将大的子文件入栈后处理 else stacktop+1=p; stacktop+2=j-1; p=j+1;/右半文件较小先处理 top=top+2; if(top=0) break; q=stacktop;p=stacktop-1; top=top-2; public static void QuickSort(int p,int q) int j; if(pq) j=q+1 j=Partition(p,j); QuickSort(p,j-1); QuickSort(j+1,q); 2008-0

15、9-01版权所有：杨波，武汉科技大学理学院 快速分类算法迭代模型的空间分析设算法所需的最大栈空间是S(n)，则有 2008-09-01版权所有：杨波，武汉科技大学理学院 4.6 选择问题1. 问题描述 在n个元素的表a1:n中确定第k小元素，1kn。2. 设计思路 利用Partition过程。在第一次划分后划分元素v测定在aj的位置上，则有j-1个元素小于或等于aj，且有n-j个元素大于或等于aj。此时， 若k=j，则aj即是第k小元素；否则， 若kj，则a1:n中的第k小元素将出现在aj+1:n， 是aj+1:n中的第k-j小元素。2008-09-01版权所有：杨波，武汉科技大学理学院 利用

16、Partition实现的选择算法public static void Select(int n,int k) /在数组a1,an中找第k小元素s并把它放在位置k，假设1kn。 /将剩下的元素按如下方式排列，使ak=t，对于1mk，有amt；对于 /kmn，有amt。an+1=+ int m,r,j; m=1;r=n+1;an+1=10000; while(true) /每当进入这一循环时，1mkrn+1 j=r; /将剩余元素的最大下标加1后给j j=Partition(m,j); /返回j，它使得aj是第j小的值 if(kj) r=j; /j是新的上界 else if(k=j) return

17、; else m=j+1; /j+1是新的下界 2008-09-01版权所有：杨波，武汉科技大学理学院 m=1;r=n+1;an+1=10000; while(true) j=r; j=Partition(m,j); if(k0，使得 ：因此， 划分元素ik,将在i的前半部分求解2008-09-01版权所有：杨波，武汉科技大学理学院 选择cR(1)，对问题规模n进行归纳，证明对于所有n2，有R(n)4cn 归纳基础 对于n=2由上式有 归纳假设 假定对于所有的n，2nm， R(n)4cn。 归纳步骤 对于n=m， 由于R(n)是n的非降函数，故可以得到当m为偶数而k=m/2时，或者当m为奇数而

18、k=(m+1)/2时，取极大值。因此 若m为偶数，则 若m为奇数，则 由于 TA(n)R(n)，所以TA(n)4cn，故TA(n)=O(n)2008-09-01版权所有：杨波，武汉科技大学理学院 最坏情况时间是O(n)的选择算法基本思想：精心挑选划分元素v方法：二次取中间值目的：使v比一部分元素小比另一部分元素大2008-09-01版权所有：杨波，武汉科技大学理学院 二次取中间值作为划分元素v 首先，将参加划分的n个元素分成 组，每组有r个元素(r1)。（多余的 个元素忽略不计） 然后，对这 组每组的r个元素进行分类并找出其中间元素mi,1i ，共得 个中间值。 之后，对这 个中间值分类，并找

19、出其中间值mm。将mm作为划分元素执行划分。2008-09-01版权所有：杨波，武汉科技大学理学院 例：设n=35，r=7。分为n/r=5个元素组：B1，B2，B3，B4，B5，每组7个元素。每组7个元素沿列而下已排成一个非降序列。 每列中间的元素就是mi。而且这些列也按的mi非降次序进行排列。因此，第3列的mi就是mm。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列2008-09-01版权所有：杨波，武汉科技大学理学院 由于r个元素的中间值是第 小元素。则， 至少有 个mi小于或等于mm； 至少有 个mi大于或等于mm。 故，至少有

20、个元素小于或等于（或大于或等于）mm。 当r=5，则使用两次取中间值规则来选择v=mm，可得到， 至少有 个元素小于或等于选择元素v。 且至多有 个元素大于v。 同理，至多有 0.7n+1.2个元素小于v。 故，这样的v可较好地划分a中的n个元素。2008-09-01版权所有：杨波，武汉科技大学理学院 使用二次取中规则的选择算法的说明性描述public static int Select2(int a,int k,int n) /在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。 把a分成大小为r的 个子集合，忽略剩余的元素。 设 是上面 个子集合的中间值的集合。 用P

21、artition划分a，v作为划分元素。 假设v在位置j。 case k=j: return(v); kj: 设S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:设R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j)2008-09-01版权所有：杨波，武汉科技大学理学院 算法分析记T(n)是Select2所需的最坏情况时间对特定的r分析Select2，选取r=5。(a中的元素各不相同)2008-09-01版权所有：杨波，武汉科技大学理学院 public static int Select2(int a,int k,int n)

22、/在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。 把a分成大小为r的 个子集合，忽略剩余的元素。 设 是上面 个子集合的中间值的集合。 用Partition划分a，v作为划分元素。 假设v在位置j。 case k=j: return(v); kn 两个子问题的规模和大于原问题。 改进： 取r=9。经计算可得，此时将有 个元素小于或等于v，同时至少有 大于或等于v。 则当n90时，|S|和|R|都至多为：public static int Select2(int a,int k,int n) /在集合a中找第k小元素 case k=j: return(v); kj:

23、设S是a1:j-1中元素的集合 return(Select2(S,k,j-1) else:设R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j)T(n)T(n/5)+T(3n/4)+cn2008-09-01版权所有：杨波，武汉科技大学理学院 用归纳法可证：T(n)72c1n即：T(n)=O(n)2008-09-01版权所有：杨波，武汉科技大学理学院 Select2的实现算法中需要解决的两个问题 1) 如何确定子集合的中间值 当r较小时，采用InsertionSort(a,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为当前r个元素中的中间位置下标对应的元素。 2) 如何保存 个子集合的中间值 注：各组找到的中间元素值将调整到数组a的前部，连续保存，从而可用递归调用