数据结构课程设计---多种排序.doc

课 程 设 计 说 明 书 课程名称： 数据结构课程设计 设计题目： 多种排序 院 系： 计算机科学与信息工程学院 学生姓名： 徐思勇 学 号： 200903010016 专业班级： 09级计科班（应用） 指导教师： 孙高飞 2011年 6 月 8 日课 程 设 计 任 务 书 设计题目 多种排序 学生姓名 徐思勇 所在院系 计科院 专业、年级、班 09级计科应用班 设计要求： 利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序 学生应完成的工作： 采用如下六种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序。 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。并将数据序列和不同的查找算法的性能结果记录入txt文件。 参考文献阅读： 清华大学出版社《数据结构》 编著：严蔚敏 吴伟民 清华大学出版社《C程序设计教程》 编著：谭浩强 工作计划： 两天时间讨论框架，由组长分配任务。 三人合作每人解决两种排序方法由组长组合起来。 任务下达日期： 2011年 6月 7 日 任务完成日期： 2001年 6月 13日 指导教师（签名）： 学生（签名）： 李志祥 多种排序 摘 要：本次课程设计所要求的排序方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序，基本上将我们学习过的排序方法都囊括在内，可以说这次课程设计是对我们学过的排序算法的一个总结和对比。通过实验中各种排序方法所用的时间对比，可以让我们对每种排序方法的性能有一个清晰的认识，有利于我们以后在做某些程序时更好的选择最好的排序方法。 关键词：(1)六种排序 ①插入排序 ②希尔排序 ③起泡排序 ④快速排序 ⑤选择排序 ⑥堆排序 (2) 排序方法的性能 关键问题: 核心问题: 排列组合 数据模型（逻辑结构）：30000个随机数 存储结构: 保存在不同的文件 核心算法: 直接插入、直接选择、冒泡、快速排序、堆排序的算法 输入数据: 初始化数组：rand()%50000+1 输出数据：排序内容到文件，排序所用时间 目 录 1. 设计背景………………………………………………………5 1.1 总设计………………………………………………………5 2.设计方案………………………………………………………5 2.1设计思想……………………………………………………5 2.2主要思想和流程图…………………………………………6 3方案实施………………………………………………………7 3.1程序的实现…………………………………………………7 3.2主要源代码及说明…………………………………………7 4结果与结论……………………………………………………20 4.1运行主界面…………………………………………………20 4.2各种排序方法运行结果……………………………………20 4.3 运行结论……………………………………………………24 5收获与致谢……………………………………………………24 6参考文献………………………………………………………24 7 附件 ………………………………………………………24 1. 设计背景 1.1总设计 分别实现直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题： （1）建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。 （2）分别实现直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、堆排序的算法。 （3）通过冒泡排序法来测试每组数据用那种排序算法最优。 2.设计方案 2.1 设计思想 建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。分别实现直接插入、直接选择、冒泡、快速排序、堆