Sherwood 型线性时间选择算法

《Sherwood 型线性时间选择算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计实验报告第次实验实验名称Sherwood型线性时间选择算法实验目的1.通过上机实验，要求掌握Sherwood型线性时间选择算法的问题描述、算法设计思想、程序设计。2.使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，并计算出程序运行所需要的时间。3.用分治法查找数组元素的最大值和最小值实验原理(1)问题描述：给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第n/2小元素）。(2)设A是一个确定性算法，当它的输入实例为x时所需的计算时间记为

2、tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的输入规模为n时，算法A所需的平均时间为。这显然不能排除存在x∈Xn使得的可能性。希望获得一个随机化算法B，使得对问题的输入规模为n的每一个实例均有。这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时，舍伍德算法可获得很好的平均性能。(3)对于选择问题而言,用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要O(n^2)计算时间。舍伍德选择算法则随机地

3、选择一个数组元素作为划分基准，这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。(4)用Select随机产生l和r之间的一个整数作为划分基准，对a[l:r]中n个元素进行划分时，第k小元素可能在低区子数组，或者刚好是划分基准，或者在较大的子数组中。低区子数组含有一个元素的概率为2/n，含有i个元素的概率为1/n,最坏情况是第k小元素总是被划分在较大的子数组中，此时在较大子数组中重新选择随机的划分基准，找出第k小元素。(5)舍伍德算法属于概率算法，消除了运行时间和输入实例之间的联系。实验步骤(1)先判断是否需要进行随机划

4、分即（kϵ（1，n）?n>1?）；(2)产生随机数j，选择划分基准，将a[j]与a[l]交换；(3)以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值；(4)判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组重复步骤(2)(3)(4)。关键代码//Sherwood.cpptemplateTypeselect(Typea[],intlt,intrt,intk){//计算a[lt:rt]中第k小元素staticRandomNumberrnd;while(true){if(lt

5、>rt)returna[lt];inti=lt,j=lt+rnd.Random(rt-lt+1);//随机选择的划分基准Swap(a[i],a[j]);j=rt+1;Typepivot=a[lt];//以划分基准为轴作元素交换while(true){while(a[++i]pivot);if(i>=j)break;Swap(a[i],a[j]);}if(j-lt+1==k)returnpivot;a[lt]=a[j];a[j]=pivot;//对子数组重复划分过程if(j-lt+1

6、k=k-j+lt-1;lt=j+1;}elsert=j-1;}}templateTypeSelect(Typea[],intn,intk){//计算a[0:n-1]中第k小元素//假设a[n]是一个键值无穷大的元素if(k<1

7、

8、k>n)cerr<<"Wrong!"<

9、心在于随机选择划分基准，保证了算法的线性时间平均性能。从上面测试结果时间上也可以看出时间的平均性能。在课本上了解了随机洗牌算法和搜索有序表两个部分，知道了舍伍德算法还可用于设计高效的数据结构如跳跃表，应用真的很广泛。附录：完整代码(建一个项目工程)//Sherwood.cpp#include"RandomNumber.h"#include#include#include#include#includeusingnamespacestd;cons

10、tintINF=9999;//交换a,b的值templatevoidSwap(Type&a,Type&b){Typetemp;temp=a;a=b;b=temp;}templateTypese