第10章排序案例.ppt

例1： (96, 83, 27, 38, 11, 09) 例2： (13, 38, 27, 49, 76, 65, 49, 97) 96 27 09 11 38 83 13 27 38 49’ 65 76 49 97 可将堆序列看成完全二叉树，则： k2i 是 ki 的左孩子； k2i+1 是 ki 的右孩子。 所有非终端结点的值均不大（小）于其左右孩子结点的值。 堆顶元素必为序列中 n 个元素的最小值或最大值。 堆排序： 堆排序需解决的两个问题： 1、如何由一个无序序列建成一个堆？ 2、在输出堆顶元素后，如何将剩余元素调整为一个新的堆？ 将无序序列建成一个堆，得到关键字最小（大）的 记录；输出堆顶的最小（大）值后，将剩余的 n-1 个元 素重又建成一个堆，则可得到 n 个元素的次小值；如此 重复执行，直到堆中只有一个记录为止，每个记录出堆 的顺序就是一个有序序列，这个过程叫堆排序。 堆 堆 筛选 所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉 树，“调整”根结点使整个二叉树也成为一个堆。 第二个问题解决方法——筛选： 输出堆顶元素之后，以堆中最后一个元素替代之；然后将 根结点值与左、右子树的根结点值进行比较，并与其中小者进 行交换；重复上述操作，直至叶子结点，将得到新的堆，称这 个从堆顶至叶子的调整过程为“筛选”。 13 27 38 49 65 76 49 97 97 97 27 97 49 97 38 97 97 49 65 65 49 76 49 76 97 97 65 76 27 65 49 38 49 97 13 76 对深度为 k 的堆，“筛选” 所需进行的关键字比较的次数 至多为 2(k-1)。 第一个问题解决方法： 从无序序列的第 ?n/2? 个元素（即无序序列对应的完全二叉 树的最后一个内部结点）起，至第一个元素止，进行反复筛选。 建堆是一个从下往上进行“筛选”的过程。 例: 排序之前的关键字序列为： 13 27 38 49 49 65 76 97 堆排序过程 49 65 38 49 76 13 27 97 49 38 65 97 76 13 27 49 49 97 13 65 13 49 13 97 27 49 97 27 97 49 27 97 97 38 97 38 65 65 49 76 49 49 49 97 97 49 65 65 97 76 97 76 76 97 关键字初始序列 void HeapAdjust (HeadType H, int s, int m) { // 已知 H.r[s..m]中记录的关键字除 H.r[s] 之外均满足堆的特征，本函数自 // 上而下调整 H.r[s] 的关键字，使 H.r[s..m] 成为一个大顶堆 } // HeapAdjust rc = H.r[s]; // 暂存 H.r[s] for ( j=2*s; j=m; j*=2 ) { // j 初值指向左孩子自上而下的筛选过程; } R[s] = rc; // 将调整前的堆顶记录插入到 s 位置 if ( rc.key = R[j].key ) break; // 再作“根”和“子树根”之间的比较，若“=”成立，则说明 // 已找到 rc 的插入位置 s ，不需要继续往下调整 R[s] = R[j]; s = j; // 否则记录上移，尚需继续往下调整 if ( j m H.r[j].key H.r[j+1].key ) ++j; // 左/右“子树根”之间先 // 进行相互比较，令 j 指示关键字较大记录的位置 void HeapSort ( HeapType H ) { // 对顺序表 H 进行堆排序 } // HeapSort for ( i = H.length/2; i 0; - - i ) HeapAdjust (H.r, i, H.length); // 建大顶堆 for ( i = H.length; i 1; - - i ) { H.r[1]←→H.r[i]; // 将堆顶记录和当前未经排序子序列 // H.r[1..i