实验 1 排序算法性能分析
一、实验目的
1. 掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理
2. 掌握不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
二、实验概述
排序问题要求我们按照升序排列给定列表中的数据项,目前为止,已有多种排序算法提
出。本实验要求掌握选择排序、冒泡排序、合并排序、快速排序、插入排序算法原理,并进
行代码实现。通过对大量样本的测试结果,统计不同排序算法的时间效率与输入规模的关系,
通过经验分析方法,展示不同排序算法的时间复杂度,并与理论分析的基本运算次数做比较,
验证理论分析结论的正确性。
三、实验内容。
1、实现选择排序、冒泡排序、合并排序、快速排序、插入排序算法;
2、以待排序数组的大小 n 为输入规模,固定 n,随机产生 20 组测试样本,统计不同排
序算法在 20
个样本上的平均运行时间;
3、分别以 n=10000, n=20000, n=30000, n=40000, n=50000 等等,重复 2 的实验,画出不
同排序算法在 20 个随机样本的平均运行时间与输入规模 n 的关系,如下图 1 所示;
图 1. 时间效率与输入规模 n 的关系图
4、画出理论效率分析的曲线和实测的效率曲线,注意:由于实测效率是运行时间,而
理论效率是基本操作的执行次数,两者需要进行对应关系调整。调整思路:以输入规模为
10000 的数据运行时间为基准点,计算输入规模为其他值的理论运行时间,画出不同规模数
据的理论运行时间曲线,并与实测的效率曲线进行比较。经验分析与理论分析是否一致?如
果不一致,请解释存在的原因。
- 1
- 2
前往页