n个数第k个大

题：一个数组有n个数，无序，找出从大到小排列在第k位的数，其中1<=k<=n

#include
#define n 10

main()
{
	int a[n],i,j,t,k;

	for(i=0;i

思考：假设要设计一个程序，从n个数中找出第k大的那个数。

许多同学都会觉得这个问题太容易了，因为只要设计一个能够容纳这n个数的数组，把n个数顺序读入，每读入一个数就与已经读入的数依次进行比较，然后插在适当的位置，使得在数组里的数，总是从大到小排序，最后数组里的第k个元素一定就是所求的解。然而问题并不这么简单。首先，你怎么知道机器的内存一定有足够的空间能够容纳这n个数的数组呢？如果不能应该怎么办？聪明的同学也许想出一个办法：内存中只要开辟一个能够容纳k个数的数组就行，在把n个数顺序读入时，只要保证最大的k个数都在数组里，并且总是从大到小排序，其它数根本不必保存（当然更不必排序），最后数组里的最后一个元素一定就是所求的解。显然，这后一种方法在时间和空间的占有方面都比前一种好（为什么？请读者自己分析），假如内存中能够开辟一个容纳k个数的数组，这个程序就可以上机实现。不过我们还可以大概估计一下这个程序的时间开销：假如每读入一个数，都要与数组中所有数进行比较，仅仅计算比较的次数可知，第二到第k个元素各自比较1到k-1次，k后面的所有元素各自都要比较k次。不难算出一共比较的次数是：S=1+2+…+(k-1)+k*(n-k)=k*(k-1)/2+k*(n-k)=k*n-k*k/2-k/2.

如果n=108，k=5*107, 那么S>3.7*1015。假如一台计算机每秒能够执行3.7*108次两个数的比较，仅比较就需要10^7秒（大约100多天）的时间。如果要求读者设计一个算法，能够把速度提高100倍，即对于同样规模的问题，使用同样的计算机，你的算法必须在1天内给出答案，这种算法存在吗？答案是肯定的。