查找最小的k个元素

题目：输入n个整数，输出其中最小的k个。

例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

两种思路，无非就是时间与空间的妥协。

限制空间的时候要对原数组进行排序，最好的时间复杂度是O(nlogn)，由此可见，当牺牲一部分空间的时候会换来时间复杂度的降低。进而再想到利用一个大小为K的临时数组，来存储K个最小的值，在遍历原数组的同时，更新临时数组里的数据就OK了。那么，现在的问题就是更新临时数组，怎样才能每访问一个数据，都能使临时数组里的数据是最小的K个。自然想到选出临时数组里面的最大值，和原数组里的新访问的值进行比较，判断是否替换最大值。遍历原数组的时间复杂度是O(n)那么，选择临时数组的最大值的时间复杂度要小于O(logn)才对得住牺牲的空间复杂度。。。

现在，马上想到的选择最大值的方法是进行一趟冒泡，但时间复杂度是O(K)不见得比O(logn)小。能比O(logn)小的，自然就想到了O(logk)，见到logk就想到了二叉树或者说是堆。。。嗯，也就是大根堆

当元素个数小于k的时候，直接把原数组里面的数据直接放到临时数组里面，当达到k后，便建立大根堆——选出最大的和原数组的新数据进行比较（每次的时间复杂度为logk，这样共要进行n-k次，因此，时间复杂度是O(nlogk)。但是，还有一种做法，是原地比较，将原数组建成一个小根堆，然后输出k次，就可以在原数组末端得出最小的k个数据，这样的时间复杂度应该是max(O(n)[建堆]+O(klogn)[选出k个])，和利用临时数组的比不知哪个的时间复杂度会更低。

下面是利用临时数组的做法：

#include<stdio.h>

#include<stdlib.h>

void HeapAdjust(int* a,int length,int i){

int lchild =  * i ;

int rchild =  * i + ;

int max = i;

if(lchild < length&&a[max] < a[lchild])

  max = lchild;

if(rchild < length&&a[max] < a[rchild])

  max = rchild;

int temp = a[max];

if(max != i){

  a[max] = a[i];

  a[i] = a[max];

  HeapAdjust(a,length,max);

}

}

void HeapSort(int*temp,int*a,int length,int k){//遍历原数组，更新临时数组

for(int i = k + ; i <= length; i++){

  if(temp[] > a[i]){

    temp[] = a[i];

    HeapAdjust(temp,k,);

  }

}

void HeapBuild(int* a,int length){

for(i = length / ; i > ; i--)

  HeapAdjust(a,length,i);

}

void minKvalue(int* a,int length,int k){//所要求功能函数

if(k > length||k < ||length < )

  return ;

int* temp = (int*)malloc(sizeof(int)*(k + ));

int i;

for(i = ; i <= k; i++)

  temp[i] = a[i];

BuildHeap(temp,k);

HeapSort(temp,a,length,k);

for(i = ; i <= k; i++)

  printf("%4d",temp[i]);

printf("\n");

free(temp);

}

int main(){//测试函数

int length,*a;

printf("输入数组长度:\n");

scanf("%d",&length);

a = (int*)malloc(sizeof(int)*(length + ));

printf("输入%d个数据:\n");

for(int i = ; i <= length; i++)

  scanf("%d",a + i);

minKvalue(a,temp,length,k);

free(a);