高中信息技术竞赛班数据结构专项培训教程09内部排序教案 

输出堆顶元素后，以堆中最后元素代替之，如图9－2 (a)。此时根结点的左右子树均为堆，则仅需自上而下进行调整即可。

首先以新堆顶元素与其左右子树根结点的值比较，由于右子树根结点的值小于左子树根结点的值，且小于根结点的值，则将根结点的值69与右子树根结点的值11交换， 如图9－2 (b)。由于69替代了11之后破坏了右子树的“堆”，需进行和上述相同的调整，直至叶子结点。调整后的状态如图9－2 (c)。这个过程可称为“筛”。

输出堆顶元素后的调整过程如下：

procedure sift ( var S : array [ 1..n ] of integer ; k , m : integer ); { 假设S[k+1. . m]为小根堆，调整S[k]使整个序列S[k . . m]满足堆的性质 } begin

i:=k; j:=2*i; x:=S[k]; finish:=false; while (j<=m) and (finish=false) do begin if (jS[ j+1 ]) then j:=j+1;

{若存在右子树，且右子树根结点的值更小，则沿右分支调整}

if x<=S[ j ] then finish:=true else begin

S[ i ] := S[ j ]; i :=j ; j :=2*i ; end;

end; {whie} S[ i ]:=x; end;

( a )

( b )

图9－2 调制建新堆的过程

( c )

排序过程：

从一个无序序列建堆的过程就是一个反复调整的过程。将无序数列看成一棵完全二叉树，从最后一个非叶子结点i开始进行调整以该结点为根的子树，然后在调整以i-1为根的子树，…… 这样，在原序列的尾部形成有序区并逐步向前扩大到整个序列。

【例】：对无序序列42，13，91，23，24，16，05，88建立大跟堆

【练习】对输入的无序序列进行堆排序。

输入： 第一行： n 第二行： n个整数

输出： 将n个整数按从小到大排序输出

§9.6 排序算法的比较和选择 1. 选取排序方法需要考虑的因素：

(1) 待排序的元素数目n； (2) 元素本身信息量的大小； (3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。 2. 小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的

记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。 (2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序法中被认为是最好的方法。 (4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因

此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于\比较\的排序算法，至少需要O(nlog2n)的时间。 (5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。