好久沒有寫博客了，這一段時間主要在準(zhǔn)備為將來找工作復(fù)習(xí)，今天我就總結(jié)一下關(guān)于如何查找數(shù)組的前K個最小值實現(xiàn)方法，查找前K個最小值實現(xiàn)方法很多，主要的思想包括如下的幾種：
1、對數(shù)組進(jìn)行排序，然后前K個元素就是需要查找的元素，排序的方法可以采用快速排序，但是我們知道在快速排序中如果已經(jīng)是有序的數(shù)組，采用快速排序的時間復(fù)雜度是O(N^2),為了解決這種問題，通常選擇隨機(jī)選擇一個數(shù)組值pivot作為基準(zhǔn)，將數(shù)組分為S1 =< pivot和S2 > pivot，這樣就能避免快速排序中存在的問題，或者采用隨機(jī)選擇三個元素，然后取中間值作為基準(zhǔn)就能避免快速算法的最差時間復(fù)雜度，這種方法的前K個數(shù)字是有序的。
2、既然是選擇前K個對象，那么就沒必要對所有的對象進(jìn)行排序，可以采用快速選擇的思想獲得前K個對象，比如首先采用快速排序的集合劃分方法劃分集合：S1，pivot，S2，然后比較K是否小于S1的個數(shù)，如何小于，則直接對S1進(jìn)行快速排序，如果K的個數(shù)超過S1,那么對S2進(jìn)行快速排序，排序完成之后，取數(shù)組的前K個元素就是數(shù)組的前K個最小值。這種實現(xiàn)方法肯定比第一種的全快速排序要更快速。
3、將數(shù)組轉(zhuǎn)換為最小堆的情況，根據(jù)最小堆的特性，第一個元素肯定就是數(shù)組中的最小值，這時候我們可以將元素保存起來，然后將最后一個元素提升到第一個元素，重新構(gòu)建最小堆，這樣進(jìn)行K次的最小堆創(chuàng)建，就找到了前K個最小值，這是運用了最小堆的特性，實質(zhì)上是最小堆的刪除實現(xiàn)方法。這種算法的好處是實現(xiàn)了數(shù)組的原地排序，并不需要額外的內(nèi)存空間。
4、接下來的這種思想有點類似桶排序，首先給定一個K個大小的數(shù)組b，然后復(fù)制數(shù)組a中的前K個數(shù)到數(shù)組b中，將這K個數(shù)當(dāng)成數(shù)組a的前K個最小值，對數(shù)組b創(chuàng)建最大堆，這時候再次比較數(shù)組a中的其他元素，如果其他元素小于數(shù)組b的最大值（堆頂），則將堆頂?shù)闹颠M(jìn)行替換，并重新創(chuàng)建最大堆。這樣遍歷一次數(shù)組就找到了前K個最小元素。這種方法運用了額外的內(nèi)存空間，特別當(dāng)選擇的K值比較大時，這種方法有待于權(quán)衡一下。
這種方法對于海量數(shù)據(jù)來說是有較好的作用，對于海量數(shù)據(jù)不能全部存放在內(nèi)存中，這時候創(chuàng)建一個較小的數(shù)組空間，然后創(chuàng)建最大堆，從硬盤中讀取其他的數(shù)據(jù)，進(jìn)而實現(xiàn)前K個數(shù)據(jù)的查找。
這是比較傳統(tǒng)的幾種方法，當(dāng)然還存在其他的選擇方式，我在這邊就不闡述了，從上面幾種方法的可知，查找方法都充分運用了運用了數(shù)據(jù)結(jié)構(gòu)和算法的特性。因此數(shù)據(jù)結(jié)構(gòu)的靈活運用對算法的實現(xiàn)有很多的好處。
下面是我的實現(xiàn)代碼，數(shù)組中前K個元素我通過打印的方式實現(xiàn)，并沒有保存到新的數(shù)組中：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#include<time.h>
#define LEN 500000
#define K 100
/*堆的性質(zhì)*/
#define LEFTSON(i) (2*(i)+1)
#define RIGHTSON(i) (2*((i)+1))
#define PARENT(i) (((i)-1)/2)
void swap(int *a, int *b)
{
assert(a != NULL && b != NULL);
if(a != b)
{
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}
}
int partition(int *a, int left, int right)
{
int pivot = a[right];
int i = left;
int j = left - 1;
assert(a != NULL);
for(i = left; i < right; ++ i)
{
if(a[i] < pivot)
{
++ j;
swap(&a[i],&a[j]);
}
}
swap(&a[j + 1],&a[right]);
return (j + 1);
}
void quicksort(int *a, int left, int right)
{
int i = 0;
assert(a != NULL);
if(left < right)
{
i = partition(a,left,right);
quicksort(a, left, i - 1);
quicksort(a, i + 1, right);
}
}
int QuickSort(int *a, int size)
{
assert(a != NULL);
quicksort(a,0,size-1);
}
void quickselect(int *a, int left, int right, int k)
{
int i = 0;
assert(a != NULL && left <= k
&& left <= right && k <= right);
if(left < right)
{
i = partition(a, left, right);
if(i + 1 <= k)
quickselect(a, i + 1 , right, k);
else if(i > k)
quickselect(a, left, i - 1, k);
}
}
void QuickSelect(int *a, int size, int k)
{
assert(a != NULL);
quickselect(a, 0, size - 1, k);
}
/*最大堆*/
void max_heapify(int *a, int left, int right)
{
int tmp = 0;
int child = left;
int parent = left;
assert(a != NULL);
for(tmp = a[parent]; LEFTSON(parent) <= right;parent = child)
{
child = LEFTSON(parent);
if(child != right && a[child] < a[child + 1])
child ++;
if(tmp < a[child])
a[parent] = a[child];
else /*滿足最大堆的特性，直接退出*/
break;
}
a[parent] = tmp;
}
/*創(chuàng)建最大堆*/
void build_maxheap(int *a, int size)
{
int i = 0;
assert(a != NULL);
for(i = PARENT(size); i >= 0 ; -- i)
max_heapify(a,i,size - 1);
}
/*最小堆的實現(xiàn)*/
void min_heapify(int *a, int left, int right)
{
int child = 0;
int tmp = 0;
int parent = left;
assert(a != NULL);
for(tmp = a[parent]; LEFTSON(parent) <= right; parent = child)
{
child = LEFTSON(parent);
if(child != parent && a[child] > a[child + 1])
child ++;
if(a[child] < tmp)
a[parent] = a[child];
else /*滿足最小堆的特性，直接退出*/
break;
}
a[parent] = tmp;
}
/*創(chuàng)建最小堆*/
void build_minheap(int *a, int size)
{
int i = PARENT(size);
assert(a != NULL);
for(; i >= 0; -- i)
min_heapify(a, i, size - 1);
}
/*采用快速排序查找*/
void find_Kmin_num_1(int *a , int size, int k)
{
int i = 0;
assert(a != NULL);
QuickSort(a, size);
#if 0
for(i = 0; i < k ; ++ i)
printf("%d\t",a[i]);
printf("\n");
#endif
}
/*采用快速選擇實現(xiàn)*/
void find_Kmin_num_2(int *a, int size, int k)
{
int i = 0;
assert(a != NULL);
QuickSelect(a, size, k);
#if 0
for(i = 0; i < k ; ++ i)
printf("%d\t",a[i]);
printf("\n");
#endif
}
/*采用最大堆實現(xiàn)*/
void find_Kmin_num_3(int *a, int size, int k)
{
int i = 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);
}
}
#if 0
for(i = 0; i < k ; ++ i)
printf("%d\t",b[i]);
printf("\n");
#endif
}
/*采用最小堆刪除元素的方式實現(xiàn)*/
void find_Kmin_num_4(int *a ,int size, int k)
{
int i = 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");
}
int main()
{
int a[LEN];
int b[LEN];
int c[LEN];
int d[LEN];
int i = 0,j = 0;
clock_t _start;
double times = 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() - _start)/CLOCKS_PER_SEC;
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);
return 0;
}
檢測算法的性能：
[gong@Gong-Computer interview]$ gcc -g minKnum.c -o minKnum
[gong@Gong-Computer interview]$ ./minKnum
快速排序的查找需要:0.130000
快速選擇的查找需要:0.020000
最大堆的查找需要:0.000000
最小堆的查找需要:0.010000
從結(jié)果可知，快速排序的算法效果最差，而最大堆的效果最好，最小堆的效果其次，但是最大堆運用了額外的內(nèi)存空間。因此在內(nèi)存空間限制的情況下，考慮最小堆是比較合適的。但是最大堆的思想確實很精妙的，運用了類似桶排序的性質(zhì)。
為了說明算法能否實現(xiàn)前K個最小值的查找，改變數(shù)組大小為50，并打印各個方法完成的情況，查找前10個數(shù)據(jù)，實驗結(jié)果如下所示：
[gong@Gong-Computer interview]$ ./minKnum
15 38 14 43 31 45 42 1 32 23 43 34 9 4 45 31 25 48 8 42 40 27 36 30 32 4 11 23 47 12 24 14 1 40 8 32 36 0 35 18 26 28 2 35 35 49 17 12 48 27
0 1 1 2 4 4 8 8 9 11
快速排序的查找需要:0.000000
1 9 4 8 4 11 1 8 0 2
快速選擇的查找需要:0.000000
11 8 9 4 2 1 8 1 4 0
最大堆的查找需要:0.000000
0 1 1 2 4 4 8 8 9 11
最小堆的查找需要:0.000000
從上面的實驗結(jié)果可知，四種方法都是實現(xiàn)了獲得前K個最小元素。