发布时间 : 星期日 文章常用排序算法课程设计报告更新完毕开始阅读9489155577232f60ddcca1e0
xxxxx《xxxxx》课程设计报告
重庆科技学院 课程设计任务书
设计题目：常用排序算法的比较 学生姓名 课程名称 地 点 设计内容及要求 *** 数据结构课程设计 专业班级 ***** 计算机基础自主学习中心 起止时间 2011.11.16-12.5 利用随机函数产生N个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。 要求： 1) 分别采用的排序算法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，实现这批数据的排序，并把排序后的结果保存在不同的文件中。 2) 统计每一种排序算法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的算法。 注：在完成以上数据的同时，还能采用其它的排序算法，适当加分。 设计 测试数据要求：随机产生1000 个以上的随机整数，并保存在文本文件中。排序后参的数据和所需的时间也保存在各自的txt文件中。 数 进度 要 求 参1．严蔚敏 吴伟民 著， 数据结构，清华大学出版社，2007.3 考2．李春葆 著，数据结构教程，清华大学出版社，2005.1 资3. Richard F.Gilberg Behrouz A.Forouzan, 数据结构的C++伪码实现（英文版），人民邮料 电出版社，2002.1 其它 说１.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。２.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计明 内容、参数、要求等方面应有所区别。 教研室主任： 指导教师：
2011年 11月 16日
xxxxx《xxxxx》课程设计报告
摘要
排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。
本报告将描述如何利用随机函数产生N个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。
关键词：排序算法 数据结构 随机函数
I
xxxxx《xxxxx》课程设计报告
目录
摘要................................................................................................................................ I 1 设计内容和要求........................................................................................................ 1
1.1 设计内容......................................................................................................... 1 1.2 设计要求......................................................................................................... 1 2 需求分析.................................................................................................................... 2
2.1 直接插入排序............................................................................................... 2 2.2 希尔排序........................................................................................................ 2 2.3 快速排序:（递归和非递归） ...................................................................... 2 2.4 堆排序.............................................................................................................. 3 3 概要设计.................................................................................................................... 4
3.1 头文件........................................................................................................... 4 3.2 ADT .............................................................................................................. 4 3.3 各种操作函数：........................................................................................... 4 3.4 主函数............................................................................................................. 5 4 详细设计.................................................................................................................... 6
4.1 主函数............................................................................................................ 6 4.2 4.3 4.4 4.5 4.6 4.7 4.8
直接插入排序 .............................................................................................. 7 希尔排序 ...................................................................................................... 9 起泡排序 .................................................................................................... 10 快速排序 .................................................................................................... 11 选择排序 .................................................................................................... 13 堆排序 ........................................................................................................ 15 归并排序 .................................................................................................... 18
5 系统测试 ................................................................................................................. 21
5.1 系统操作....................................................................................................... 21 5.2 测试数据...................................................................................................... 23 6 总结.......................................................................................................................... 26 致谢.............................................................................................................................. 27 参考文献...................................................................................................................... 28
II
xxxxx《xxxxx》课程设计报告
1 设计内容和要求
1.1 设计内容
利用随机函数产生N个随机整数，采用多种方法对这些数进行排序，然后分析各自的所需的排序时间找出较快的排序算法。
1.2 设计要求
1) 分别采用的排序算法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序，实现这批数据的排序，并把排序后的结果保存在不同的文件中。
2) 统计每一种排序算法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的算法。
1