0006算法筆記-【分治法】線性時(shí)間選擇

線性時(shí)間選擇問(wèn)題：給定線性序集中n個(gè)元素和一個(gè)整數(shù)k,1<k<n要求找出這n個(gè)元素中第k小的元素，（這里給定的線性集是無(wú)序的）。1、隨機(jī)劃分線性選擇線性時(shí)間選擇隨機(jī)劃分法可以模仿隨機(jī)化快速排序算法設(shè)計(jì)。基本思想是對(duì)輸入數(shù)組進(jìn)行遞歸劃分，與快速排序不同的是，它只對(duì)劃分出的子數(shù)組之一進(jìn)行遞歸處理程序清單如下：1.2.3.1.2.3.4.5.6.//2d9-1隨機(jī)劃分線性時(shí)間選擇#include"stdafx.h"#include<iostream>#include<ctime>usingnamespacestd;7-inta[]={5,7,3,4,8,6,9,1,2};&template<classType〉voidSwap(Type&x,Type&y);11.12-inlineintRandom(intx,inty);13.template<classType>intPartition(Typea[],intp,intr);16.template<classType>intRandomizedPartition(Typea[],intp,intr);19.template<classType>21-TypeRandomizedSelect(Typea[],intp,intr,intk);22.23-intmain(){for(inti=0;i<9;i++){{26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.cout<<a[i]<<}cout<<endl;cout<<RandomizedSelect(a,0,8,3)<<endl;}template<classType〉voidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}inlineintRandom(intx,inty){srand((unsigned)time(0));intran_num=rand()%(y-x)+x;returnran_num;}template<classType〉intPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];while(true){while(a[++i]<x&&i<r);while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}template<classType>70.71.72.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.}intRandomizedPartition(Typea[],intp,intr){inti=Random(p,r);Swap(a[i],a[p]);returnPartition(a,p,r);}template<classType〉TypeRandomizedSelect(Typea[],intp,intr,intk){if(p==r){returna[p];}inti=RandomizedPartition(a,p,r);intj=i-p+1;if(k<=j){returnRandomizedSelect(a,p,i,k);}else{//由于已知道子數(shù)組a[p:i]中的元素均小于要找的第k小元素//因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。returnRandomizedSelect(a,i+1,r,k-j);}程序解釋：利用隨機(jī)函數(shù)產(chǎn)生劃分基準(zhǔn)，將數(shù)組a[p:r]劃分成兩個(gè)子數(shù)組a[p:i]和a[i+1:r]，使a[p:i沖的每個(gè)元素都不大于a[i+1:r沖的每個(gè)元素。接著"j=i-p+1"計(jì)算a[p:i]中元素個(gè)數(shù)j?如果k<=j,則a[p:r沖第k小元素在子數(shù)組a[p:i]中，如果k>j，則第k小元素在子數(shù)組a[i+1:r]中。注意：由于已知道子數(shù)組a[p:i沖的元素均小于要找的第k小元素,因此，要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。在最壞的情況下，例如：總是找到最小元素時(shí)，總是在最大元素處劃分，這是時(shí)間復(fù)雜度為O(n"2)。但平均時(shí)間復(fù)雜度與n呈線性關(guān)

系，為0(n)(數(shù)學(xué)證明過(guò)程略過(guò)，可參考王云鵬論文《線性時(shí)間選擇算法時(shí)間復(fù)雜度深入研究》)。2、利用中位數(shù)線性時(shí)間選擇中位數(shù)：是指將數(shù)據(jù)按大小順序排列起來(lái)，形成一個(gè)數(shù)列，居于數(shù)列中間位置的那個(gè)數(shù)據(jù)。算法思路：如果能在線性時(shí)間內(nèi)找到一個(gè)劃分基準(zhǔn)使得按這個(gè)基準(zhǔn)所劃分出的2個(gè)子數(shù)組的長(zhǎng)度都至少為原數(shù)組長(zhǎng)度的E倍(0<￡<1)，那么就可以在最壞情況下用0(n)時(shí)間完成選擇任務(wù)。例如，當(dāng)￡=9/10,算法遞歸調(diào)用所產(chǎn)生的子數(shù)組的長(zhǎng)度至少縮短1/10。所以，在最壞情況下，算法所需的計(jì)算時(shí)間T(n)滿足遞推式T(n)<=T(9n/10)+O(n)。由此可得T(n)=O(n)o實(shí)現(xiàn)步驟：將所有的數(shù)n個(gè)以每5個(gè)劃分為一組共「門(mén)組，將不足5個(gè)的那組忽略，然后用任意一種排序算法，因?yàn)橹粚?duì)5個(gè)數(shù)進(jìn)行排序，所以任取一種排序法就可以了。將每組中的元素排好序再分別取每組的中位數(shù)，得到門(mén)5I個(gè)中位數(shù)。取這門(mén)三|個(gè)中位數(shù)的中位數(shù)，如果|是偶數(shù)，就找它的2個(gè)中位數(shù)中較大的一個(gè)作為劃分基準(zhǔn)。6.6.將全部的數(shù)劃分為兩個(gè)部分，小于基準(zhǔn)的在左邊，大于等于基準(zhǔn)的放右邊。在這種情況下找出的基準(zhǔn)x至少比.J［個(gè)元素大。因?yàn)樵诿恳唤M中有2個(gè)元素小于本組的中位數(shù)，有屮巧-屮(1/2)吆珂計(jì)5-i」個(gè)小于基準(zhǔn)，中位數(shù)處于l./2*Ln/5-l_［，即「n/5］個(gè)中位數(shù)中又有2'i\個(gè)小于基準(zhǔn)X。因此至少有也/5-1」+附-5)/m」h(W-5_plO)個(gè)元素小于基準(zhǔn)X。同理基準(zhǔn)X也至少比.|個(gè)元素小。而當(dāng)n>75時(shí).小.—|>n/4所以按此基準(zhǔn)劃分所得的2個(gè)子數(shù)組的長(zhǎng)度都至少縮短1/4。程序清單如下:[cpp][cpp]viewplaincopy1.//2d9-2中位數(shù)線性時(shí)間選擇2.#include"stdafx.h"3.#include<ctime>4.#include<iostream>5.usingnamespacestd;7.&9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.template<classType〉voidSwap(Type&x,Type&y);inlineintRandom(intx,inty);template<classType〉voidBubbleSort(Typea[],intp,intr);template<classType>intPartition(Typea[],intp,intr,Typex);template<classType>TypeSelect(Typea[],intp,intr,intk);intmain(){//初始化數(shù)組inta[100];//必須放在循環(huán)體外面srand((unsigned)time(0));for(inti=0;i<100;i++){a[i]=Random(0,500);cout<<”a[”<<i<<”]:”<<a[i]<<””；}cout<<endl;cout<<"第83小元素是"<<Select(a,0,99,83)<<endl;〃重新排序，對(duì)比結(jié)果BubbleSort(a,0,99);for(inti=0;i<100;i++){cout<<"a["<<i<<"]:"<<a[i]<<}cout<<endl;}template<classType>voidSwap(Type&x,Type&y){

51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.Typetemp=x;x=y;y=temp;}inlineintRandom(intx,inty){intran_num=rand()%(y-x)+x;returnran_num;}//冒泡排序template<classType〉voidBubbleSort(Typea[],intp,intr){//記錄一次遍歷中是否有元素的交換boolexchange;for(inti=p;i<=r-1;i++){exchange=false;for(intj=i+1;j<=r;j++){if(a[j]<a[j-1]){Swap(a[j],a[j-1]);exchange=true;}}〃如果這次遍歷沒(méi)有元素的交換，那么排序結(jié)束if(false==exchange){break;}}}template<classType〉intPartition(Typea[],intp,intr,Typex){inti=p-1,j=r+1;while(true){while(a[++i]<x&&i<r);

while(a[--j]>x);if(i>=j){break;}Swap(a[i],a[j]);}returnj;}template<classType〉TypeSelect(Typea[],intp,intr,intk){if(r-p<75){BubbleSort(a,p,r);returna[p+k-1];}//(r-p-4)/5相當(dāng)于n-5for(inti=0;i<=(r-p-4)/5;i++){//將元素每5個(gè)分成一組，分別排序，并將該組中位數(shù)與a[p+i]交換位置//使所有中位數(shù)都排列在數(shù)組最左側(cè)，以便進(jìn)一步查找中位數(shù)的中位數(shù)BubbleSort(a,p+5*i,p+5*i+4);Swap(a[p+5*i+2],a[p+i]);}//找中位數(shù)的中位數(shù)Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x);intj=i-p+1;if(k<=j){returnSelect(a,p,i,k);}else{returnSelect(a,i+1,r,k-j);}}95.96.97.98.99.100.101.102.103.104.105.106.107.108.109.110.111.112.113.114.115.116.117.118.119.120.121.122.123.124.125.126.127.128.129.130.131.132.133.134.運(yùn)行結(jié)果如下:I_I_HIC:\V/!ndows\system32\cmd.exe[D|回|?^i|?51:427a[26]：224a[27]：40a[28]：246aE2?]：172aE30J：26aE31]：469a[32J：la[33J：2HIa[34]：26a[35]：91&[361:169a[3?J：376aE38J：459aE3?]：309aE40J：398a[41J：71a[421:457a[43]：426&[441:153a[45J：475&[461:44VaE47J：499aE48J：76a[49J：240a[501:449a[51]：378&[521:253&[531:222aE54J：l&3aE55J：114aE56J：186a[57J：171a[581:76a[591：441a[60]：299&[611:255&[621:435aEG3J：177aE64J：472a[65J：36a[66J：258a[67]：406&[68X229a[69]：3G?aE70J：laE71J：274aE72J：388aE73J：290a[74J：83a[75]：422a[76]：62a[77]：56a[78J：465aE79J：l?7aE80J：492aE81J：118a[821：195a[83]：362&[841:151a[85]：24&[861:52aE87J：51a[881：494aE89J：327a[?0J：17a[?l]：339a[92]：387a[93]：416a[94]：lG?aE?5J：431aE96J：108aE97J：289a[98J：53a[99J：193第83小元素是422a[0]：17atl]：2a[2]：la[3]：4a[4J：la[5J：24aE6J：26aE7J：26aE8J：36a[93：40a[101:51atll]：52a[12]：53a[13]：56aE14J：G0aE15J：G2aL16J：52a[17J：71a[181：76all9]：76a[20]：83a[21J：91151173195240290365388426457499a[28J：153a[36J：175a[44J：197a[52J：246a[60J：299a[68J：367aC76J：398a[84J：427a[92J：459a[29J