分治法之选择问题 (1)

《分治法之选择问题 (1)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.问题描述在n个元素的表a[1:n]中确定第k小元素，1≤k≤n。2.设计思路利用Partition过程。在第一次划分后划分元素v测定在a[j]的位置上，则有j-1个元素小于或等于a[j]，且有n-j个元素大于或等于a[j]。此时，若k=j，则a[j]即是第k小元素；否则，若kj，则a[1:n]中的第k小元素将出现在a[j+1:n]，是a[j+1:n]中的第k-j小元素。选择问题利用Part

2、ition实现的选择算法publicstaticvoidSelect(intn,intk){//在数组a[1],…,a[n]中找第k小元素s并把它放在位置k，假设1≤k≤n。//将剩下的元素按如下方式排列，使a[k]=t，对于1≤m

3、返回j，它使得a[j]是第j小的值if(k

4、缩小的子集的元素数将至少比上一次划分的元素数少1。最坏情况时间Select的最坏情况时间是O()Select的平均情况时间是O(n)最坏情况下的特例：输入a恰好使对Partition的第i次调用选用的划分元素是第i小元素，而k=n。此时，（区间下界）m随着Partition的每一次调用而仅增加1，j保持不变。Partition最终需要调用n次。则n次调用的时间总量是：最坏情况时间是O(n)的选择算法基本思想：精心挑选划分元素v方法：二次取中间值目的：使v比一部分元素小比另一部分元素大使用二次取中规则的选择算法的说

5、明性描述publicstaticintSelect2(inta[],intk,intn){//在集合a中找第k小元素①若n≤r，则采用插入法直接对a分类并返回第k小元素。②把a分成大小为r的个子集合，忽略剩余的元素。③设是上面个子集合的中间值的集合。④⑤用Partition划分a，v作为划分元素。⑥假设v在位置j。⑦casek=j:return(v);k

6、R,k-j,n-j))}Select2的待解决问题算法中需要解决的两个问题1)如何确定子集合的中间值当r较小时，采用InsertionSort(a,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为当前r个元素中的中间位置下标对应的元素。2)如何保存个子集合的中间值注：各组找到的中间元素值将调整到数组a的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。Select2的实现publicstaticintSel(intm,intp,intk){//返回一个i，使得i属于[

7、m,p]，且a[i]是a[m:p]中第k小元素，r是一个全程变量，其取值为一个大于1的整数。inti,j,n,temp;if(p-m+1<=r){InsertionSort(m,p);return(m+k-1);//返回第k小元素的位置}while(true){n=p-m+1;//元素数for(i=1;i<=n/r;i++)//计算中间值{InsertionSort(m+(i-1)*r,m+i*r-1);//将中间值收集到a[m:p]的前部temp=a[m+i-1];a[m+i-1]=a[m+(i-1)*r+r/

8、2-1];a[m+(i-1)*r+r/2-1]=temp;}j=Sel(m,m+n/r-1,((n/r)+1)/2);//二次取中求mmtemp=a[m];a[m]=a[j];a[j]=temp;//交换a[m]与a[j]j=Partition(m,p);if((j-m+1)==k)return(j);elseif(j-m+1>k)p=j-1;else{k=k-(j-m+