Sherwood型线性时间选择算法

算法分析与设计实验报告第8次实验姓名学号班级时间6.4上午地点四合院实验名称Sherwood型线性时间选择算法实验目的通过上机实验，要求掌握Sherwood型线性时间选择算法的问题描述、算法设计思想、程序设计。实验原理1、使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，并计算出程序运行所需要的时间。2、设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。实验步骤1、先判断是否需要进行随机划分即（kϵ（1，n）?n1?）；2、产生随机数j，选择划分基准，将a[j]与a[l]交换；3、以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值；4、判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组重复步骤2、3、4。5、输入数据到input.txt文件中。6、添加计算运行时间的代码，计算不同规模数据的运行时间，并将结果输出到output文件中。7、分析时间复杂度：非递归的舍伍德型选择算法可以在O(n)平均时间内找出n个输入元素中的第k小元素。关键代码templateclassTypeTypeselect(Typea[],intn,intk){if(k1||kn){cout请输入正确的k!endl;return0;}returnselect(a,0,n-1,k);}//计算a[l:r]中第k小元素templateclassTypeTypeselect(Typea[],intl,intr,intk){staticRandomNumberrnd;while(true){if(l=r){returna[l];}inti=l,j=l+rnd.Random(r-l+1);//随机选择划分基准Swap(a[i],a[j]);j=r+1;Typepivot=a[l];//以划分基准为轴做元素交换while(true){while(a[++i]pivot);while(a[--j]pivot);if(i=j){break;}Swap(a[i],a[j]);}if(j-l+1==k)//第k小{returnpivot;}//a[j]必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大a[l]=a[j];a[j]=pivot;//对子数组重复划分过程if(j-l+1k){k=k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1l=j+1;}else{r=j-1;}}}测试结果说明：output文件中第一组结果为手动输入验证正确与否的测试数据，其他几组为随机生成数据的结果。input文件中输入的是手动输入的数据。附录：完整代码//RandomNumber.h#includetime.h#includeiostreamusingnamespacestd;实验心得过这次实验，我回顾了舍伍德线性时间查找问题。对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要O(n^2)计算时间。舍伍德选择算法则随机地选择一个数组元素作为划分基准，这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。我主要是实现书上代码，理解起来也比较容易，关于随机数的生成部分，借鉴了网上一些代码的方法。通过这次实验，我理解了舍伍德算法，也理解了线性时间查找问题，收获很多。实验得分助教签名constunsignedlongmaxshort=65535L;constunsignedlongmultiplier=1194211693L;constunsignedlongadder=12345L;classRandomNumber{private://当前种子unsignedlongrandSeed;public://构造函数,默认值0表示由系统自动产生种子RandomNumber(unsignedlongs=0);//产生0~n-1之间的随机整数unsignedshortRandom(unsignedlongn);//产生[0,1)之间的随机实数doublefRandom();};//产生种子RandomNumber::RandomNumber(unsignedlongs){if(s==0)randSeed=time(0);//用系统时间产生种子elserandSeed=s;}//产生0~n-1之间的随机整数unsignedshortRandomNumber::Random(unsignedlongn){randSeed=multiplier*randSeed+adder;return(unsignedshort)((randSeed16)%n);}//产生[0,1)之间的随机实数doubleRandomNumber::fRandom(){returnRandom(maxshort)/double(maxshort);}//源.cpp#includeRandomNumber.h#includeiostream#includetime.h#includealgorithm#includefstreamusingnamespacestd;ifstreamin(input.txt);ofstreamout(output.txt);templateclassTypeinlinevoidSwap(Type&a,Type&b){Typetemp=a;a=b;b=temp;}//计算a[l:r]中第k小元素templateclassTypeTypeselect(Typea[],intl,intr,intk){staticRandomNumberrnd;while(true){if(l=r){returna[l];}inti=l,j=l+rnd.Random(r-l+1);//随机选择划分基准Swap(a[i],a[j]);j=r+1;Typepivot=a[l];//以划分基准为轴做元素交换while(true){while(a[++i]pivot);while(a[--j]pivot);if(i=j){break;}Swap(a[i],a[j]);}if(j-l+1==k)//第k小{returnpivot;}//a[j]必然小于pivot,做最后一次交换，满足左侧比pivot小，右侧比pivot大a[l]=a[j];a[j]=pivot;//对子数组重复划分过程if(j-l+1k)//计算前一半元素个数{k=k-j+l-1;//右侧：k-(j-l+1)=k-j+l-1l=j+1;}else{r=j-1;}}}//计算a[0:n-1]中第k小元素//假设a[n]是一个键值无穷大的元素templateclassTypeTypeselect(Typea[],intn,intk){if(k1||kn){cout请输入正确的k!endl;return0;}returnselect(a,0,n-1,k);}voidtest1(){intn;inn;out测试数据：endl;inta[n];out原数组为：endl;for(inti=0;i9;i++){ina[i];outa[i];}outendl;intm;inm;out所给数组第m小元素为：select(a,n,m)endlendl;}voidtest(intsize){out数组规模:sizeendl;srand(time(0));int*a=newint[size];for(inti=0;isize;i++)a[i]=rand();intk=size/8;clock_tstart,end,over;start=clock();end=clock();over=end-start;start=clock();intx=select(a,size,k);end=clock();out所给数组第k小元素为：xendl;out开始时间为:start结束时间为:end持续时间为:(double)(end-start)/CLOCKS_PER_SECendl;outendlendl;free(a);}intmain(){cout请在input.txt中填写原测试数据，第一行为数据个数，第二行为数据，第三行为想要的第几小的数据endl;test1();test(10000);test(100000);test(1000000);test(10000000);cout数据读入完毕，请在output.txt中查看结果endl;return0;}