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

1、對(duì)數(shù)組進(jìn)行排序，然后前K個(gè)元素就是需要查找的元素，排序的方法可以采用快速排序，但是我們知道在快速排序中如果已經(jīng)是有序的數(shù)組，采用快速排序的時(shí)間復(fù)雜度是O(N^2),為了解決這種問題，通常選擇隨機(jī)選擇一個(gè)數(shù)組值pivot作為基準(zhǔn)，將數(shù)組分為S1 =< pivot和S2 > pivot，這樣就能避免快速排序中存在的問題，或者采用隨機(jī)選擇三個(gè)元素，然后取中間值作為基準(zhǔn)就能避免快速算法的最差時(shí)間復(fù)雜度，這種方法的前K個(gè)數(shù)字是有序的。

2、既然是選擇前K個(gè)對(duì)象，那么就沒必要對(duì)所有的對(duì)象進(jìn)行排序，可以采用快速選擇的思想獲得前K個(gè)對(duì)象，比如首先采用快速排序的集合劃分方法劃分集合：S1，pivot，S2，然后比較K是否小于S1的個(gè)數(shù)，如何小于，則直接對(duì)S1進(jìn)行快速排序，如果K的個(gè)數(shù)超過S1,那么對(duì)S2進(jìn)行快速排序，排序完成之后，取數(shù)組的前K個(gè)元素就是數(shù)組的前K個(gè)最小值。這種實(shí)現(xiàn)方法肯定比第一種的全快速排序要更快速。

3、將數(shù)組轉(zhuǎn)換為最小堆的情況，根據(jù)最小堆的特性，第一個(gè)元素肯定就是數(shù)組中的最小值，這時(shí)候我們可以將元素保存起來，然后將最后一個(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、接下來的這種思想有點(diǎn)類似桶排序，首先給定一個(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ù)來說是有較好的作用，對(duì)于海量數(shù)據(jù)不能全部存放在內(nèi)存中，這時(shí)候創(chuàng)建一個(gè)較小的數(shù)組空間，然后創(chuàng)建最大堆，從硬盤中讀取其他的數(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è)元素我通過打印的方式實(shí)現(xiàn)，并沒有保存到新的數(shù)組中：

#include
#include
#include
#include
#include

#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);
}

/*最小堆的實(shí)現(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;
}