编程之美系列之寻找最大的K个数

题目描述：有很多无序的数，姑且家丁它们各不相等，怎么选出其中最大的若干个数呢？这里我不想去写一些很没有意义的思路。神马先排序取前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);
	}
}