良久没有写博客了，这一段时刻首要在预备为将来找工作温习，今日我就总结一下关于怎么查找数组的前K个最小值完结办法，查找前K个最小值完结办法许多，首要的思维包含如下的几种：
1、对数组进行排序，然后前K个元素便是需求查找的元素，排序的办法能够选用快速排序，可是咱们知道在快速排序中假如已经是有序的数组，选用快速排序的时刻复杂度是O(N^2),为了处理这种问题，一般挑选随机挑选一个数组值pivot作为基准，将数组分为S1 =< pivot和S2 > pivot，这样就能防止快速排序中存在的问题，或许选用随机挑选三个元素，然后取中心值作为基准就能防止快速算法的最差时刻复杂度，这种办法的前K个数字是有序的。
2、既然是挑选前K个目标，那么就没必要对一切的目标进行排序，能够选用快速挑选的思维取得前K个目标，比方首要选用快速排序的调集区分办法区分调集：S1，pivot，S2，然后比较K是否小于S1的个数，怎么小于，则直接对S1进行快速排序，假如K的个数超越S1,那么对S2进行快速排序，排序完结之后，取数组的前K个元素便是数组的前K个最小值。这种完结办法必定比第一种的全快速排序要更快速。
3、将数组转换为最小堆的状况，依据最小堆的特性，第一个元素必定便是数组中的最小值，这时候咱们能够将元素保存起来，然后将最终一个元素提升到第一个元素，从头构建最小堆，这样进行K次的最小堆创立，就找到了前K个最小值，这是运用了最小堆的特性，实质上是最小堆的删去完结办法。这种算法的优点是完结了数组的原地排序，并不需求额定的内存空间。
4、接下来的这种思维有点相似桶排序，首要给定一个K个巨细的数组b，然后仿制数组a中的前K个数到数组b中，将这K个数当成数组a的前K个最小值，对数组b创立最大堆，这时候再次比较数组a中的其他元素，假如其他元素小于数组b的最大值（堆顶），则将堆顶的值进行替换，并从头创立最大堆。这样遍历一次数组就找到了前K个最小元素。这种办法运用了额定的内存空间，特别当挑选的K值比较大时，这种办法有待于权衡一下。
这种办法关于海量数据来说是有较好的效果，关于海量数据不能悉数存放在内存中，这时候创立一个较小的数组空间，然后创立最大堆，从硬盘中读取其他的数据，从而完结前K个数据的查找。
这是比较传统的几种办法，当然还存在其他的挑选办法，我在这边就不论述了，从上面几种办法的可知，查找办法都充分运用了运用了数据结构和算法的特性。因而数据结构的灵活运用对算法的完结有许多的优点。
下面是我的完结代码，数组中前K个元素我经过打印的办法完结，并没有保存到新的数组中：
#include
#include
#include
#include
#include
#define LEN 500000
#define K 100
/*堆的性质*/
#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;
}
/*创立最大堆*/
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);
}
/*最小堆的完结*/
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;
}
