分治法之選擇問(wèn)題 (1)

《分治法之選擇問(wèn)題 (1)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、1.問(wèn)題描述在n個(gè)元素的表a[1:n]中確定第k小元素，1≤k≤n。2.設(shè)計(jì)思路利用Partition過(guò)程。在第一次劃分后劃分元素v測(cè)定在a[j]的位置上，則有j-1個(gè)元素小于或等于a[j]，且有n-j個(gè)元素大于或等于a[j]。此時(shí)，若k=j，則a[j]即是第k小元素；否則，若kj，則a[1:n]中的第k小元素將出現(xiàn)在a[j+1:n]，是a[j+1:n]中的第k-j小元素。選擇問(wèn)題利用Part

2、ition實(shí)現(xiàn)的選擇算法publicstaticvoidSelect(intn,intk){//在數(shù)組a[1],…,a[n]中找第k小元素s并把它放在位置k，假設(shè)1≤k≤n。//將剩下的元素按如下方式排列，使a[k]=t，對(duì)于1≤m

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

4、縮小的子集的元素?cái)?shù)將至少比上一次劃分的元素?cái)?shù)少1。最壞情況時(shí)間Select的最壞情況時(shí)間是O()Select的平均情況時(shí)間是O(n)最壞情況下的特例：輸入a恰好使對(duì)Partition的第i次調(diào)用選用的劃分元素是第i小元素，而k=n。此時(shí)，（區(qū)間下界）m隨著Partition的每一次調(diào)用而僅增加1，j保持不變。Partition最終需要調(diào)用n次。則n次調(diào)用的時(shí)間總量是：最壞情況時(shí)間是O(n)的選擇算法基本思想：精心挑選劃分元素v方法：二次取中間值目的：使v比一部分元素小比另一部分元素大使用二次取中規(guī)則的選擇算法的說(shuō)

5、明性描述publicstaticintSelect2(inta[],intk,intn){//在集合a中找第k小元素①若n≤r，則采用插入法直接對(duì)a分類并返回第k小元素。②把a(bǔ)分成大小為r的個(gè)子集合，忽略剩余的元素。③設(shè)是上面?zhèn)€子集合的中間值的集合。④⑤用Partition劃分a，v作為劃分元素。⑥假設(shè)v在位置j。⑦casek=j:return(v);k

6、R,k-j,n-j))}Select2的待解決問(wèn)題算法中需要解決的兩個(gè)問(wèn)題1)如何確定子集合的中間值當(dāng)r較小時(shí)，采用InsertionSort(a,i,j)直接對(duì)每組的r個(gè)元素分類，在分類好的序列中，中間元素即為當(dāng)前r個(gè)元素中的中間位置下標(biāo)對(duì)應(yīng)的元素。2)如何保存?zhèn)€子集合的中間值注：各組找到的中間元素值將調(diào)整到數(shù)組a的前部，連續(xù)保存，從而可用遞歸調(diào)用的方式對(duì)這些中間值進(jìn)行排序并找出中間值的中間值。Select2的實(shí)現(xiàn)publicstaticintSel(intm,intp,intk){//返回一個(gè)i，使得i屬于[

7、m,p]，且a[i]是a[m:p]中第k小元素，r是一個(gè)全程變量，其取值為一個(gè)大于1的整數(shù)。inti,j,n,temp;if(p-m+1<=r){InsertionSort(m,p);return(m+k-1);//返回第k小元素的位置}while(true){n=p-m+1;//元素?cái)?shù)for(i=1;i<=n/r;i++)//計(jì)算中間值{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+