ap0.ppt

堆排序算法 void HeapSort ( Elem R[], int n ) {// 对记录序列R[1..n]进行堆排序 for ( i=n/2; i0; --i )// 把R[1..n]建成大顶堆 HeapAdjust ( R, i, n ); for ( i=n; i1; --i ) { R[1]←→R[i]; // 将堆顶记录和当前未经排序子序列 R[1..i]中最后一个记录相互交换 HeapAdjust(R, 1, i-1); // 将R[1..i-1] 重新调整为大顶堆 } } // HeapSort 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 ( jm R[j].keyR[j+1].key ) ++j; // j为key较大的记录的下标 if ( rc.key = R[j].key ) break; // rc应插入在位置s上 R[s] = R[j]; s = j;} R[s] = rc; // 插入 } // HeapAdjust 91 88 42 23 24 16 05 13 （a）初始堆a[1]到a[8] 91 88 42 23 24 16 05 13 23 91 13 88 42 24 16 05 （b）第1次交换之后 13 88 42 23 24 16 05 91 堆排序的示例2（排序）如下: 88 24 42 23 13 16 05 91 （c）重建的堆a[1]到a[7] 88 24 42 23 13 16 05 91 88 24 42 23 13 16 05 91 （c）重建的堆a[1]到a[7] 88 24 42 23 13 16 05 91 05 24 42 23 13 16 88 91 （d）第2次交换之后 05 24 42 23 13 16 88 91 42 24 16 23 13 05 88 91 （e）重建的堆a[1]到a[6] 42 24 16 23 13 05 88 91 42 24 16 23 13 05 88 91 （e）重建的堆a[1]到a[6] 42 24 16 23 13 05 88 91 05 24 16 23 13 42 88 91 （f）第3次交换之后 05 24 16 23 13 42 88 91 24 23 16 05 13 42 88 91 （g）重建的堆a[1]到R[5] 24 23 16 05 13 42 88 91 24 23 16 05 13 42 88 91 （g）重建的堆a[1]到R[5] 24 23 16 05 13 42 88 91 13 23 16 05 24 42 88 91 （h）第4次交换之后 13 23 16 05 24 42 88 91 23 13 16 05 24 42 88 91 （i）重建的堆a[1]到a[4] 23 13 16 05 24 42 88 91 23 13 16 05 24 42 88 91 （i）重建的堆a[1]到a[4] 23 13 16 05 24 42 88 91 05 13 16 23 24 42 88 91 （j）第5次交换之后 05 13 16 23 24 42 88 91 16 13 05 23 24 42 88 91 （k）重建的堆a[1]到a[3] 16 13 05 23 24 42 88 91 16 13 05 23 24 42 88 91 （k）重建的堆a[1]到a[3] 16 13 05 23 24 42 88 91 05 13 16 23 24 42 88 91 （l）第6次交换之后 05 13 16 23 24 42 88 91 13 05 16 23 24 42 88 91 （m）重建的堆a[1]到a[2] 13 05 16 23 24 42 88 91 13 05 16 23 24 42 88 91 （m）重建的堆a[1]到a[2] 13 05 16 23 24 42 88 91 05 13 16 23 24 42 88 91 （n）第7次交换之后 05 13 16 23 24 42 88 91 堆排序的时间复杂度分析： 1. 对深度为 h 的堆，“筛选”所需进行的关键字 比较的次数至多为2(h-1)； 3. 调整“堆顶” n-1 次，总共进行的关键