利用堆排序实现学生成绩管理

1　引言

排序是计算机数据处理及其它许多软件系统中常用的一种操作。排序的目的通常是为了便于查找或为了适应某些查找算法的需要。例如，在统计高考成绩的系统中，要产生几个表。第一个表按考生的考号从小到大的顺序，列出所有考生的成绩；第二个表按考生的考试成绩从高到低的顺序，列出所有考生的成绩等等。在这样的系统中就要多次进行排序操作。

排序（Sorting）是把一个无序的数据元素序列按某个关键字进行有序（递增或递减）排列的过程。通常，待排序的操作对象称为数据表，它是数据元素（即记录）的有限集合。在每一个数据元素中有多个属性。当某个属性用来区分对象作为排序的依据时，该属性就称为排序关键字（Key）。如上例中的考号、考试成绩等都是排序关键字。在实际应用中，每个数据表用哪个属性作为排序关键字要视具体的应用需要而定。

排序的方法很多，就其全面的性能而言，很难提出一种被认为是最好的方法，每种方法都各有优缺点，适合在不同的环境下使用。就其时间的性能而言，插入排序、冒泡排序、选择排序性能比较接近，而快速排序、堆排序、归并排序则是性能比较接近的另一类。

2　堆排序的原理与技术

堆排序是改进的算法，比较复杂。记录数越多越适合，效率可以明显提高。堆排序是借助于一种称为堆的完全二叉树结构进行排序的，排序过程中，将向量中存储的数据看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中的父结点和子结点之间的内在关系来选择关键字最小或最大的记录。

具体做法是：把待排序的记录存放在数组r[1‥n]中，将r看作一棵二叉树，每个结点表示一个记录，第一个记录r[1]作为二叉树的根，以后各记录r[2]，…，r[n]依次逐层从左到右顺序排列，构成一棵完全二叉树，任意结点r[i]的左孩子是r[2i]，右孩子是r[2i+1]，双亲是r[i/2]。对这棵完全二叉树的结点进行调整，使各结点的关键字满足条件，r[i]≤r[2i]且r[i]≤r[2i+1]，即每个结点的值均小于或等于它的两个子结点的值，显然在这个堆树中根结点的关键字最小，这种堆被称为“小根堆”。若各结点的值满足r[i]≥r[2i]并且r[i]≥r[2i+1]的堆，称为“大根堆”，大根堆中根结点的关键字值最大。

在堆中，根结点又被称为堆顶元素，当把二叉树转换成大根堆后，堆顶元素最大，把堆顶元素输出，重新调整二叉树的剩余结点，使其成为一个新堆，再输出堆顶元素，便可求得次最大值，如此反复进行，就可得到一个有序序列，这就是利用大根堆排序的基本方法。小堆根的排序方法类似。

堆排序的关键是构造堆，即调整元素间的关系使之形成堆。由二叉树的性质得知，二叉树中序号最大的一个非终点是[n/2]，序号最小的列终结点是序号为1的结点，对这些结点需一一进行调整，使其满足堆的条件。调整过程为：首先把[n/2]号结点元素与其两个孩子中值大者进行比较并交换后，形成以[n/2]为根的子树即为堆，接着用相同的步骤对第[n/2-1]结点进行调整，直至第1个结点。如果在中间调整过程中，由于交换破坏了以其孩子为根的堆，则要对破坏了的堆进行调整，依次类推，直到父结点大于等于左、右孩子的元素结点或者孩子结点为空的元素结点。当这一系列调整过程完成时，即成为一个堆树，这个调整过程也叫做“筛选”。

3　堆排序的实现3.1　堆排序在成绩管理中的实现

下面给出学生的考试成绩表，如图1所示。每条信息由考号与分数组成。以按分数高低次序来排出每个学生在考试中获得的名次，分数相同的为同一名次为例，说明堆排序的算法。

这里，二叉树中序号最大的一个非终点是[n/2]，即图中的4号结点268.5，序号最小的列终结点是序号为1的结点，即根结点270.0。调整过程为：首先把4号结点元素268.5与其两个孩子中值大者进行比较，由于左孩子272.5>268.5故将它们交换，则以272.5为根的子树即为堆。接着用相同的步骤对第3个结点进行调整，因其满足条件，则不必交换。直至第1个结点270.0，最终形成初始堆，如图3。

图1　学生考试成绩表

图2　 原始数据的二叉树顺序存储形

图3　建立初始堆

排序过程为：先输出堆顶元素292.0，把它放到原数组的最后位置，而原数组最后一个单元存放的是244.5，为了不破坏数据，则把292.0与244.5交换，即r[1]与r[n]（n为9）交换，这时r[n]为最大，接着对r[1]与r[n－1]进行筛选又得到新堆，此时新堆的r[1]为当前最大的元素，再把r[1]与r[n－1]对调，使r[n－1]为次最大，这样，经过n－1次对调、筛选，数组r中的所有元素均按升序排列，堆排序全部完成，如图4所示。

图4　 堆排序的过程

3.2　堆排序的算法描述

下面给出整个排序过程及算法描述。（说明：已经有序的子树部分省去。）

heapsort （Recordnode　r[ ]，int n）
　　{int i，k；
　　Struct Recordnode x；
　　For（i=n/2；i>0；i--）　　　　/*建立初始堆*/
　　Sift（r，i，n）；
　　For（i=n；i>1；i--）　　　　 /*进行n－1次循环，完成堆排序*/
　　{ x=r[1]；　　　　　　　　　/*将第一个元素与当前区间的最后一个元素对调*/
　　 r[1]=r[i]；
　　 r[i]=x；
　　sift（r，1，i-1）；　　　　　/*调用筛选子函数*/
}
}

4　结束语

从堆排序的算法知道，堆排序所需的比较次数是建立初始堆与重新建堆所需的比较次数之和，其平均时间复杂度和最坏的时间复杂度均为O（n lbn）。它是一种不稳定的排序方法。

但对应于大量记录，堆排序的效率却是非常高的。

参考文献

[1]（美）Sartaj　Sahni ，汪诗林，孙晓东等译．数据结构、算法与应用——C++语言描述．机械工业出版社，2001

[2] 高一凡．《数据结构》算法实现及解析．西安电子科技大学出版社，2004

收稿日期：7月11日　　修改日期：8月27日

作者简介：尹聪春（1975-），女，东北财经大学职业技术学院计算机教研室，讲师，研究方向：计算机网络技术、嵌入式开发技术。

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!