分治策略快速排序.ppt

《分治策略快速排序.ppt》由会员分享，可在线阅读，更多相关《分治策略快速排序.ppt（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分治策略快速排序分治策略快速排序现在学习的是第1页，共31页QuickSortlSelect a pivot (partitioning element)lRearrange the list so that all the elements in the positions before the pivot are smaller than or equal to the pivot and those after the pivot are larger than the pivot lExchange the pivot with the last element in the firs

2、t (i.e., sublist) the pivot is now in its final positionlSort the two sublists2现在学习的是第2页，共31页2.5 快速排序问题快速排序问题基本策略是：基本策略是：将数组将数组A1:n分解成两个子数组分解成两个子数组B1:p和和Bp+1:n，使得，使得B1:p中的元素均不大于中的元素均不大于Bp+1:n中的元素，然后分别对这里两个数组中中的元素，然后分别对这里两个数组中的元素进行排序（非降的），最后再把两个排好的元素进行排序（非降的），最后再把两个排好序的数组接起来即可。序的数组接起来即可。pAipAip3现在学习的

3、是第3页，共31页l选取选取A的某个元素的某个元素t=A(s)，然后将其他元素重新排列，然后将其他元素重新排列，使，使A(1:n)中所有在中所有在t以前出现的元素都小于或等以前出现的元素都小于或等于于t，而在，而在t之后出现的元素都大于或等于之后出现的元素都大于或等于t。A(1)A(2)A(s-1)A(s)A(s+1)A(n)t划分元素划分元素A(n)A(k)tA(j)A(2)A(1)经过一次划分后经过一次划分后每个元素都小于或等于每个元素都小于或等于t每个元素都大于或等于每个元素都大于或等于t2.5 快速排序问题快速排序问题4现在学习的是第4页，共31页The partition algor

4、ithm5现在学习的是第5页，共31页算法步骤算法步骤l分解分解(Divide):以以ap为基准元素将为基准元素将ap:r划分成划分成3段段ap:q-1,aq和和aq+1:r,使得使得ap:q-1中任何一中任何一个小于等于个小于等于aq,下标下标q在划分过程中确定。在划分过程中确定。l递归求解递归求解(conquer):通过递归调用快速排序算法通过递归调用快速排序算法分别对分别对ap:q-1和和aq+1:r进行排序。进行排序。l合并合并(Merge):由于对由于对ap:q-1和和aq+1:r的排序是的排序是就地进行的，所以在就地进行的，所以在ap:q-1和和aq+1:r都已排好都已排好的序后步

5、需执行任何计算的序后步需执行任何计算ap:r就已排好序。就已排好序。2.5快速排序问题快速排序问题6现在学习的是第6页，共31页快速排序快速排序templatevoid QuickSort(Type a , int p,int r) if(pr) int q=Partition(a,p,r); QuickSort(a,p,q-1);/对左半段排序对左半段排序 QuickSort(a,q+1,r);/对右半段排序对右半段排序 a的起始位置的起始位置a的终止位置的终止位置Partition函数负责将函数负责将a进行一次分割，返回分进行一次分割，返回分割元素的位置割元素的位置快速排序问题快速排序问题

6、2.5快速排序问题快速排序问题7现在学习的是第7页，共31页划分过程划分过程lPartition的过程中，首先要选择一个元素，根的过程中，首先要选择一个元素，根据其值划分数组。称该元素为中轴。据其值划分数组。称该元素为中轴。l选择中轴有许多不同的策略，我们使用最简单选择中轴有许多不同的策略，我们使用最简单的策略，选择第一个元素：的策略，选择第一个元素：s = ap。快速排序问题快速排序问题2.5快速排序问题快速排序问题8现在学习的是第8页，共31页划分举例划分举例(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)ip657075808560555045+29654575808560

7、555070+38654550808560557570+47654550558560807570+56654550556085807570+65604550556585807570+快速排序问题快速排序问题2.5快速排序问题快速排序问题 Figure 2-19现在学习的是第9页，共31页划分的过程划分的过程l使用一种两次扫描子数组的方法使用一种两次扫描子数组的方法:一次是一次是从左到右从左到右,另一次是另一次是从右到左从右到左,每次都把子数组的元素和中轴进行比较。每次都把子数组的元素和中轴进行比较。l从左到右的扫描从左到右的扫描从第二个元素从第二个元素开始开始,希望小于中轴的元素位于希望小于中

8、轴的元素位于子数组的第一部分，扫描会忽略小于中轴的元素，子数组的第一部分，扫描会忽略小于中轴的元素，直到遇到第直到遇到第一个大于等于中轴的元素才会停止一个大于等于中轴的元素才会停止。l从右到左的扫描从从右到左的扫描从最后一个元素最后一个元素开始，因为我们希望大于中轴开始，因为我们希望大于中轴的元素位于子数组的第二部分，扫描会忽略大于中轴的元素，的元素位于子数组的第二部分，扫描会忽略大于中轴的元素，直到遇到第一个小于等于中轴的元素才会停止。直到遇到第一个小于等于中轴的元素才会停止。快速排序问题快速排序问题2.5快速排序问题快速排序问题10现在学习的是第10页，共31页P全部全部=p=pij全部全

9、部=p=p全部全部=p=p=p全部全部=pPij快速排序问题快速排序问题如果扫描指针如果扫描指针i和和j不相交，不相交，ij, 把中轴和把中轴和Aj交换，得到该数组的一个分区。交换，得到该数组的一个分区。如果扫描指针如果扫描指针i指向同一元素，指向同一元素，ij，被指向元素的值一定等于，被指向元素的值一定等于p。2.5快速排序问题快速排序问题11现在学习的是第11页，共31页划分程序划分程序 template int Partition(Type a ,int p,int r) int i = , j = ; Type x = ; while( true ) while( a +i x );

10、if( ) break; Swap( a i , a j ); a p = ; a j = ; return j;快速排序问题快速排序问题pr+1a p i = ja j x左侧扫描指针起始左侧扫描指针起始右侧扫描指针起始右侧扫描指针起始中轴元素中轴元素移动左侧扫描指针移动左侧扫描指针移动右侧扫描指针移动右侧扫描指针2.5快速排序问题快速排序问题该算法是否有问题？该算法是否有问题？12现在学习的是第12页，共31页快速排序问题快速排序问题例：排列例：排列 5，3，1，9，8，2，4，70 1 2 3 4 5 6 7 i j5 3 1 9 8 2 4 7 i j5 3 1 9 8 2 4 7 i

11、 j5 3 1 4 8 2 9 7 i j5 3 1 4 8 2 9 7 i j5 3 1 4 2 8 9 7 j i5 3 1 4 2 8 9 7 2 3 1 4 5 8 9 7 i j2 3 1 4 i j2 3 1 4 i j2 1 3 4 j i2 1 3 41 2 3 41 i j 3 4 j i 3 4 4 i j8 9 7 j i8 7 97 8 9792.5快速排序问题快速排序问题13现在学习的是第13页，共31页问题：问题：l扫描停止的时候扫描停止的时候i和和j有几种关系，每种代表哪有几种关系，每种代表哪种情况？种情况？l下标下标i和和j会不会超出会不会超出a的下标界？的下标

12、界？l该排序算法是否稳定？该排序算法是否稳定？快速排序问题快速排序问题2.5快速排序问题快速排序问题14现在学习的是第14页，共31页Efficiency of QuickSortlBest case: split in the middle ( n log n) lWorst case: sorted array! ( n2) lAverage case: random arrays ( n log n)lImprovements:lbetter pivot selection: median of three partitioning avoids worst case in sorted

13、 fileslswitch to insertion sort on small subfileslelimination of recursionthese combine to 20-25% improvementlConsidered the method of choice for internal sorting for large files (n 10000)15现在学习的是第15页，共31页算法分析l最坏情况：划分的两个区域分别包含最坏情况：划分的两个区域分别包含n-1个元素和个元素和1个元素，也个元素，也就是已经排好序的数组。如果用就是已经排好序的数组。如果用A0作为中轴，从

14、左到右的作为中轴，从左到右的扫描会停在扫描会停在A1上，而从右到左的扫描会一直处理到上，而从右到左的扫描会一直处理到A0，导，导致分裂点出现在致分裂点出现在0这个位置，所以，在进行了这个位置，所以，在进行了n1次比较之后次比较之后建立了分区，并且将建立了分区，并且将A0 和它本身进行了交换以后，快速排和它本身进行了交换以后，快速排序算法还会对严格递增的数组序算法还会对严格递增的数组A1n-1进行排序，对规模减进行排序，对规模减小了的严格递增数组的排序会一直继续到最后一个子数组小了的严格递增数组的排序会一直继续到最后一个子数组An-2n-1，这种情况下，键值比较的总次数应该等于：，这种情况下，键

15、值比较的总次数应该等于：l(n+1)+n+3=O(n2)快速排序问题快速排序问题2.5快速排序问题快速排序问题16现在学习的是第16页，共31页算法分析l最坏情况：划分的两个区域分别包含最坏情况：划分的两个区域分别包含n1个元个元素和素和1个元素，如果每一步都出现这种情况，个元素，如果每一步都出现这种情况，其复杂性其复杂性T(n) O(1) n1 T(n)= T(n-1)+O(n) n1解得：解得：T(n)=O(n2)快速排序问题快速排序问题2.5快速排序问题快速排序问题17现在学习的是第17页，共31页l最好情况最好情况:每次划分所取的基准都恰好为中值每次划分所取的基准都恰好为中值，即每次划

16、分都产生两个大小为，即每次划分都产生两个大小为n/2的区域，的区域， O(1) n1 T(n)= 2T(n/2)+O(n) n1 T(n)=O(nlogn)快速排序问题快速排序问题2.5快速排序问题快速排序问题18现在学习的是第18页，共31页计数排序、冒泡排序、插入排序、选择排序、归并排序和快速排序的时间复杂性如下：l算法算法 最坏复杂性最坏复杂性 平均复杂性平均复杂性l冒泡排序冒泡排序 n2 n2l计数排序计数排序 n2 n2l插入排序插入排序 n2 n2l选择排序选择排序 n2 n2l快速排序快速排序 n2 n log nl归并排序归并排序 n log n n log n 快速排序问题快

17、速排序问题2.5快速排序问题快速排序问题19现在学习的是第19页，共31页2.6 线性时间选择线性时间选择 Selection in Linear Time l问题：问题：已知已知n元数组元数组A1:n，试确定其中第，试确定其中第k小小的元素。的元素。l如果如果k1，就是找最小的元素，如果，就是找最小的元素，如果kn，就是找最大的元素。就是找最大的元素。2.6 线性时间选择线性时间选择20现在学习的是第20页，共31页l利用快速分类思想解决这一问题利用快速分类思想解决这一问题l根据根据PARTITION过程。如果划分元素过程。如果划分元素v确定在确定在A(j)的的位置上，则有位置上，则有j-1

18、个元素小于或等于个元素小于或等于A(j)，且有，且有n-j个元素大于或等于个元素大于或等于A(j)。2.6 线性时间选择线性时间选择21现在学习的是第21页，共31页l假设在一次划分中，划分元素假设在一次划分中，划分元素v处于第处于第j个位置。个位置。如果如果kj，则要找的第，则要找的第k小元素在新数组小元素在新数组Aj1:n中中,而且是而且是Aj1:n的第的第k-j小元素。小元素。2.6 线性时间选择线性时间选择22现在学习的是第22页，共31页采用划分的选择算法采用划分的选择算法l 若若k=j，则，则A(j)即是第即是第k小元素；否则，小元素；否则，l 若若kj，则第，则第k小元素为小元素

19、为A(j+1:n)中第中第k-j小元素。小元素。A(1)A(2)A(j-1)A(j)A(j+1)A(n-1)A(n)V划分元素kj时，第时，第k小元素小元素所在的集合所在的集合K=j时，第时，第k小元素小元素就是划分元素就是划分元素2.6 线性时间选择线性时间选择23现在学习的是第23页，共31页templateType RandomizedSelect(Type a ,int p,int r,int k) if(p = r) return a p ; int i = RandomizedPartition( a, p, r ); j= i - p + 1; if ( k 3，调用，调用Ran

20、domizedSelect( a, 4, 9, 2)第二次调用第二次调用Randomizedpartition(a, 4, 9)=6得到得到 2 1 4 8 7 9 12 10 1556，调用，调用RandomizedSelect( a, 4, 6, 2)第二次调用第二次调用Randomizedpartition(a, 4, 6)=5得到得到 2 1 4 7 8 9 12 10 152.6 线性时间选择线性时间选择25现在学习的是第25页，共31页算法复杂度：l在最坏情况下，总是在最大元素处划分，算法RandomizedSelect需要O(n2)计算时间。l但可以证明，算法Randomized

21、Select可以在O(n)平均时间内找出n个输入元素中的第k小元素。2.6 线性时间选择线性时间选择26现在学习的是第26页，共31页如果能在线性时间内找到一个划分基准，使得按这个基准所划分出的2个子数组的长度都至少为原数组长度的倍(01是某个正常数)，那么就可以在最在最坏情况下坏情况下用O(n)时间完成选择任务。例如，若=9/10，算法递归调用所产生的子数组的长度至少缩短1/10。所以，在最坏情况下，算法所需的计算时间T(n)满足递归式T(n)T(9n/10)+O(n) 。由此可得T(n)=O(n)。2.6 线性时间选择线性时间选择27现在学习的是第27页，共31页l 将n个输入元素划分成n

22、/5个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共n/5个。l 递归调用selectselect来找出这n/5个元素的中位数。如果n/5是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x。同理，基准x也至少比3(n-5)/10个元素小。而当n75时，3(n-5)/10n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。2.6 线性时间选

23、择线性时间选择28现在学习的是第28页，共31页private static Comparable select (int p, int r, int k) if (r-p5) /用某个简单排序算法对数组ap:r排序; bubbleSort(p,r); return ap+k-1; /将ap+5*i至ap+5*i+4的第3小元素 /与ap+i交换位置; /找中位数的中位数，r-p-4即上面所说的n-5 for ( int i = 0; i=(r-p-4)/5; i+ ) int s=p+5*i, t=s+4; for (int j=0;j3;j+) bubble(s,t-j); MyMath.

24、swap(a, p+i, s+2); Comparable x = select(p, p+(r-p-4)/5, (r-p-4)/10); int i=partition(p,r,x), j=i-p+1; if (k=j) return select(p,i,k); else return select(i+1,r,k-j); 复杂度分析复杂度分析T(n)=O(n)7575)4/3()5/()(21nnnTnTnCCnT上述算法将每一组的大小定为5，并选取75作为是否作递归调用的分界点。这2点保证了T(n)的递归式中2个自变量之和n/5+3n/4=19n/20=n，01。这是使T(n)=O(n)的关键之处。当然，除了5和75之外，还有其他选择。2.6 线性时间选择线性时间选择29现在学习的是第29页，共31页l自学 改进的线性时间选择l作业 教材P37页，2-1530现在学习的是第30页，共31页ExerciseslUsing Figure 2-1 as a model, illustrate the operation of PARTITION on the array A = 13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21. 31现在学习的是第31页，共31页