1、 数据结构课程设计 设计说明书 内部堆排序算法的实现 学 生 姓 名 学 号 班 级 成 绩 指 导 教 师 课程设计任务书 20122013 学年第二学期 课程设计名称： 数据结构课程设计 课程设计题目： 内部堆排序算法的实现 完 成 期 限： 自 2013 年 3 月 4 日至 2013 年 3 月 15 日共 2 周 设计内容： 堆排序（heap sort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n 个关 键字序列 K1，K2，Kn 称为堆，当且仅当该序列满足如下性质(简称为堆性质)： kiK2i 且 kiK2i+1 或(2)KiK2i 且 kiK2i+1(1i n)
2、 若将此序列所存储的向量 R1n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质 的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 （即如果按照线性存储该树，可得到一个不下降序列或不上升序列） 。 本课程设计中主要完成以下内容： 1.设计堆排序算法并实现该算法。 2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。 3.寻找改进堆排序的方法。 基本要求如下： 1.程序设计界面友好；2.设计思想阐述清晰；3.算法流程图正确；4.软件测试方案合理、有效。 指导教师：曹阳 教研室负责人：申静 课程设计评阅 评语： 指导教师签名： 年 月 日 摘 要
3、 堆排序是直接选择排序法的改进。本课设以 VC+6.0 作为开发环境，C 语言作为编程语言，编程 实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。 关键词关键词：堆排序；C 语言；时间复杂度 目 录 1课题描述 . 1 2. 算法描述 . 2 2.1 堆排序描述 2 2.2 堆排序算法的图示 2 2.3 堆排序算法 5 3算法流程图 . 6 4代码实现 . 7 5. 算法分析 10 6. 测试 11 总结 . 12 参考文献 . 13 1 1 课题描述 查找是计算机的一项主要功能，为了查找方便，通常希望计算机中的表是按关键字是 有序的。因为有序的顺序表可采用查找效率较高的折半查找法，
4、而无序的表只能进行顺序 查找。 因此排序也就是计算机程序设计中的一种重要操作， 它的功能是将一个数据元素 （或 记录）的任意序列，重新排列成一个按关键字有序的序列。因此，学习和研究各种排序方 法是计算机工作者的重要课题之一。 本课题利用简单选择排序中的堆排序方法，通过对用户输入的可以组成堆的数据元素 建立大、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有 效地提高了查找的效率。 开发工具：vc+6.0 2 2. 算法描述 2.1 堆排序描述堆排序描述 堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。 堆的定义如下：n 个元素的序列（k1,k2,
5、,kn）当且仅当满足下关系时，称之为 堆。 kiK2i 且 kiK2i+1 或(2)KiK2i 且 kiK2i+1(1i n) 若将和此程序对应的一维数组看成是一个完全二叉树， 则堆的含义表明， 完全二叉树中 所有非终端结点的值均不大于（或小不于）其左、右孩子结点的值。由此，若序列 k1,k2,kn是堆，则堆顶元素必须为序列中 n 的元素的最大值。例如，下列一个序列 为堆，对应的完全二叉树如图 2.1 所示。 96,83,27,38,11,9 图 2.1 序列96,83,27,38,11,9对应的堆 若再输出堆顶的最大值之后，使得剩余 n-1 个元素的序列重又建成一个堆，则得到 n 元素中的最大值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。 2.2 堆排序算法的图示堆排序算法的图示 一组无序序列：49,38,65,97,76,13,27,49 堆排序算法的演示过程如图 2.2.和图 2.3 所示： (a) (b) 98 27 83 38 11 9 49 38 65 76 13 2
