- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
北京邮电大学信息与通信工程学院
数据结构实验报告
实验名称:实验四排序——题目一
学生姓名:
班级:
班内序号:
学号:
日期:2012年12月15日
1.实验要求
使用简单数组实现下面各种排序算法,并进行比较。
排序算法:
1、插入排序
2、希尔排序
3、冒泡排序
4、快速排序
5、简单选择排序
6、堆排序(选作)
7、归并排序(选作)
8、基数排序(选作)
9、其他
要求:
1、测试数据分成三类:正序、逆序、随机数据
2、对于这三类数据,比较上述排序算法中关键字的比较次数和移动次数(其中关键字交换计为3次移动)。
3、对于这三类数据,比较上述排序算法中不同算法的执行时间,精确到微秒(选作)
4、对2和3的结果进行分析,验证上述各种算法的时间复杂度
编写测试main()函数测试线性表的正确性。
2.程序分析
首先,题目要求测试不同的数据,所以可以手动输入待排序元素。其次,由于对一组数据要求用不同的排序算
法来处理,所以需要一个复制函数把排序前的无序数组寄存出去,为下一次排序做准备。再次,由于每次排序后都
需要把排序后的结果打印出来,代码是一样的,根据相同的代码可以封装成一个函数的思想,所以还需增加一个打
印函数。最后,由于题目中要求计算代码的执行时间精确到微妙级,而c++库函数中的clock()函数等只能精确
到毫秒级,故需调用微软公司在其多媒体Windows中提供了精确定时器的底层API支持,本实验中调用
queryperformancefrequency和queryperformancecounter函数即可满足精确到微妙级的要求。
2.1存储结构
本程序采用简单数组来储存输入的待排序数组。
第1页
北京邮电大学信息与通信工程学院
2.2关键算法分析
2.2.1插入排序算法
插入排序的思想是:每次从无序区取一元素将其添加到有序区中。
C++描述如下,其中形参r[]为待排序数组,n为待排序元素个数
2.2.2希尔排序算法
希尔排序是一种缩小增量排序的算法,首先将待排序元素集按照一定间隔分成多个子集,分别对这些子集进
行直接插入排序,整个序列部分有序。然后缩小间隔,在进行直接插入排序,直到间隔为1,此时,整个序列已全
部有序。其c++描述如下:
第2页
北京邮电大学信息与通信工程学院
2.2.3冒泡排序
冒泡排序的思想是:两两比较相邻的元素,如果反序,则交换次序,直到没有反序的元素为止。
在此思想指导下①首先将待排序元素划分为有序区和无序区,初始状态有序区为空,无序区所有待排序素;
②对无序区从前向后依次将相邻元素关键码进行比较,若反序,则交换
③重复执行②直到无序区中没有元素。
第3页
北京邮电大学信息与通信工程学院
2.2.4快速排序算法
2,2,4,1一趟快速排序算法自然语言描述如下
①选取区间第一个元素作为轴值
②读取区间首尾坐标,并将其左右侧待比较元素
③右侧扫描:从后向前找到第一个比轴值小的元素,和左侧待比较元素交换(左侧第一个带比较元素为轴值)
④左侧扫描:从前向后找到第一个比轴值大的元素,和右侧待比较元素交换
⑤重复②③,直到左右两侧带比较元素的坐标相等
其c++描述如下
第4页
北京邮电大学信息与通信工程学院
2.2.4.2完整的快速排序算法如下:
2.2.5选择排序算法
选择排序自然语言描述如下:
①在r[1]~r[n]待排序元素序列中选出最小记录,将其与第一个元素r[n]交换
②在r[2]~r[n]待排序元素序列中选出最小记录,将其与第一个元素r[i]交换
…………
③直至r[n-1]~r[
文档评论(0)