实验要求
请采用分治策略实现从S集合中选第K小的数问题。
要求：
1)集合S的大小不要小于1000，值的分部范围可以是[0,20000]中的浮点数。K可以选择|S|/3, |S|/2等
2)可以改变输入集合S的大小，来分析算法运行时间随输入集合规模的变化
3)请严格按照课本第43页的算法伪代码思路来实现
设计原理
核心代码
double Select(double s[],int low,int high, int k) //求数组S中下标low到high中的第k个数{
double *M=new double[MAX];
//每五个数找中位数
if (high - low == 1)
return s[low];
if ((high - low < 5)&&(high-low>1))
{
InsertSort(s, low, high);
return s[low + k-1];
}
int t=0;
int i, j;
for (i = low; (j = i + 4)&&(j<high); i += 5)
{
InsertSort(s, i, j);
//把中位数放入M
M[t] = s[i + 2];
t++;
}
//选M的中位数m
double m= Select(M,0, t,t/2);
delete[] M;
//用m划分出S1和S2
double *S1 = new double[MAX];
double *S2=new double[MAX];
int s1=0, s2=0;
for (i = low; i < high; i++)
{
if (s[i] < m)
{
S1[s1] = s[i];
s1++;
}
if (s[i] > m)
{
S2[s2] = s[i];
s2++;
}
}
//子问题递归
if (k == s1+1)
{
return m;
}
else if (k <=s1)
{
return Select(S1, 0, s1, k);
}
else if(k>s1+1)
{
return Select(S2, 0, s2, k - s1 - 1);
}
delete[] S1;
delete[] S2;}
实验结果(（以在1000个随机数中选择第500小的数的情况为例）)
验证结果的正确：（中间行数据有省略）
算法时间复杂度分析
实验总结
通过实验可以看出，一般性的选择问题可以在O(n)时间内求解，采用的思想是用空间换时间。
选择第k小问题运用递归方法的时候，会出现堆栈溢出的情况，这个时候可以用使用new来创建动态数组，并在使用完之后释放，就可以解决此问题。