[排序综合]
成都吃喝网 www.cdchw.com
学生姓名： 0 0 学生学号： 0
院（系）： 计算机学院 年级专业： 0 指导教师： 0
二〇10年6 月
1
题 目 排序综合 1、课程设计的目的 1) 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。 2) 使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 3） 使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等） [问题描述]：用程序实现多种排序算法 [基本要求]：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求： 1) 至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 如果采用4种或4种以上的方法者，可适当加分。 3、主要参考文献 ［1］刘大有等，《数据结构》（C语言版），高等教育出版社 ［2］严蔚敏等，《数据结构》（C语言版），清华大学出版社 ［3］William Ford，William Topp，《Data Structure with C++》清华大学出版社 ［4］苏仕华等，数据结构课程设计，机械工业出版社 4、课程设计工作进度计划 第1天 完成方案设计与程序框图 第2、3天 编写程序代码 第4天 程序调试分析和结果 第5天 课程设计报告和总结 指导教师（签字） 教研室意见： 年 月 日 学生（签字）： 接受任务时间： 年 月 日 注：任务书由指导教师填写。
日期 年 月 日 课程设计（论文）指导教师成绩评定表 题目名称 评分项目 工作 表现 20% 01 02 03 04 05 06 07 08 学习态度 科学实践、调研 课题工作量 综合运用知识的能力 应用文献的能力 设计（实验）能力，方案的设计能力 计算及计算机应用能力 对计算或实验结果的分析能力（综合分析能力、技术经济分析能力） 插图（或图纸）质量、篇幅、设计（论文）规范化程度 设计说明书（论文）质量 创新 分值 6 7 7 10 5 5 5 10 排序综合 得分 评价内涵 遵守各项纪律，工作刻苦努力，具有良好的科学工作态度。 通过实验、试验、查阅文献、深入生产实践等渠道获取与课程设计有关的材料。 按期圆满完成规定的任务，工作量饱满。 能运用所学知识和技能去发现与解决实际问题，能正确处理实验数据，能对课题进行理论分析，得出有价值的结论。 能独立查阅相关文献和从事其他调研；能提出并较好地论述课题的实施方案；有收集、加工各种信息及获取新知识的能力。 能正确设计实验方案，独立进行装置安装、调试、操作等实验工作，数据正确、可靠；研究思路清晰、完整。 具有较强的数据运算与处理能力；能运用计算机进行资料搜集、加工、处理和辅助设计等。 具有较强的数据收集、分析、处理、综合的能力。 能力 水平 35% 成果 质量 45% 09 10 11 5 30 10 符合本专业相关规范或规定要求；规范化符合本文件第五条要求。 综述简练完整，有见解；立论正确，论述充分，结论严谨合理；实验正确，分析处理科学。 对前人工作有改进或突破，或有独特见解。 成绩 指导教师评语 指导教师签名： 年 月 日
- 2 -
2
摘 要
数据结构是由数据元素依据某种逻辑联系组织起来的。对数据元素
间逻辑关系的描述称为数据的逻辑结构；数据必须在计算机内存储，数据的存储结构是数据结构的实现形式，是其在计算机内的表示；此外讨论一个数据结构必须同时讨论在该类数据上执行的运算才有意义。在许多类型的程序的设计中，数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。
关键字：数据结构；算法比较；比较次数；时间复杂度
- 3 - 3
目录
摘要 .............................................................. 1 1概要 ............................................................ 4
1.1设计目的 ............................................................... 4 1.2预期目标 ............................................................... 5
2排序算法 ........................................................ 7
2.1各排序算法的特点 ....................................................... 8 2.1.1冒泡排序 ........................................................... 8 2.1.2直接插入排序 ....................................................... 9 2.1.3简单选择排序 ....................................................... 9 2.1.4快速排序 ........................................................... 9 2.1.5希尔排序 ........................................................... 9 2.1.6堆排序 ............................................................. 9 2.2各算法的比较方法 ...................................................... 10
3流程图及详细算法 ................................................ 10
3.1流程图 ................................................................ 11 3.2流程图模块说明 ........................................................ 11 3.3可排序表的抽象数据类型定义 ............................................ 11 3.4程序代码 .............................................................. 11 3.4.1函数声明 .......................................................... 11 3.4.2六种排序函数代码 .................................................. 12 3.4.3排序算法的选择 .................................................... 17 3.4.4主函数程序代码 .................................................... 17
4运行结果 ....................................................... 18
4.1调试分析 .............................................................. 19 4.2输入输出 .............................................................. 20 4.3排序算法的评价 ........................................................ 23
5结束语 ......................................................... 25 参考文献 ......................................................... 24
- 4 - 4