内部堆排序算法的实现课程设计说明书

《内部堆排序算法的实现课程设计说明书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、----数据结构课程设计设计说明书内部堆排序算法的实现学生姓名金少伟学号1121024029班级信管1101成绩指导教师曹阳数学与计算机科学学院2013年3月15日-----课程设计任务书2012—2013学年第二学期课程设计名称：数据结构课程设计课程设计题目：内部堆排序算法的实现完成期限：自2013年3月4日至2013年3月15日共2周设计内容：堆排序（heapsort）是直接选择排序法的改进，排序时，需要一个记录大小的辅助空间。n个关键字序列K1，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：　　ki≤K2i且ki≤K2

2、i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤n)　　若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。（即如果按照线性存储该树，可得到一个不下降序列或不上升序列）。本课程设计中主要完成以下内容：1.设计堆排序算法并实现该算法。2.对堆排序的时间复杂度及空间复杂度进行计算与探讨。3.寻找改进堆排序的方法。基本要求如下：1.程序设计界面友好；2.设计思想阐述清晰；3.算法流程图正确；4.软件测试方案合理、有

3、效。指导教师：曹阳教研室负责人：申静课程设计评阅评语：指导教师签名：年月日----摘要堆排序是直接选择排序法的改进。本课设以VC++6.0作为开发环境，C语言作为编程语言，编程实现了堆排序算法。程序运行正确，操作简单，易于为用户接受。关键词：堆排序；C语言；时间复杂度--------目录1．课题描述12.算法描述22.1堆排序描述22.2堆排序算法的图示22.3堆排序算法53．算法流程图64．代码实现75.算法分析106.测试11总结12参考文献13----1．课题描述查找是计算机的一项主要功能，为了查找方便，通常希望计算机中的表是按关键字是有

4、序的。因为有序的顺序表可采用查找效率较高的折半查找法，而无序的表只能进行顺序查找。因此排序也就是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。因此，学习和研究各种排序方法是计算机工作者的重要课题之一。本课题利用简单选择排序中的堆排序方法，通过对用户输入的可以组成堆的数据元素建立大、小根堆，并将其进行排序输出，使其成为一个按关键字排序的有序序列，从而有效地提高了查找的效率。开发工具：vc++6.013----2.算法描述2.1堆排序描述堆排序只需要一个记录大小的辅助空间，每个待排序

5、的记录仅占有一个存储空间。堆的定义如下：n个元素的序列（k1,k2,．．．．．．,kn）当且仅当满足下关系时，称之为堆。ki≤K2i且ki≤K2i+1或(2)Ki≥K2i且ki≥K2i+1(1≤i≤n)若将和此程序对应的一维数组看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或小不于）其左、右孩子结点的值。由此，若序列{k1,k2,……,kn}是堆，则堆顶元素必须为序列中n的元素的最大值。例如，下列一个序列为堆，对应的完全二叉树如图2.1所示。{96,83,27,38,11,9}98278338119图2.1序列{

6、96,83,27,38,11,9}对应的堆若再输出堆顶的最大值之后，使得剩余n-1个元素的序列重又建成一个堆，则得到n元素中的最大值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。2.2堆排序算法的图示一组无序序列：{49,38,65,97,76,13,27,49}堆排序算法的演示过程如图2.2.和图2.3所示：499381376652797494938657613274997(a)(b)13----49976576132749384997657613274938(c)(d)9776654913274938(e)图2.2建初始堆过程

7、示例49766549132797387649654913279738（a）(b)13----27496549137697386549274913769738(c)(d)13492749657697384913274965769738(e)(f)491327494965769738381327494965769749(g)(h)13----271338494965769749132738494965769749（l）(m)图2.3输出对元素并调整建新堆的过程2.3堆排序算法堆排序算法代码如下：TypedefSqlistHeapType;VoidH

8、eapAdjust(HeapType&H,ints,intm)//j建大顶堆函数{RC=H.r[s];for(j=2*s;j<=m;j*=2){if(