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

利用堆排序实现学生成绩管理2011-04-14尹聪春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。