分治算法设计与应用(2)

else

{

num1=num/ 5; j=0; num2=0;

for(i=0;i

temp[j]=S[i]; j++; if(j==5)

{

j=0; sort(5,temp); M[num2]=temp[2]; num2++; } }

m=select((num1+1)/2,M,num2); n1=n2=n3=0; for(i=0;i

S1[n1]=S[i]; n1++; }

else if(S[i]==m) { S2[n2]=S[i]; n2++; } else

{

S3[n3]=S[i]; n3++; } } if(n1>k)

return(select(k,S1,n1)); else if(n1+n2>=k) return m;

else return(select(k-n1-n2,S3,n3)); } }

/*----------------主函数------------------*/ void main() {

int m,i,t,j;

printf(\输入测例个数：\\n\ scanf(\ for(i=1;i<=m;i++) {

printf(\第-个测例数如下：\\n\ scanf(\ for(j=1;j<=Data[i].number;j++) {

scanf(\ }

scanf(\ printf(\

printf(\第-个测例的前%d小元素是: \\n\ for(t=1;t<=Data[i].number;t++) {

Data[i].output[t]=select(t,Data[i].elem,Data[i].number); }

find(Data[i].output,Data[i].number,Data[i].k); printf(\ } }

五、实验结果

实验三.(1).cpp

按照实验要求输入测试例，得到的实验结果是：

实验三.(2).cpp

按照实验要求输入测试例，得到的实验结果是：

六、总结

1.主要要注意实验中的细节

2.在写算法的时候要注意时间复杂性。