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

《数据结构课程设计---多种排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计说明书课程名称：数据结构课程设计设计题目：多种排序院系：计算机科学与信息工程学院学生姓名：徐思勇学号：200903010016专业班级：09级计科班（应用）指导教师：孙高飞2011年6月8日课程设计任务书设计题目多种排序学生姓名徐思勇所在院系计科院专业、年级、班09级计科应用班设计要求：利用随机函数产生N个随机整数（10000以上），对这些数进行多种方法进行排序学生应完成的工作：1)采用如下六种方法实现上述问题求解：插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其

2、中两种较快的方法。并将数据序列和不同的查找算法的性能结果记录入txt文件。参考文献阅读：1)清华大学出版社《数据结构》编著：严蔚敏吴伟民2)清华大学出版社《C程序设计教程》编著：谭浩强工作计划：1)两天时间讨论框架，由组长分配任务。2)三人合作每人解决两种排序方法由组长组合起来。任务下达日期：2011年6月7日任务完成日期：2001年6月13日指导教师（签名）：学生（签名）：李志祥多种排序摘要：本次课程设计所要求的排序方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序，基本上将我们学习过的排序方法都囊括在内，可以说这次课程设计是对我们学过的排序算

3、法的一个总结和对比。通过实验中各种排序方法所用的时间对比，可以让我们对每种排序方法的性能有一个清晰的认识，有利于我们以后在做某些程序时更好的选择最好的排序方法。关键词：(1)六种排序①插入排序②希尔排序③起泡排序④快速排序⑤选择排序⑥堆排序(2)排序方法的性能关键问题:核心问题:排列组合数据模型（逻辑结构）：30000个随机数存储结构:保存在不同的文件核心算法:直接插入、直接选择、冒泡、快速排序、堆排序的算法输入数据:初始化数组：rand()%50000+1输出数据：排序内容到文件，排序所用时间目录1.设计背景………………………………………………………51.

4、1总设计………………………………………………………52.设计方案………………………………………………………52.1设计思想……………………………………………………52.2主要思想和流程图…………………………………………63方案实施………………………………………………………73.1程序的实现…………………………………………………73.2主要源代码及说明…………………………………………74结果与结论……………………………………………………204.1运行主界面…………………………………………………204.2各种排序方法运行结果……………………………………204.3

5、运行结论……………………………………………………245收获与致谢……………………………………………………246参考文献………………………………………………………247附件………………………………………………………241.设计背景1.1总设计分别实现直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、堆排序的算法。从时间的角度来分析各种排序的性能。通过测试多组数据来掌握各种排序的方法及适用场合，并能在解决实际问题灵活运用。在编写代码的时候，有以下几个问题：（1）建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。（

6、2）分别实现直接插入排序、希尔排序、直接选择排序、冒泡排序、快速排序、堆排序的算法。（3）通过冒泡排序法来测试每组数据用那种排序算法最优。2.设计方案2.1设计思想建立一个主函数，在主函数中要有菜单界面，和输入功能键相应执行的功能。并且要求能循环使用系统。分别实现直接插入、直接选择、冒泡、快速排序、堆排序的算法。（1）直接插入排序的基本思想是基于插入，开始假定第一个记录有序，然后从第二个记录开始，依次插入到前面有序的子文件中。即将记录a[i](2<=i<=n)插入到有序子序列a[1..i-1]中，使记录的有序序列从a[1..i-1]变为a[1..i]，最终使

7、整个文件有序。共进行n-1趟插入。最坏时间复杂度是0(n2)，平均时间复杂度是0(n2)，空间复杂度是O(1)，是稳定排序。（2）希尔排序的基本思想是基于分组，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

8、[i..n]的n-i+1记录中选出关键字最小的记录，