题目描述：有很多无序的数，姑且家丁它们各不相等，怎么选出其中最大的若干个数呢？这里我不想去写一些很没有意义的思路。神马先排序取前k个这种弱爆了并且一点也不适用的思想我就不想废话了，因为如果数据量很大的时候，对所有数据排序肯定是费力不讨好的事情，换换思路，不能全部排序，那就部分排序吧！这里介绍两个比较实用的。当然为了有点递进关系，先来一个比较差一点的方法。如果对排序算法还不是很熟悉的，可以参考博客： 排序算法。
1、快排。回忆一下快排的思想，选一个关键元素key，利用key将数组分成两部分，左边一部分比key大，右边一部分比key小（当然本身的定义是左边一部分比key小，右边一部分比key大），那么key的位置有下面三种情况：
*如果key正好放在第k个数的位置上面，OK，那说明前k大的数我们已经找到了，就不需要排序了。
*如果key的位置比k小，那说明前面找到的最大的元素中还不足k个，那就在后面一段的数据中继续找。
*如果key的位置比k小，那说明前面找到的最大的元素的个数超过k了，那就在前面的一段数据中分出k个就不可以了。
如果是需要找最小的k个元素，类似的思想，这里就不废话了。代码如下：
void QuickSort(int *arr, int Begin, int End, int k)
{
if(!arr || Begin >= End || End < 0)
return;
int i,j;
int key;
i = (double)rand()/RAND_MAX * (End - Begin + 1) + Begin;
key = arr[i];
arr[i] = arr[Begin];
arr[Begin] = key;
i = Begin;
j = End;
while(i < j)
{
while(i < j && arr[j] <= key)//找到后面第一个比key大的元素
--j;
if(i < j)
arr[i++] = arr[j];
while(i < j && arr[i] >= key)//找到前面第一个比key小的元素
++i;
if(i < j)
arr[j--] = arr[i];
}
arr[i] = key;
if(i == k - 1)//恰好k个，返回
return;
else if(i < k - 1)//不足k个，在后面继续找
QuickSort(arr, i + 1, End, k);
else//多于k个，在前面分出k个
QuickSort(arr, Begin, i - 1, k);
}
2、堆排序。如果数据量很多的时候，快排有个什么坏处呢？它需要将所有数据都一次导入内存，在海量数据的情况下，显然是不能做到的，但是堆排序就可以。如果我们需要找最大的k个数，那就维护一个由k个数组成的最小堆，堆顶元素是堆的最小值。每次进来一个数，先与堆顶元素比较，如果小于堆顶元素，那一定小于堆中的任何一个元素。如果大于堆顶元素，OK，用这个数替换堆顶元素，然后调整新得到的堆。代码如下：
//将开始元素s到nLen组成的堆调整为最小堆
void MinHeapAdjust(int *arr, int s, int nLen)
{
if(!arr || s < 1 || nLen < 1 || s > nLen)
return;
int i,t;
t = arr[s];
for(i = s<<1; i <= nLen; i = s<<1)
{
if(i < nLen && arr[i] > arr[i|1])//找到左右子树中最小的一个
i |= 1;
if(t < arr[i])//t已经很小了，就不往下沉了
break;
arr[s] = arr[i];
s = i;
}
arr[s] = t;
}
3、给出两种方法的main函数调用，如果不需要，可以直接pass掉。
//打印数组
void Print(int *arr, int nLen)
{
for(int i = 0; i < nLen; ++i)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
const int N = 30;
int arr[N];
int i,n,k,v;
/* //快排的main函数调用部分
while(scanf("%d %d", &n, &k) != EOF)
{
for(i = 0; i < n; ++i)
scanf("%d", &arr[i]);
printf("输入k：");
scanf("%d", &k);
QuickSort(arr, 0, n - 1, k);
Print(arr, k);
}
*/
//堆排序main函数的调用部分
while(scanf("%d %d", &n, &k) != EOF)
{
for(i = 1; i <= k; ++i)
scanf("%d", &arr[i]);
//得到最小堆
for(i = k>>1; i > 0; --i)
MinHeapAdjust(arr, i, k);
for(i = k; i < n; ++i)
{
scanf("%d", &v);
if(v > arr[1])
{
arr[1] = v;
MinHeapAdjust(arr, 1, k);
}
}
Print(&arr[1], k);
}
}