算法分析与复杂性理论 实验报告 几个排序的对比

2、 以待排序数组的大小n为输入规模，固定n，随机产生20组测试样本，统计不同排序算法在20个样本上的平均运行时间； 3、 分别以n=10, n=100, n=1000, n=10000, n=100000，重复2的实验； 对于选择排序，固定n的大小为100。 设置time1和time2来统计时间，主函数中部分代码如下 实验截图如下图所示： 测试了20组规模为100的数据平均耗时为20毫秒。 当n=10时，因数据太少，显示时间为0。 当 n=100时，耗时50毫秒。 同理当n规模增大时可得下表（表中的时间单位为秒）： N的规模 选择排序 冒泡排序 归并排序 快速排序 插入排序 100 1000 10000 100000 0.05 3 452 34269 0.05 9 725 55812 0.3 1 81 4390 0 1 12 142 0.05 2 294 28208 图表见下页 数据处理分析： 实验结论： 五种排序方法都是很优秀的排序方法，根据需要选择相应的排序 对于一组无序的数，当n的规模越大，快速排序的平均效率越高，冒泡排序的平均效率越低。 指导教师批阅意见： 成绩评定： 指导教师签字： 年 月 日 备注： 注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。 2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。