精品文档---下载后可任意编辑HUNANUNIVERSITY课程实习报告题 目: 排序算法的时间性能学生姓名 学生学号专业班级指导老师 李晓鸿 完 成 日 期精品文档---下载后可任意编辑设计一组实验来比较下列排序算法的时间性能 快速排序、堆排序、希尔排序、冒泡排序、归并排序(其他排序也可以作为比较的对象)要求 (1)时间性能包括平均时间性能、最好情况下的时间性能、最差情况下的时间性能等。 (2)实验数据应具有说服力,包括:数据要有一定的规模(如元素个数从 100 到 10000);数据的初始特性类型要多,因而需要具有随机性;实验数据的组数要多,即同一规模的数组要多选几种不同类型的数据来实验。实验结果要能以清楚的形式给出,如图、表等。 (3)算法所用时间必须是机器时间,也可以包括比较和交换元素的次数。 (4)实验分析及其结果要能以清楚的方式来描述,如数学公式或图表等。(5)要给出实验的方案及其分析。说明 本题重点在以下几个方面:理解和掌握以实验方式比较算法性能的方法;掌握测试实验方案的设计;理解并实现测试数据的产生方法;掌握实验数据的分析和结论提炼;实验结果汇报等。一、需求分析 (1) 输入的形式和输入值的范围:本程序要求实现各种算法的时间性能的比较,由于需要比较的数目较大,不能手动输入,于是采纳系统生成随机数。用户输入随机数的个数 n,然后调用随机事件函数产生 n 个随机数,对这些随机数进行排序。于是数据为整数 (2) 输出的形式:输出在各种数目的随机数下,各种排序算法所用的时间和比较次数。 (3) 程序所能达到的功能:该程序可以根据用户的输入而产生相应的随机数,然后对随机数进行各种排序,根据排序进行时间和次数的比较。(4)测试数据:略二、概要设计1.抽象数据类型ADT List 数据对象 D={ ai | ai ElemSet, i=1,2,...,n, n≥0 }∈数据关系 R1={
|ai-1 ,aiD, i=2,...,n }∈基本操作 virtual void clear() = 0;bool insert(const Elem&) = 0;bool append(const Elem&) = 0;lbool remove(Elem&) = 0;void setStart() = 0; void setEnd() = 0;void prev() = 0;void next() = 0;int leftLength() const = 0;int rightLength() const = 0;bool setPos(int pos) = 0;bool getValue(Elem&) const = 0;void print() const = 0;2.程序的流程(1) 输入模块:输入要排序的数的数量 n(2) 处理模块...