深 圳 大 学 实 验 报 告

课程名称： 算法分析与复杂性理论

实验项目名称： 实验一 排序算法性能分析

学院： 计算机与软件学院

专业： 软件工程

指导教师： 杨烜

报告人：文成 学号：2150230509 班级： 15级软工学术型

实验时间： 2015-10-20

实验报告提交时间： 2015-10-24

教务部制

实验目的与要求： 实验目的 1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理 2. 掌握不同排序算法时间效率的经验分析方法，验证理论分析与经验分析的一致性。 实验概述 排序问题要求我们按照升序排列给定列表中的数据项，目前为止，已有多种排序算法提出。本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理，并进行代码实现。通过对大量样本的测试结果，统计不同排序算法的时间效率与输入规模的关系，通过经验分析方法，展示不同排序算法的时间复杂度，并与理论分析的基本运算次数做比较，验证理论分析结论的正确性。 提交材料 1. 代码：排序算法及注释 2. 实验报告：按照实验报告要求完成完整的实验报告。 实验内容： 1、实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法； 2、以待排序数组的大小n为输入规模，固定n，随机产生20组测试样本，统计不同排序算法在20个样本上的平均运行时间； 3、分别以n=10, n=100, n=1000, n=10000, n=100000，重复2的实验； 4、画出不同排序算法在20个随机样本的平均运行时间与输入规模n的关系，如下图1所示。 图1. 时间效率与输入规模n的关系图 5、画出理论效率分析的曲线和实测的效率曲线，注意：由于实测效率是运行时间，而理论效率是基本操作的执行次数，两者需要进行对应关系调整。调整思路：以输入规模为10000的数据运行时间为基准点，计算输入规模为其他值的理论运行时间，画出不同规模数据的理论运行时间曲线，并与实测的效率曲线进行比较。经验分析与理论分析是否一致？如果不一致，请解释存在的原因。 实验过程及内容： （实验代码已作为附件提交，名为“算法实验一.cpp”） 1、 实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法； 部分排序代码截图如下，详细代码可见源文件。 在主函数中创建一个初始的无序序列{1,3,5,7,9,2,4,6,8} 然后调用各个方法进行排序 如下所示，编写主函数进行测试：