软考软件设计师专题讲义九：数据结构相关算法

　　堆排序：对n个元素的序列进行堆排序，先将其建成堆，以根结点与第n个结点交换;调整前n-1个结点成为堆，再以根结点与第n-1个结点交换;重复上述操作，直到整个序列有序。

　　【算法10.10】

　　void HeapAdjust(S_TBL *h，int s，int m)

　　{/*r[s…m]中的记录关键码除r[s]外均满足堆的定义，本函数将对第s个结点为根的子树筛选，使其成为大顶堆*/

　　rc=h->r[s];

　　for(j=2*s;j<=m;j=j*2) /* 沿关键码较大的子女结点向下筛选 */

　　{ if(jr[j].keyr[j+1].key)

　　j=j+1; /* 为关键码较大的元素下标*/

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

　　h->r[s]=h->r[j]; s=j; /* 使s结点满足堆定义 */

　　}

　　h->r[s]=rc; /* 插入 */

　　}

　　void HeapSort(S_TBL *h)

　　{ for(i=h->length/2;i>0;i--) /* 将r[1..length]建成堆 */

　　HeapAdjust(h，i，h->length);

　　for(i=h->length;i>1;i--)

　　{ h->r[1]<-->h->r[i]; /* 堆顶与堆低元素交换 */

　　HeapAdjust(h，1，i-1); /*将r[1..i-1]重新调整为堆*/

　　}

　　}

　　交换记录至多k次。所以，在建好堆后，排序过程中的筛选次数不超过下式：

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

　　而建堆时的比较次数不超过4n次，因此堆排序最坏情况下，时间复杂度也为O(nlog2n)。

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