软考软件设计师专题讲义十：常用的算法设计方法

　　2.几个重要的算法程序

　　2.1 堆排序

　　堆排序也是选择排序的一种，其特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。

　　堆的定义: 堆是满足下列性质的数列{r1, r2, …，rn}： 或 若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。

　　由此，若上述数列是堆，则r1必是数列中的最小值或最大值，分别称作小顶堆或大顶堆。

　　堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。

　　所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。

　　堆排序的算法如下所示：

　　template

　　void HeapSort ( Elem R[], int n ) {

　　// 对记录序列R[1..n]进行堆排序。

　　for ( i=n/2; i>0; --i )

　　// 把R[1..n]建成大顶堆

　　HeapAdjust ( R, i, n );

　　for ( i=n; i>1; --i ) {

　　R[1]←→R;

　　// 将堆顶记录和当前未经排序子序列

　　// R[1..i]中最后一个记录相互交换

　　HeapAdjust(R, 1, i-1);

　　// 将R[1..i-1] 重新调整为大顶堆

　　}

　　} // HeapSort

　　其中筛选的算法如下所示。为将R[s..m]调整为“大顶堆”，算法中“筛选”应沿关键字较大的孩子结点向下进行。

　　Template

　　void HeapAdjust (Elem R[], int s, int m) {

　　// 已知R[s..m]中记录的关键字除R[s].key之

　　// 外均满足堆的定义，本函数调整R[s] 的关

　　// 键字，使R[s..m]成为一个大顶堆(对其中

　　// 记录的关键字而言)

　　rc = R[s];

　　for ( j=2*s; j<=m; j*=2 ) {// 沿key较大的孩子结点向下筛选

　　if ( j if ( rc.key >= R[j].key ) break; // rc应插入在位置s上

　　R[s] = R[j]; s = j;

　　}

　　R[s] = rc; // 插入

　　} // HeapAdjust

　　堆排序的时间复杂度分析：

　　1. 对深度为k的堆，“筛选”所需进行的关键字比较的次数至多为2(k-1);

　　2.对n个关键字，建成深度为+1)ûlog2nëh(=的堆，所需进行的关键字比较的次数至多为4n;

　　3. 调整“堆顶”n-1次，总共进行的关键字比较的次数不超过

　　+û2(log2(n-1) + …+log22)ûlog2(n-2)ë

　　因此，堆排序的时间复杂度为O(nlogn)

　　　　　　　计算机软考软件设计师练习试题及答案解析汇总