输入n个整数，找出其中最小的k个数

解法1：需要修改输入的数组，基于partition快速排序来做，时间复杂福O（N）

分析：基于数组的第k个元素来调整，使的比第k个数大的所有数字放到数组的右边，这样，数组左边k个就是最小的k个数字

voidGetLestNumber(int*input,intn,int*output,intk){if(input==NULL||output==NULL||k>n||n<=0||k<=0)return;intstart=0;intend=n-1;intindex=Partition(input,n,start,end);while(index!=k-1){if(index>k-1){end=index-1;index=Partition(input,n,start,end);}else{start=index+1;index=Partition(input,n,start,end);}}for(inti=0;i<k;++i){output[i]=input[i];}}

解法二：

分析：先创建一个大小为k的数据容器来存储最小的k个数字，接着每次从输入的n个整数中读入一个数，如果容器中少于k个数则直接放，若大于则表示容器以满，此时找出容器中最大值，然后拿输入的值和最大值比较，若待插入的数小于最大值，则直接替换。

最大堆的结构每次可以在O（1）得到最大值，但需要o（logk）时间来完成删除及插入

红黑树同上，但是代码简于大堆

voidGetLestNumber(int*input,intn,int*output,intk){if(input==NULL||output==NULL||k>n||n<=0||k<=0)return;intstart=0;intend=n-1;intindex=Partition(input,n,start,end);while(index!=k-1){if(index>k-1){end=index-1;index=Partition(input,n,start,end);}else{start=index+1;index=Partition(input,n,start,end);}}for(inti=0;i<k;++i){output[i]=input[i];}}解法二：分析：先创建一个大小为k的数据容器来存储最小的k个数字，接着每次从输入的n个整数中读入一个数，如果容器中少于k个数则直接放，若大于则表示容器以满，此时找出容器中最大值，然后拿输入的值和最大值比较，若待插入的数小于最大值，则直接替换。最大堆的结构每次可以在O（1）得到最大值，但需要o（logk）时间来完成删除及插入constintN=1000;constintk=10;voidAdjustDown(int*a,intsize,intparent){intchild=(parent-1)/2;while(child<size){if(child+1<size&&a[child]>a[child+1])child++;if(a[child]>a[parent]){swap(a[child],a[parent]);parent=child;child=(parent-1)/2;}elsebreak;}}voidGetTopK(int*a){assert(k<N);inttop[k];for(inti=0;i<k;i++){top[i]=a[i];}for(inti=(k-2)/2;i>=0;i++){AdjustDown(top,k,i);}for(inti=N-k-1;i<N;i++){if(a[i]>top[0]){top[0]=a[i];AdjustDown(top,k,0);}}}