|
摘要： 本章所討論的問(wèn)題是在一個(gè)由n個(gè)不同數(shù)值構(gòu)成的集合中選擇第i個(gè)順序統(tǒng)計(jì)量問(wèn)題。主要講的內(nèi)容是如何在線性時(shí)間內(nèi)O(n)時(shí)間內(nèi)在集合S中選擇第i小的元素，最基本的是選擇集合的最大值和最小值。一般情況下選擇的元素是隨機(jī)的，最大值和最小值是特殊情況，書中重點(diǎn)介紹了如何采用分治算法來(lái)實(shí)現(xiàn)選擇第i小的元素，并借助中位數(shù)進(jìn)行優(yōu)化處理，保證最壞運(yùn)行時(shí)間是線性的O(n)。 1、基本概念 順序統(tǒng)計(jì)量：在一個(gè)由n個(gè)元素組成的集合中，第i個(gè)順序統(tǒng)計(jì)量是值該集合中第i小的元素。例如最小值是第1個(gè)順序統(tǒng)計(jì)量，最大值是第n個(gè)順序統(tǒng)計(jì)量。 中位數(shù)：一般來(lái)說(shuō)，中位數(shù)是指它所在集合的“中間元素”，當(dāng)n為奇數(shù)時(shí)，中位數(shù)是唯一的，出現(xiàn)位置為n/2；當(dāng)n為偶數(shù)時(shí)候，存在兩個(gè)中位數(shù)，位置分別為n/2（上中位數(shù)）和n/2+1（下中位數(shù)）。 2、選擇問(wèn)題描述 輸入：一個(gè)包含n個(gè)（不同的）數(shù)的集合A和一個(gè)數(shù)i，1≤i≤n。 輸出：元素x∈A，它恰大于A中其他的i-1個(gè)元素。 最直接的辦法就是采用一種排序算法先對(duì)集合A進(jìn)行排序，然后輸出第i個(gè)元素即可?？梢圆捎们懊嬷v到的歸并排序、堆排序和快速排序，運(yùn)行時(shí)間為O(nlgn)。接下來(lái)書中由淺入深的講如何在線性時(shí)間內(nèi)解決這個(gè)問(wèn)題。 3、最大值和最小值 要在集合中選擇最大值和最小值，可以通過(guò)兩兩元素比較，并記錄最大值和最小值，n元素的集合需要比較n-1次，這樣運(yùn)行時(shí)間為O(n)。舉個(gè)例子來(lái)說(shuō)明，現(xiàn)在要求和集合A={32,12,23,67,45,78}的最大值，開始假設(shè)第一個(gè)元素最大，即max=1，然后從第二個(gè)元素開始向后比較，記錄最大值的位置。執(zhí)行過(guò)程如下圖所示：
書中給出的求最小值的偽代碼如下： 1 MINMUN(A) 2 min = A[1] 3 for i=1 to length(A) 4 do if min > A[i] 5 then min = A[i] 6 return min 問(wèn)題： 方法1：按照上面講到的方法，分別獨(dú)立的找出集合的最大值和最小值，各用n-1次比較，共有2n-2次比較。 方法2：可否將最大值和最小值結(jié)合在一起尋找呢？答案是可以的，在兩兩比較過(guò)程中同時(shí)記錄最大值和最小值，這樣最大需要3n/2次比較。現(xiàn)在的做法不是將每一個(gè) 輸入元素與當(dāng)前的最大值和最小值進(jìn)行比較，而是成對(duì)的處理元素，先將一對(duì)輸入元素進(jìn)行比較，然后把較大者與當(dāng)前最大值比較，較小者與當(dāng)前最小者比較，因此每?jī)蓚€(gè)元素需要3次比較。初始設(shè)置最大值和最小值方法：如何n為奇數(shù)，就將最大值和最小值都設(shè)置為第一個(gè)元素的值，然后成對(duì)的處理后續(xù)的元素。如果n為偶數(shù)，那么先比較前面兩個(gè)元素的值，較大的設(shè)置為最大值，較小的設(shè)置為最小值，然后成對(duì)處理后續(xù)的元素。這樣做的目的保證能夠成對(duì)的處理后續(xù)的元素。舉個(gè)例子說(shuō)明這個(gè)過(guò)程，假設(shè)現(xiàn)在要找出集合A={32,23,12,67,45,78,10,39,9,58}最大值和最小值，執(zhí)行過(guò)程如下： 從圖中可以看出方法2要比方法一要好，減少了元素之間的比較次數(shù)。現(xiàn)在用C語(yǔ)言實(shí)現(xiàn)方法2，程序如下： 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 //return max and min value by pointer 5 void get_max_min(int *datas,int length,int* ptrmax,int* ptrmin) 6 { 7 int i,maxtmp,mintmp; 8 //judge length is even or odd 9 if(length %2 == 0) 10 { 11 if(datas[0] > datas[1]) 12 { 13 *ptrmax = datas[0]; 14 *ptrmin = datas[1]; 15 } 16 else 17 { 18 *ptrmax = datas[1]; 19 *ptrmin = datas[0]; 20 } 21 } 22 else 23 { 24 *ptrmax = datas[0]; 25 *ptrmin = datas[0]; 26 } 27 for(i=2;i<length;i+=2) 28 { 29 if(datas[i] > datas[i+1]) 30 { 31 maxtmp = datas[i]; 32 mintmp = datas[i+1]; 33 } 34 else 35 { 36 maxtmp = datas[i+1]; 37 mintmp = datas[i]; 38 } 39 if(*ptrmax < maxtmp) 40 *ptrmax = maxtmp; 41 if(*ptrmin > mintmp) 42 *ptrmin = mintmp; 43 } 44 } 45 46 int main() 47 { 48 int max,min; 49 int i; 50 int datas[10] = {23,12,34,26,78,45,87,15,60,19}; 51 get_max_min(datas,10,&max,&min); 52 printf("All elements in set are:\n"); 53 for(i=0;i<10;++i) 54 printf("%d ",datas[i]); 55 putchar('\n'); 56 printf("max=%d\tmin=%d\n",max,min); 57 exit(0); 58 }  程序測(cè)試結(jié)果如下：
（2）如何找出找出n個(gè)元素中的第2小元素。 解答：類似與上面的同時(shí)找出最大值和最小值的方法2，變成同時(shí)找最小值和第2小元素值。先初始化最小值和第2小的值，然后成對(duì)比較后續(xù)的元素，找出較小的元素與當(dāng)前最小值和第二小值進(jìn)行比較，在三者中找出最小值和第二小值。 4、以期望線性時(shí)間做選擇 一般的選擇問(wèn)題似乎要比選擇最大值和最小值要難，但是這兩種問(wèn)題的運(yùn)行時(shí)間是相同的，都是θ(n)。書中介紹了采用分治算法解決一般的選擇問(wèn)題，其過(guò)程與快速排序過(guò)程中劃分類似。每次劃分集合可以確定一個(gè)元素的最終位置，根據(jù)這個(gè)位置可以判斷是否是我們要求的第i小的元素。如果不是，那么我們只關(guān)心劃分產(chǎn)出兩個(gè)子部分中的其中一個(gè)，根據(jù)i的值來(lái)判斷是前一個(gè)還是后一個(gè)，然后接著對(duì)子數(shù)組進(jìn)行劃分，重復(fù)此過(guò)程，直到找到第i個(gè)小的元素。劃分可以采用隨機(jī)劃分，這樣能夠保證期望時(shí)間是θ(n)（假設(shè)所有元素是不同的）。 給個(gè)例子說(shuō)明此過(guò)程，假設(shè)現(xiàn)有集合A={32,23,12,67,45,78,10,39,9,58}，要求其第5小的元素，假設(shè)在劃分過(guò)程中以總是以最后一個(gè)元素為主元素進(jìn)行劃分。執(zhí)行過(guò)程如下圖所示：
書中給出了返回A[p...r]中的第i小元素的偽代碼：  1 RANDOMIZED_SELECT(A,p,r,i) 2 if p==r 3 then return A[p] 4 q = RANDOMIZED_PARTITION(A,p,r) 5 k = q-p+1; 6 if i==k 7 then return A[q] 8 else if i<k 9 then return RANDOMIZED_SELECT(A,p,q-1,i) 10 else 11 return RANDOMIZED_SELECT(A,p,q-1,i-k) RANDOMIZED_SELECT通過(guò)對(duì)輸入數(shù)組的遞歸劃分來(lái)找出所求元素，該算法要保證對(duì)數(shù)組的劃分是個(gè)好劃分才更加高效。RANDOMIZED_SELECT的最壞情況運(yùn)行時(shí)間為θ(n^2)，即使是選擇最小元素也是如此。因?yàn)樵诿看蝿澐诌^(guò)程中，導(dǎo)致劃分后兩邊不對(duì)稱，總好是按照剩下元素中最大的劃分進(jìn)行。為了更好的選擇過(guò)程，我采用C語(yǔ)言實(shí)現(xiàn)求集合A={32,23,12,67,45,78,10,39,9,58}的第i小的元素，完成程序如下： 1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <time.h> 4 5 size_t randomized_partition(int* datas,size_t beg,size_t last); 6 void swap(int* a,int *b); 7 int randomized_select_one(int* datas,int beg,int last,int i); 8 int randomized_select_two(int* datas,int length,int i); 9 10 int main() 11 { 12 int datas[10]={32,23,12,67,45,78,10,39,9,58}; 13 int i,ret; 14 printf("The array is: \n"); 15 for(i=0;i<10;++i) 16 printf("%d ",datas[i]); 17 printf("\n"); 18 for(i=1;i<=10;++i) 19 { 20 //ret=randomized_select_one(datas,0,9,i); 21 ret=randomized_select_two(datas,10,i); 22 printf("The %dth least number is: %d \n",i,datas[i-1]); 23 } 24 exit(0); 25 } 26 /* 27 參數(shù)介紹：datas是待劃分的數(shù)組，數(shù)組下標(biāo)從0開始。 28 beg代表開始位置，last代表結(jié)束位置、封閉區(qū)間[beg,last] 29 */ 30 size_t randomized_partition(int* datas,size_t beg,size_t last) 31 { 32 int len,i,j,index; 33 len = last-beg+1; 34 //隨機(jī)獲取一個(gè)主元 35 srand(time(NULL)); 36 index = beg + rand()%len; 37 //將主元交換到末尾 38 swap(datas+index,datas+last); 39 //從第一個(gè)元素開始向后查找主元的位置 40 i=beg; 41 for(j=beg;j<last;j++) 42 { 43 if(datas[j] < datas[last]) 44 { 45 swap(datas+i,datas+j); 46 i++; 47 } 48 } 49 //最終確定主元的位置 50 swap(datas+i,datas+last); 51 return i; 52 } 53 /* 54 參數(shù)介紹：datas是待查找的數(shù)組，數(shù)組下標(biāo)從0開始。 55 beg代表開始位置，last代表結(jié)束位置、封閉區(qū)間[beg,last] 56 i表示要要查找第i小元素，i從1開始 57 */ 58 int randomized_select_one(int* datas,int beg,int last,int i) 59 { 60 int pivot,k; 61 if(beg == last) 62 return datas[beg]; 63 pivot = randomized_partition(datas,beg,last); 64 k = pivot-beg+1; 65 if(k == i) 66 return datas[pivot]; 67 else if(k < i) 68 randomized_select_one(datas,pivot+1,last,i-k); 69 else 70 randomized_select_one(datas,beg,pivot-1,i); 71 } 72 /* 73 參數(shù)介紹：datas是待查找的數(shù)組，數(shù)組下標(biāo)從0開始。 74 length表示數(shù)組的長(zhǎng)度，數(shù)組下標(biāo)范圍[0,length-1] 75 i表示要要查找第i小元素，i從1開始 76 */ 77 int randomized_select_two(int* datas,int length,int i) 78 { 79 int pivot,k,j; 80 if(length == 1) 81 return datas[length-1]; 82 pivot = randomized_partition(datas,0,length-1); 83 //確定是主元是第k小 84 k = pivot+1; 85 if(k == i) 86 return datas[pivot]; 87 else if(k < i) 88 randomized_select_two(datas+k,length-k,i-k); 89 else 90 randomized_select_two(datas,pivot,i); 91 } 92 93 void swap(int* a,int *b) 94 { 95 int temp = *a; 96 *a = *b; 97 *b = temp; 98 } 程序測(cè)試結(jié)果如下所示：
5、最壞情況線性時(shí)間的選擇 SELECT算法的思想是要保證對(duì)數(shù)組的劃分是個(gè)好的劃分，對(duì)PARTITION過(guò)程進(jìn)行了修改?，F(xiàn)在通過(guò)SELECT算法來(lái)確定n個(gè)元素的輸入數(shù)組中的第i小的元素，具體操作步驟如下： （1）將輸入數(shù)組的n個(gè)元素劃分為n/5（上取整）組，每組5個(gè)元素，且至多只有一個(gè)組有剩下的n%5個(gè)元素組成。（為何是5，而不是其他數(shù)，有點(diǎn)不明白。） （2）尋找每個(gè)組織中中位數(shù)。首先對(duì)每組中的元素（至多為5個(gè)）進(jìn)行插入排序，然后從排序后的序列中選擇出中位數(shù)。 （3）對(duì)第2步中找出的n/5（上取整）個(gè)中位數(shù)，遞歸調(diào)用SELECT以找出其中位數(shù)x。（如果是偶數(shù)去下中位數(shù)） （4）調(diào)用PARTITION過(guò)程，按照中位數(shù)x對(duì)輸入數(shù)組進(jìn)行劃分。確定中位數(shù)x的位置k。 （5）如果i=k，則返回x。否則，如果i<k，則在地區(qū)間遞歸調(diào)用SELECT以找出第i小的元素，若干i>k，則在高區(qū)找第(i-k)個(gè)最小元素。 SELECT算法通過(guò)中位數(shù)進(jìn)行劃分，可以保證每次劃分是對(duì)稱的，這樣就能保證最壞情況下運(yùn)行時(shí)間為θ(n)。舉個(gè)例子說(shuō)明此過(guò)程，求集合A={32,23,12,67,45,78,10,39,9,58,125,84}的第5小的元素，操作過(guò)程如下圖所示： 現(xiàn)在采用C語(yǔ)言實(shí)現(xiàn)上面的例子，完整程序如下所示： 1 #include <stdio.h> 2 #include <stdlib.h> 3 4 int partition(int* datas,int beg,int last,int mid); 5 int select(int* datas,int length,int i); 6 void swap(int* a,int *b); 7 8 int main() 9 { 10 int datas[12]={32,23,12,67,45,78,10,39,9,58,125,84}; 11 int i,ret; 12 printf("The array is: \n"); 13 for(i=0;i<12;++i) 14 printf("%d ",datas[i]); 15 printf("\n"); 16 for(i=1;i<=12;++i) 17 { 18 ret=select(datas,12,i); 19 printf("The %dth least number is: %d \n",i,datas[i-1]); 20 } 21 exit(0); 22 } 23 24 int partition(int* datas,int beg,int last,int mid) 25 { 26 int i,j; 27 swap(datas+mid,datas+last); 28 i=beg; 29 for(j=beg;j<last;j++) 30 { 31 if(datas[j] < datas[last]) 32 { 33 swap(datas+i,datas+j); 34 i++; 35 } 36 } 37 swap(datas+i,datas+last); 38 return i; 39 } 40 41 int select(int* datas,int length,int i) 42 { 43 int groups,pivot; 44 int j,k,t,q,beg,glen; 45 int mid; 46 int temp,index; 47 int *pmid; 48 if(length == 1) 49 return datas[length-1]; 50 if(length % 5 == 0) 51 groups = length/5; 52 else 53 groups = length/5 +1; 54 pmid = (int*)malloc(sizeof(int)*groups); 55 index = 0; 56 for(j=0;j<groups;j++) 57 { 58 beg = j*5; 59 glen = beg+5; 60 for(t=beg+1;t<glen && t<length;t++) 61 { 62 temp = datas[t]; 63 for(q=t-1;q>=beg && datas[q] > datas[q+1];q--) 64 swap(datas+q,datas+q+1); 65 swap(datas+q+1,&temp); 66 } 67 glen = glen < length ? glen : length; 68 pmid[index++] = beg+(glen-beg)/2; 69 } 70 for(t=1;t<groups;t++) 71 { 72 temp = pmid[t]; 73 for(q=t-1;q>=0 && datas[pmid[q]] > datas[pmid[q+1]];q--) 74 swap(pmid+q,pmid+q+1); 75 swap(pmid+q+1,&temp); 76 } 77 //printf("mid indx = %d,mid value=%d\n",pmid[groups/2],datas[pmid[groups/2]]); 78 mid = pmid[groups/2]; 79 pivot = partition(datas,0,length-1,mid); 80 //printf("pivot=%d,value=%d\n",pivot,datas[pivot]); 81 k = pivot+1; 82 if(k == i) 83 return datas[pivot]; 84 else if(k < i) 85 return select(datas+k,length-k,i-k); 86 else 87 return select(datas,pivot,i); 88 89 } 90 91 void swap(int* a,int *b) 92 { 93 int temp = *a; 94 *a = *b; 95 *b = temp; 96 }  程序測(cè)試結(jié)果如下所示：
總結(jié) 本章中的選擇算法之所以具有線性運(yùn)行時(shí)間，是因?yàn)檫@些算法沒有進(jìn)行排序，線性時(shí)間的行為并不是因?yàn)閷?duì)輸入做假設(shè)所得到的結(jié)果。 |
|
|
來(lái)自： 看風(fēng)景D人 > 《算法導(dǎo)論》
