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

将五种排序的实验汇总在一起，如下图16所示

图16、由图6、8、10、12、14整合而来

从图中以及之前的分析中我们可以得到以下结论

时间复杂度同样为o（n2）的选择、冒泡和合并排序，在数据处理上相差的也比较大，其中1、冒泡排序平均耗时最多，其主要原因是：冒泡排序在比较次数上达到了o（n2），但这种排序同时也受交换次数的影响，而且最多时间复杂度也是o（n2）。如此，同样是o（n2），但冒泡排序的二次项系数会比另外两个大不少，所以最为耗时。 2、选择排序和插入排序相比较，插入排序更快，其原因是：选择排序需要从序列中找到当前最大或最小的值才能进行排序，因此每次都需要与子序列中的全部元素进行比较。而插入排序无需比较子序列全部元素，只需要找到当前序列第一个比自己大或小的元素，将自身插入到其前一个位置即可。3、同样是o（nlog2n）但快速排序更快：快速排序出现最差的情况并不是由于输入数据，而是选取到的随机数本身，选到极端的情况非常小，所以对于绝大部分数据而言都是能达o（nlog2n），而合并排序需要赋值的语句还是较多，受输入数据的影响比快排大，所以当数据规模较大时，不受输入数据影响的快速排序更快

四．实验心得

本次实验虽然花费很大的心思，但确实让我对这几种排序的认识更加深刻，同样的数据，排序的时间可以相差如此之大，这可能会改变我每次都使用冒泡排序的这一习惯，同时，对算法的优良性不同而导致的结果差异之大，感觉到好的算法是多么的重要，当然合理利用算法也是不可忽视的。这次实验虽然花了很大精力，却收获累累。

指导教师批阅意见： 成绩评定： 指导教师签字： 年 月 日 备注：

注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。

2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。