求数列中的第1～k小元素

1.问题描述 设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题，这里k不是常量，即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。 2. 具体要求 输入的第一行是一个正整数m，表示测试例个数。接下来几行是m个测试例的数据，每个测试例的数据由三行组成，其中其中，第一行输入一个正整数n，表示元素的个数；第二行输入n个整数，整数之间用一个空格隔开。第三行输入一个正整数k，表示求该组测试例中的前k个最小元素。（设给出的每个整数序列中的元素是唯一的。） 输出：对于每个测试例输出一行，由k个整数组成，表示输入的n个整数中前k个最小元素。整数之间用一个空格隔开。

#include
#define M 100
#define N 5
/*..利用快速排序将数组按升序排序..*/
int partition （int key[]int lowint high）
{ 
	int k;
	k = key[low];
	while（low < high）
	{
		while（low= k） high--;
		key[low] = key[high];
		while（low		key[high] = key[low];
	}
	key[low] = k;
	return low;
}
void QSort（int str[]int lowint high）
{
	int k;
	if（low < high）
	{
      k = partition（strlowhigh）;
	  QSort（strlowk-1）;
	  QSort（strk+1high）;
	}
}
/*...求中项...*/
void mid（int s[]int i int r[]）
{
	int j=5*i;
	QSort（sjj+4）;
	r[i]=s[j+2];
}
/*...求数组的第K小元素...*/
int  select（int A[]int pint k）
{
	int qi=0jst;
	int mc[M]small[M]mid1[M]big[M];
	if（p<44） 
	{
		/*...直接排序...*/
		QSort（A0p-1）;
		return A[k-1];
	}
	/*...分成q组，每组5个元素...*/
	q=p/5;
	/*...求各组中项...*/
	for（j=0;j	{
		mid（Ajc）;
	}
	/*...递归调用求中项