算法分析与设计实验报告第次实验实验名称型线性时间选择算法实验目的通过上机实验，要求掌握型线性时间选择算法的问题描述、算法设计思想、程序设计。使用舍伍德型选择算法，根据不同的输入用例，能准确的输出用例中的中值，并计算出程序运行所需要的时间。用分治法查找数组元素的最大值和最小值实验原理问题描述：给定任意几组数据，利用舍伍德型选择算法，找出数组中的中值并输出（若数组为奇数个则输出中值，若数组为偶数个则输出第小元素）。设是一个确定性算法，当它的输入实例为时所需的计算时间记为。设是算法的输入规模为的实例的全体，则当问题的输入规模为时，算法所需的平均时间为皿）二工°（讪兀|。这显然不能排除存在e使得的可能性。希望获得一个随机化算法，使得对问题的输入规模为的每一个实例均有如⑶=「心）十$（用）。这就是舍伍德算法设计的基本思想。当与相比可忽略时，舍伍德算法可获得很好的平均性能。对于选择问题而言用拟中位数作为划分基准可以保证在最坏的情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏的情况下需要计算时间。舍伍德选择算法则随机地选择一个数组元素作为划分基准,这样既保证算法的线性时间平均性能，又避免了计算拟中位数的麻烦。用随机产生和之间的一个整数作为划分基准，对中个元素进行划分时，第小元素可能在低区子数组，或者刚好是划分基准，或者在较大的子数组中。低区子数组含有一个元素的概率为，含有个元素的概率为最坏情况是第小元素总是被划分在较大的子数组中，此时在较大子数组中重新选择随机的划分基准，找出第小元素。舍伍德算法属于概率算法，消除了运行时间和输入实例之间的联系。实验步骤先判断是否需要进行随机划分即（€（,））；产生随机数，选择划分基准，将与交换；以划分基准为轴做元素交换，使得一侧数组小于基准值，另一侧数组值大于基准值；判断基准值是否就是所需选择的数，若是，则输出；若不是对子数组重复步骤。关键代码计算中第小元素基准以划分基准为轴作元素交换对子数组重复划分过程计算中第小元素假设是一个键值无穷大的元素随机选择的划分实验心32122517104610088645220第£小的元素为:32ritetineis7.100fpocessexitedwithpetuvnualue0*pes5tocontinue-..通过本次实验明白了什么是舍伍德算法。知道了和开始的快速排序找第小元素相比，舍伍德算法以高概率对任何实例均有效，算法时间不受输入实例的影响。它的核心在于随机选择划分基准，保证了算法的线性时间平均性能。从上面测试结果时间上也可以看出时间的平均性能。在课本上了解了随机洗牌算法和搜索有序表两个部分，知道了舍伍德算法还可用于设计高效的数据结构如跳跃表，应用真的很广泛。附录：完整代码建一个项目工程测试结果测试结果如下图:交换的值计算中第小元素随机选择的划分基准以划分基准为轴作元素交换对子数组重复划分过程计算假设中第小元素是一个键值无穷大的元素第小的元素为:RandomNumber.cppR^ndomNumber-.hSherwoodxpp1234568El1112131<1516171；19L2021constunsignedlongnuaxshQr-=655：5L；conEtunsignedLongn-iltiplisr-ccanstunsignedLcmg5ddeu—"i2345~:^iz-dafRANDOhlNUMBER_-fdefi-aRANDOMNUMBER_HclassRandonLNumber{private://兰前押丁ueislgnedlongrandseed；public://构珞函数”默认翁G麦示电系统嘗踰产宅种-FEaiidamll-^uutier(unsignedlongs=3):"*也、刀》之间的随艇整最unsignedshor七Fandom(TinsignedllongnJ；门产生门*1;-乙闻的睡橫买敷doublefAandoin门；丄fsnciit//RandomNumber.cppRmndomNumber.cppR力nddmNurnber-hSherwG'od,cpp1245678//RaiiCtaEiNLLnibej?・cpp#include#in.elude#in，elude#includeRarLdomniinir!er.h"1心匸dlib・h>・h>口sitigz^ai：iespacestd；101101213141516-1710□产生种亍Ran.domNumfciQr::Rand
