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

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

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输出模块输出排序前的，或者排序后的数据元素到屏幕上显示，并且输出一某一种算法排序后的数据元素到文件中保存。—26—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