幾種查找數(shù)組的前K個(gè)最小值的算法

幾種查找數(shù)組的前K個(gè)最小值的算法好久沒(méi)有寫(xiě)博客了，這一段時(shí)間主要在準(zhǔn)備為將來(lái)找工作復(fù)習(xí)，今天我就總結(jié)一下關(guān)于如何查找數(shù)組的前K個(gè)最小值實(shí)現(xiàn)方法，查找前K個(gè)最小值實(shí)現(xiàn)方法很多，主要的思想包括如下的幾種：1、對(duì)數(shù)組進(jìn)行排序，然后前K個(gè)元素就是需要查找的元素，排序的方法可以采用快速排序，但是我們知道在快速排序中如果已經(jīng)是有序的數(shù)組，采用快速排序的時(shí)間復(fù)雜度是O(N"2),為了解決這種問(wèn)題，通常選擇隨機(jī)選擇一個(gè)數(shù)組值pivot作為基準(zhǔn)，將數(shù)組分為S1=;pivot，這樣就能避免快速排序中存在的問(wèn)題，或者采用隨機(jī)選擇三個(gè)元素，然后取中間值作為基準(zhǔn)就能避免快速算法的最差時(shí)間復(fù)雜度，這種方法的前K個(gè)數(shù)字是有序的。2、既然是選擇前K個(gè)對(duì)象，那么就沒(méi)必要對(duì)所有的對(duì)象進(jìn)行排序，可以采用快速選擇的思想獲得前K個(gè)對(duì)象，比如首先采用快速排序的集合劃分方法劃分集合：S1，pivot，S2，然后比較K是否小于S1的個(gè)數(shù)，如何小于，則直接對(duì)S1進(jìn)行快速排序，如果K的個(gè)數(shù)超過(guò)S1,那么對(duì)S2進(jìn)行快速排序，排序完成之后，取數(shù)組的前K個(gè)元素就是數(shù)組的前K個(gè)最小值。這種實(shí)現(xiàn)方法肯定比第一種的全快速排序要更快速。3、將數(shù)組轉(zhuǎn)換為最小堆的情況，根據(jù)最小堆的特性，第一個(gè)元素肯定就是數(shù)組中的最小值，這時(shí)候我們可以將元素保存起來(lái)，然后將最后一個(gè)元素提升到第一個(gè)元素，重新構(gòu)建最小堆，這樣進(jìn)行K次的最小堆創(chuàng)建，就找到了前K個(gè)最小值，這是運(yùn)用了最小堆的特性，實(shí)質(zhì)上是最小堆的刪除實(shí)現(xiàn)方法。這種算法的好處是實(shí)現(xiàn)了數(shù)組的原地排序，并不需要額外的內(nèi)存空間。4、接下來(lái)的這種思想有點(diǎn)類(lèi)似桶排序，首先給定一個(gè)K個(gè)大小的數(shù)組b，然后復(fù)制數(shù)組a中的前K個(gè)數(shù)到數(shù)組b中，將這K個(gè)數(shù)當(dāng)成數(shù)組a的前K個(gè)最小值，對(duì)數(shù)組b創(chuàng)建最大堆，這時(shí)候再次比較數(shù)組a中的其他元素，如果其他元素小于數(shù)組b的最大值（堆頂），則將堆頂?shù)闹颠M(jìn)行替換，并重新創(chuàng)建最大堆。這樣遍歷一次數(shù)組就找到了前K個(gè)最小元素。這種方法運(yùn)用了額外的內(nèi)存空間，特別當(dāng)選擇的K值比較大時(shí)，這種方法有待于權(quán)衡一下。這種方法對(duì)于海量數(shù)據(jù)來(lái)說(shuō)是有較好的作用，對(duì)于海量數(shù)據(jù)不能全部存放在內(nèi)存中，這時(shí)候創(chuàng)建一個(gè)較小的數(shù)組空間，然后創(chuàng)建最大堆，從硬盤(pán)中讀取其他的數(shù)據(jù)，進(jìn)而實(shí)現(xiàn)前K個(gè)數(shù)據(jù)的查找。這是比較傳統(tǒng)的幾種方法，當(dāng)然還存在其他的選擇方式，我在這邊就不闡述了，從上面幾種方法的可知，查找方法都充分運(yùn)用了運(yùn)用了數(shù)據(jù)結(jié)構(gòu)和算法的特性。因此數(shù)據(jù)結(jié)構(gòu)的靈活運(yùn)用對(duì)算法的實(shí)現(xiàn)有很多的好處。下面是我的實(shí)現(xiàn)代碼，數(shù)組中前K個(gè)元素我通過(guò)打印的方式實(shí)現(xiàn)，并沒(méi)有保存到新的數(shù)組中：#include;#include;#include;#include;#include;#defineLEN500000#defineK100/*堆的性質(zhì)*/#defineLEFTSON(i)(2*(i)+1)#defineRIGHTSON(i)(2*((i)+1))#definePARENT(i)(((i)-1)/2)voidswap(int*a,int*b){assert(a!=NULL&&b!=NULL);if(a!=b){*a=*a八*b;*b=*a八*b;*a=*a八*b;}}intpartition(int*a,intleft,intright){intpivot=a[right];inti=left;intj=left-1;assert(a!=NULL);for(i=left;i;k)quickselect(a,left,i-1,k);}}voidQuickSelect(int*a,intsize,intk){assert(a!=NULL);quickselect(a,0,size-1,k);}/*最大堆*/voidmax_heapify(int*a,intleft,intright){inttmp=0;intchild=left;intparent=left;assert(a!=NULL);for(tmp=a[parent];LEFTSON(parent);=0;--i)max_heapify(a,i,size-1);}/*最小堆的實(shí)現(xiàn)*/voidmin_heapify(int*a,intleft,intright){intchild=0;inttmp=0;intparent=left;assert(a!=NULL);for(tmp=a[parent];LEFTSON(parent);a[child+1])child++;if(a[child];=0;--i)min_heapify(a,i,size-1);}/*采用快速排序查找*/voidfind_Kmin_num_1(int*a,intsize,intk){inti=0;assert(a!=NULL);QuickSort(a,size);#if0for(i=0;i<k;++i)printf("%d\t",a[i]);printf("\n");#endif}/*采用快速選擇實(shí)現(xiàn)*/voidfind_Kmin_num_2(int*a,intsize,intk){inti=0;assert(a!=NULL);QuickSelect(a,size,k);#if0for(i=0;i<k;++i)printf("%d\t",a[i]);printf("\n");#endif}/*采用最大堆實(shí)現(xiàn)*/voidfind_Kmin_num_3(int*a,intsize,intk){inti=0;int*b=malloc(sizeof(int)*k);assert(a!=NULL&&b!=NULL);for(i=0;i<k;++i)b[i]=a[i];build_maxheap(b,k);for(;i<size;++i){if(a[i]<b[0]){b[0]=a[i];//build_maxheap(b,k);max_heapify(b,0,k-1);}#if0for(i=0;i<k;++i)printf("%d\t",b[i]);printf("\n");#endif}/*采用最小堆刪除元素的方式實(shí)現(xiàn)*/voidfind_Kmin_num_4(int*a,intsize,intk){inti=0;assert(a!=NULL);build_minheap(a,size-1);for(i=0;i<k;++i){//printf("%d\t",a[0]);/*刪除a[0],釋放a[size-1-i]*/a[0]=a[size-1-i];min_heapify(a,0,size-2-i);}//printf("\n");}intmain(){inta[LEN];intb[LEN];intc[LEN];intd[LEN];inti=0,j=0;clock_t_start;doubletimes=0;srand((int)time(NULL));for(i=0;i<LEN;++i){a[i]=rand()%(LEN);b[i]=a[i];c[i]=a[i];d[i]=a[i];//printf("%d\t",a[i]);}//printf("\n");_start=clock();find_Kmin_num_1(a,LEN,K);

times=(double)(clock()times=(double)(clock()-printf("快速排序的查找需要:%f\n",times);_start=clock();find_Kmin_num_2(b,LEN,K);times=(double)(clock()-_start)/CLOCKS_PER_SEC;printf("快速選擇的查找需要:%f\n",times);_start=clock();find_Kmin_num_3(c,LEN,K);times=(double)(clock()-_start)/CLOCKS_PER_SEC;printf("最大堆的查找需要:%f\n",times);_start=clock();find_Kmin_num_4(d,LEN,K);times=(double)(clock()-_start)/CLOCKS_PER_SEC;printf("最小堆的查找需要:%f\n",times);return0;}檢測(cè)算法的性能：[gong@Gong-Computerinterview]$gcc-gminKnum.c-ominKnum[gong@Gong-Computerinterview]$./minKnum快速排序的查找需要:0?130000快速選擇的查找需要:0?020000最大堆的查找需要:0.000000最小堆的查找需要:0?010000從結(jié)果可知，快速排序的算法效果最差，而最大堆的效果最好，最小堆的效果其次，但是最大堆運(yùn)用了額外的內(nèi)存空間。因此在內(nèi)存空間限制的情況下，考慮最小堆是比較合適的。但是最大堆的思想確實(shí)很精妙的，運(yùn)用了類(lèi)似桶排序的性質(zhì)。為了說(shuō)明算法能否實(shí)現(xiàn)前K個(gè)最小值的查找，改變數(shù)組大小為50，并打印各個(gè)方法完成的情況，查找前10個(gè)數(shù)據(jù)，實(shí)驗(yàn)結(jié)果如下所示：[gong@Gong-Computerinterview]$./minKnum15381