多种排序课程设计说明书.docVIP

课 程 设 计 说 明 书 课程名称： 数据结构课程设计 设计题目： 多种排序 院 系： 计算机科学与信息工程学院 学生姓名： 李志祥 学 号： 4 专业班级： 09级计科班（应用） 指导教师： 孙高飞 2011年 6 月 8 日课 程 设 计 任 务 书 设计题目 多种排序 学生姓名 李志祥 所在院系 计科院 专业、年级、班 09级计科应用班 设计要求： 利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序 学生应完成的工作： 采用如下六种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序。 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。并将数据序列和不同的查找算法的性能结果记录入txt文件。 参考文献阅读： 清华大学出版社《数据结构》 编著：严蔚敏 吴伟民 清华大学出版社《C程序设计教程》 编著：谭浩强 工作计划： 两天时间讨论框架，由组长分配任务。 三人合作每人解决两种排序方法由组长组合起来。 任务下达日期： 2011年 6月 7 日 任务完成日期： 2001年 6月 13日 指导教师（签名）： 学生（签名）： 李志祥 （多种排序） 摘 要：本程序是基于屏幕的简单应用程序，整数数列排序，如何高效的排序一直困扰着我们本程序很好的解决了这个问题程序通过调试运行初步实现了目标，可以解决数学中的一些问题。 关键词：六种排序 ①插入排序 ②希尔排序 ③起泡排序 ④快速排序 ⑤选择排序 ⑥堆排序 目 录 1.设计背景………………………………………………………5 1.1大背景………………………………………………………5 1.2设计背景……………………………………………………5 2.设计方案………………………………………………………5 2.1设计思想……………………………………………………5 2.2主要思想和流程图…………………………………………6 3方案实施………………………………………………………7 3.1程序的实现…………………………………………………7 3.2程序代码……………………………………………………8 4结果与结论……………………………………………………17 4.1运行结果……………………………………………………17 4.2运行结论……………………………………………………24 5收获与致谢……………………………………………………25 6参考文献………………………………………………………25 1. 设计背景 1.1（大背景） 排序问题从古到今就有这个问题，也一直是数学方面的重要组成部分，随着生活的变化排序也成了日常生活的一部分。 1.2（设计背景） 本程序由我小组成员在一个星期的共同努力探讨设计而成，其中包含六种排序方法并且有使用时间对比各种方法的效率。 2.设计方案 2.1（设计思想） 建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。 直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录a[i](2=i=n)插入到有序子序列a[1..i-1]中，使记录的有序序列从a[1..i-1]变为a[1..i] ，最终使整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。 希尔排序的基本思想是基于分组，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-l…d2d1)，即所有记录放在同一组中进行直接插入排序为止。 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。 (6)堆排序基本思想