排序综合报告.doc

数学与计算机学院 课程设计说明书 课 程 名 称: 数据结构-课程设计 课 程 代 码: 题 目: 排序综合 年级/专业/班: 2009级软件工程四班 学 生 姓 名: 学　　 号: 开 始 时 间: 2011 年 06 月 20 日 完 成 时 间: 2011 年 07 月 03 日 课程设计成绩： 学习态度及平时成绩（30） 技术水平与实际能力（20） 创新（5） 说明书撰写质量（45） 总 分（100） 指导教师签名： 年 月  摘 要 排序（sorting）是计算机程序设计的一种重要操作，他的功能是将一组任意顺序数据元素（记录），根据某一个（或几个）关键字按一定的顺序重新排列成为有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的存储器的不同，可将排序方法分为两大类：一类是内部排序，指的是待排序的记录存放在计算机随机存储器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需要对外存进行访问的排序过程。 内部排序又分为：插入排序、快速排序、选择排序、归并排序和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序；基数排序分为：多关键字排序和链式基数排序。 本次课程设计就是内部排序中的几个常用排序方法。分析了排序的实质，排序的应用，排序的分类，利用C语言采用数组存储结构编程实现了本排序综合系统，该系统包含了几种常见的排序方法，有直接插入排序、希尔排序、冒泡排序、非递归的快速排序、递归的快速排序、简单排序、堆排序。 关键字：内部排序，外部排序，排序，重新排列，关键字 目 录 1需求分析 1 1.1 任务与分析 1 1.2 功能模块的划分 1 1.2.1 输入模块 1 1.2.2 选择排序方法模块 1 1.2.3 输出模块 1 1.3 排序模块分析 2 1.3.1 直接插入排序 2 1.3.2 希尔排序 2 1.3.3 冒泡排序 2 1.3.4 快速排序（递归和非递归） 2 1.3.5 简单排序 3 1.3.6 堆排序 3 1.4 系统需求分析规格说明书 3 2开发及运行平台 4 2.1 windows操作系统 4 2.2 VC++6.0 4 3 概要设计 4 3.1 程序结构框图 4 3.2 程序流程图 5 3.3 抽象数据类型定义 5 3.4 各种操作函数： 6 3.5 主函数 6 4 详细设计 7 4.1 数据类型定义 7 4.2 主要模块内部设计 7 4.2.1 模块1 — 直接插入排序模块设计 7 4.2.2 模块2 — 希尔排序模块设计 7 4.2.3 模块3 — 冒泡排序模块设计 8 4.2.4 模块4 — 非递归快排模块设计 9 4.2.5 模块5 — 递归快排模块设计 10 4.2.6 模块6 — 简单排序模块设计 10 4.2.7 模块7 — 堆排序模块设计 10 5 调试分析 12 5.1 调试过程 12 5.2 性能分析 12 6 测试分析 13 6.1 测试用例 13 6.2 测试结果 13 7 结论 15 参考文献 16 附 录 17 1需求分析 1.1 任务与分析 任务： 机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。要求： 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。…….,Kn},排序开始变认为K1是一个有序的序列,让K2插入到表长为1的有序序列,使之成为一个表长为2的有序序列, 让K3插入到表长为2的有序序列,使之成为一个表长为3的有序序列,依次类推,最后让Kn插入上述表长为n-1的有序序列,得到一个表长为n的有序序列. 1.3.2 希尔排序 思路：先取一个正整数d1(d1n),把全部记录分成d1个组,所有距离为d1的倍数的记录看成是一组,然后在各组内进行插入排序;然后取d2(d2d1),重复上述分组和排序操作,直到取di=1(=1),即所有记录成为一个组为此.一般选d1约为n/2,d2为d1/2,…….,di=1 1.3.3 冒泡排序 思路：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第