算法分析与复杂性理论 实验报告 基本排序

《算法分析与复杂性理论 实验报告 基本排序》由会员分享，可在线阅读，更多相关《算法分析与复杂性理论 实验报告 基本排序（17页珍藏版）》请在装配图网上搜索。

1、深圳大学实验报告课程名称：算法设计与分析实验名称： 多种排序算法的算法实现及性能比较学院： 计算机与软件学院专业:计算机科学与技术报告人：张健哲 学号： 2013150372 班级：3同组人：无指导教师：李炎然实验时间： 2015/3/252015/4/8一实验目的1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。二实验步骤与结果实验总体思路：利用switch结构来选择实验所要用的排序算法，每一种排序都用相同的计算运行时间 的代码，不同的算法就在算法实现部分进行改动（如下代码1至5所示。不断的改变数据

2、 规模，每一个规模在实验时，用循环进行多次实验并作为样本记录消耗的时间。最后输出在 不同排序算法下，不同的数据规模的20次实验样本和平均用时（如下图1至5所示。各排序算法的实现及实验结果： （注1：以下代码全部为伪代码，具体代码实现请参照程序中的代码） （注2：图中显示的时间单位均为毫秒，图中“排序所花时间”一项为平均消耗时间，平均 消耗时间结果以20组样本计算平均值后取整得到（并非四舍五入）。）1、选择排序代码1：for i=0 to n-2min=ifor j= i+1 to n-1if eleminelej min=jswap（elei,elemin） /交换图1、选择排序在不同数据规模

3、下排序所消耗的时间2、冒泡排序 代码 2： for i= 0 to n-1for j=0 to n-1-iif ajaj+1 swap(aj,aj+1) /交换图2、冒泡排序在不同数据规模下排序所消耗的时间3、合并排序代码 3：Merge(ele1.n,left,right)middle=(left+right)/2if right1eft+1Merge(ele,left,middle)Merge(ele,middle+1,right)ITeft r right iTeftwhile l=middle&r=right /两组分别一一比较，数据小的放入 eleif elelmiddle&r=r/

4、只剩一组还有剩余的时，将剩下的按顺序放入elei+=sr+while lrightelei+=sl+;图3、合并排序在不同数据规模下排序所消耗的时间4、快速排序代码 4：quick(ele0.n-1,left,right)if lr/找到一个比 x 小的数之后交换到前面的部分l left r right x elel; while lrwhile lr & x=elerr-if lr elel eler l+while lelel/与上面相反ll+if lr eler elel r- elel x;quick(ele,left,l-1) / 递归调用 quick(ele,l+1,right)图

5、4、快速排序在不同数据规模下排序所消耗的时间5、插入排序代码 5：for i=lf n-1if eleitempelej+1 elejelej+1 temp图5、插入排序在不同数据规模下排序所消耗的时间三实验分析选择排序：图 6、由图 1 数据整合而成的折线图为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了 一些调整，得到的平均数据依旧是以20 组数据样本取平均数算 （如下表 1、图 7 所示 ： （由于图片占空间大且表达不直白，我将所得数据做成表格分析，下同）数据规模：1000020000300004000050000耗时（ms）158634142425413

6、953表1、选择排序在不同数据规模下排序所消耗的时间图7、由表1数据整合而成的折线图图形上：形状基本符合小（二次增长）丫-口 r数据上：我们发现当数据规模增大两倍时：当数据规模增大两倍时：1000020000： 158*22=632 6341000030000： 158*32=142214242000040000：634*22=25362541其他倍数也可得到类似的结果。结论：我们发现，由于时间复杂度是。（小）并且该排序的主要操作是比较操作，当数据规模扩大 n倍时，相应的在时间的消耗上会扩大厲倍，同时我们发现，理论上乘以厲后的数据普遍会 略小于实际数据，这主要原因可能是除了比较操作之外，赋值操

7、作也随着n的增加逐渐增大， 并且会在时间上体现出来，此外轻微的误差可能是数据的差异造成或者电脑等其他因素造成。冒泡排序：为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以 20 组数据样本取平均数算得（如下表 2、图 9所示 ：数据规模：1000020000300004000050000耗时（ms）2841266289952138075表2、冒泡排序在不同数据规模下排序所消耗的时间图9、由表2数据整合而成的折线图图形上：形状基本符合小（二次增长）M TE r数据上：我们发现当数据规模增大两倍时：当数据规模增大两倍时：10000-20

8、000： 284*22=1136工1266（误差 130） 10000-30000： 284*32=2556工2899（误差 343）20000-40000:1266*22=5064工 5313 （误差 149） 其他倍数也可得到类似的结果。结论：我们发现，虽然时间复杂度是o （少），但当数据规模扩大n倍时，并没有相应的在时间的消 耗上扩大m倍，而是多于n2，同时我们发现，这个误差会随着数据规模的扩大而扩大，这 主要原因是除了比较操作之外，赋值操作也随着n的增加逐渐增大，而且事实证明在数据比 较极端的情况下，赋值操作已经不能忽略不计（这里的赋值操作发生在数据交换时所需要的 操作），最糟糕的情况

9、是每次比较就要进行三次的赋值操作，与此相比，电脑等其他因素造 成轻微的误差可以忽略不计。合并排序：图10、由图 3数据整合而成的折线图为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以20 组数据样本取平均数算得（如下表3、图 11所示：数据规模：100000200000300000400000500000耗时（ms）245176105132表3、合并排序在不同数据规模下排序所消耗的时间图形上：形状基本符合n（线性增长）rm r当数据规模增大两倍时：1000030000： 24*3log3=7276数据上： 我们发现当数据规模增大两

10、倍时：1000020000：24*2log2=48512000040000：51*2log22=102105其他倍数也可得到类似的结果。结论：我们发现，由于时间复杂度是o （nlog2n）,当数据规模扩大n倍时，相应的在时间的消耗上 会扩大nlog2n倍，同时我们发现，理论上乘以nlog2n后的数据普遍会略小于实际数据，这 主要原因快速排序需要递归调用，递归调用需要花费额外的时间,此外轻微的误差可能是数据的差异造成或者电脑等其他因素造成。快速排序：快速排序+Q Q0Q j7仃门C QCCCC百门门门仃只门（ICC 1门门仃门门1 7门门1口一一快谨排序图12、由图 4数据整合而成的折线图为了更

11、清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了 一些调整，得到的平均数据依旧是以20 组数据样本取平均数算得（如下表4、图 13 所示 ：数据规模：100000200000300000400000500000耗时（ms）1736567698表4、快速排序在不同数据规模下排序所消耗的时间Q-OOB0C-J20O图13、由表 4数据整合而成的折线图100000 200000 3000004000aa 500000 600000快速排序十快速排序图形上：形状基本符合n（线性增长）丫-口 r数据上：我们发现当数据规模增大两倍时： 当数据规模增大两倍时：10000-20000

12、：17*2log2=343610000-30000： 17*3log3562000040000：26*2log2=5456其他倍数也可得到类似的结果。结论：我们发现，由于时间复杂度是o （nlog2n）,当数据规模扩大n倍时，相应的在时间的消耗上 会扩大nlog2n倍，同时我们发现，理论上乘以nlog2n后的数据普遍会略小于实际数据，这 主要原因快速排序需要递归调用，递归调用需要花费额外的时间,此外轻微的误差可能是数 据的差异造成或者电脑等其他因素造成。插入排序：为了更清晰的看到排序的数据规模与排序所需时间之间的影响，我将实验的数据规模进行了一些调整，得到的平均数据依旧是以20组数据样本取平均

13、数算得（如下表5、图15所示：数据规模：1000020000300004000050000耗时（ms）8031972312832011表5、插入排序在不同数据规模下排序所消耗的时间图15、由表 5数据整合而成的折线图图形上：形状基本符合厲（二次增长）卜口 r数据上： 我们发现当数据规模增大两倍时：当数据规模增大两倍时：10000-20000： 80*22=320 31910000-30000： 80*32=720 7232000040000：3 1 9*22=12 761283其他倍数也可得到类似的结果。结论：我们发现，由于时间复杂度是。（少），当数据规模扩大n倍时，相应的在时间的消耗上会扩

14、大 n2 倍，理论上，如果数据太具有特殊性，那此算法被影响的程度会比较大，他的的比较 次数可以从线性次数，到n2次，赋值次数也可能由常数次变成n2总的来说，受数据影响较 大，由于我实验基数少，所以无法得出此结论。314357061绘昌区图 16、由图 6、8、10、12、14 整合而来将五种排序的实验汇总在一起，如下图16 所示300002500035QQQ2000015-627+冒泡排帛15000十合拜排序*快速排序100QO十插人排帛-2DDDD2CQOO 斗 GOTO 60CCG10QQDD 12GCCC从图中以及之前的分析中我们可以得到以下结论时间复杂度同样为o(n2)的选择、冒泡和合

15、并排序，在数据处理上相差的也比较大， 其中1、冒泡排序平均耗时最多，其主要原因是：冒泡排序在比较次数上达到了 o (n2),但 这种排序同时也受交换次数的影响，而且最多时间复杂度也是o (n2)。如此，同样是o (n2), 但冒泡排序的二次项系数会比另外两个大不少，所以最为耗时。 2、选择排序和插入排序 相比较，插入排序更快，其原因是：选择排序需要从序列中找到当前最大或最小的值才能进 行排序，因此每次都需要与子序列中的全部元素进行比较。而插入排序无需比较子序列全部 元素，只需要找到当前序列第一个比自己大或小的元素，将自身插入到其前一个位置即可。3、同样是o (nlog2n)但快速排序更快：快速

16、排序出现最差的情况并不是由于输入数据，而 是选取到的随机数本身，选到极端的情况非常小，所以对于绝大部分数据而言都是能达 o (nlog2n),而合并排序需要赋值的语句还是较多，受输入数据的影响比快排大，所以当数 据规模较大时，不受输入数据影响的快速排序更快四实验心得本次实验虽然花费很大的心思，但确实让我对这几种排序的认识更加深刻，同样的数据， 排序的时间可以相差如此之大，这可能会改变我每次都使用冒泡排序的这一习惯，同时，对 算法的优良性不同而导致的结果差异之大，感觉到好的算法是多么的重要，当然合理利用算 法也是不可忽视的。这次实验虽然花了很大精力，却收获累累。注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。2、教师批改学生实验报告时间应在学生提交实验报告时间后 10 日内。