数据结构课程设计-排序综合报告

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

1、数学与计算机学院课程设计说明书课程名称:数据结构-课程设计课程代码:8404181题目:排序综合年级/专业/班:2009级软件工程四班学生姓名:学　　号:开始时间:2011年06月20日完成时间:2011年07月03日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总分（100）指导教师签名：年月摘要排序（sorting）是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的存储器的不同，可将排序方法分为两大类：

2、一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需要对外存进行访问的排序过程。内部排序又分为：插入排序、快速排序、选择排序、归并排序和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序；基数排序分为：多关键字排序和链式基数排序。本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质，排序的应用，排序的分类，利用C语言采用数组存储结构编程实现了本排序综合系统，该系统包含了几种常见的排序方法，有直接插入排

3、序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。关键字：内部排序，外部排序，排序，重新排列，关键字目录1需求分析11.1任务与分析11.2功能模块的划分11.2.1输入模块11.2.2选择排序方法模块11.2.3输出模块11.3排序模块分析21.3.1直接插入排序21.3.2希尔排序21.3.3冒泡排序21.3.4快速排序（递归和非递归）21.3.5简单排序31.3.6堆排序31.4系统需求分析规格说明书32开发及运行平台42.1windows操作系统42.2VC++6.043概要设计43.1程序结构框图43.2程序流程图53.3抽象数据类型定义53.4各种操

4、作函数：63.5主函数64详细设计74.1数据类型定义74.2主要模块内部设计74.2.1模块1—直接插入排序模块设计74.2.2模块2—希尔排序模块设计74.2.3模块3—冒泡排序模块设计84.2.4模块4—非递归快排模块设计94.2.5模块5—递归快排模块设计104.2.6模块6—简单排序模块设计104.2.7模块7—堆排序模块设计105调试分析125.1调试过程125.2性能分析126测试分析136.1测试用例136.2测试结果137结论15参考文献16附录171需求分析1.1任务与分析任务：机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求：1)至少采用

5、三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。分析：前面分析了排序的种类以及过程，因此，本系统实现了几种常用的排序方法，包括：直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。1.2功能模块的划分1.2.1输入模块利用随机函数产生N个数（20000以上），产生的数据个数有用户自己输入。1.2.2选择排序方法模块在菜单中通过键入相应的选项编号来选择采用何种

6、算法排序，包括的排序算法有：直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。1.2.3输出模块输出排序前的，或者排序后的数据元素到屏幕上显示，并且输出一某一种算法排序后的数据元素到文件中保存。—24—1.3排序模块分析1.3.1直接插入排序思路：设有一组关键字{K1,K2,…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列,让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列.1.3.2希尔排序思路

7、：先取一个正整数d1(d1=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=11.3.3冒泡排序思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3