求数组的第k大数

此题也可转换成求前k大数，方法类似。

#include <stdio.h>
#include <stdlib.h>

int partition(int a[],int n) //快排思想
{
	int l = 0,r = n - 1;
	int random = rand()%n;
	int temp;
	temp = a[random];
	a[random] = a[0];
	a[0] = temp;
	while(l<r)
	{
		while(l<r && a[r]>=temp)
			r--;
		if(l<r)
			a[l++] = a[r];
		while(l<r && a[l]<temp)
			l++;
		if(l<r)
			a[r--] = a[l];
	}
	a[l] = temp;
	return l;
}

void find(int a[],int n,int k)
{
	if(a==NULL || n<=0 || n<k)
		return;
	int mid = partition(a,n);
	if(mid == n-k)//找到第k大数
	{
		printf("第k大数是:%dn",a[mid]);
		return;
	}
	else if(mid < n-k) //第k大数在右数组，且仍然是第k大数
		find(a+mid+1,n-mid-1,k);
	else
		find(a,mid,k-(n-mid));//第k大数在左数组,变成第k-(n-mid)大数
}

int main()
{
	int a[] = {123,42,52,747,53,456,2,74};
	int i;
	printf("数组值为:n");
	for(i=0;i<8;i++)
		printf("%dt",a[i]);
	printf("n");
	int k;
	printf("请输入k值:n");
	scanf("%d",&k);
	find(a,8,k);
	return 0;
}