《计算机算法设计与分析》实验报告-线性时间选择

福州大学数计学院《计算机算法设计与分析》实验报告专业：数理综合班学号081200416姓名林灵锋班级数理综合班实验名称线性时间选择实验主要内容熟悉编程实验目的和要求一、利用RandomizedSelect和Select算法找出n个元素中第k小的元素。二、设计思想：递归调用select函数求解算法时间复杂度：n75时，T(n)=C1;n=75时，T(n)=C2n+T(n/5)+T(3n/4);问题描述和主要步骤一、程序：#includestdlib.h#includectime#includeiostreamusingnamespacestd;templateclassTypevoidSwap(Type&x,Type&y){Typetemp=x;x=y;y=temp;}templateclassTypevoidBubbleSort(Typea[],intp,intr){for(inti=p;i=r-1;i++)for(intj=r-1;j=i;j--){if(a[j]a[j-1]){Swap(a[j],a[j-1]);}}}templateclassTypeintPartition(Typea[],intp,intr,Typex){inti=p-1,j=r+1;while(true){while(a[++i]x&&ir);while(a[--j]x);if(i=j){break;}Swap(a[i],a[j]);}a[j]=x;returnj;}templateclassTypeTypeSelect(Typea[],intp,intr,intk){if(r-p75){BubbleSort(a,p,r);returna[p+k-1];}for(intm=0;m=(r-p-4)/5;m++){BubbleSort(a,p+5*m,p+5*m+4);Swap(a[p+5*m+2],a[p+m]);}Typex=Select(a,p,p+(r-p-4)/5,(r-p-4)/10);inti=Partition(a,p,r,x);intj=i-p+1;if(k=j){returnSelect(a,p,i,k);}else{returnSelect(a,i+1,r,k-j);}}intRandom(intx,inty){intn=rand()%(y-x)+x;returnn;}intmain(){inta[100],k;srand((unsigned)time(NULL));cout随机输入的100个数为：;coutendl;for(inti=0;i100;i++){a[i]=Random(0,200);couta[i]:a[i];}coutendl;cout请输入所搜索的k=;cink;cout第k小元素是Select(a,0,99,k)endl;BubbleSort(a,0,99);cout将这100个数排序后的结果是：;coutendl;for(intj=0;j100;j++){couta[j]:a[j];}coutendl;cout第k小元素是a[k-1]endl;coutendl;return0;}实验结果（截图表示）研究与探讨说明：实验名称为教学大纲中各章的实验项目名称，实验内容为具体章节的实验内容名称