14-Chapter9 -排序.ppt

140-* 最大堆的向下调整算法 template class T siftDown (dataListT L, const int start, const int m){ //私有函数: 从结点start开始到m自上向下比较, //如果子女的值大于双亲的值, 则相互交换, 将一 //个集合局部调整为最大堆。 int i = start; int j = 2*i+1; //j是i的左子女 ElementT temp = L[i]; //暂存子树根结点 while (j = m) { //逐层比较 if (j m L[j] L[j+1]) j++; //让j指向两子女中的大者 if (temp = L[j]) break; //temp排序码大不调整 140-* else { //否则子女中的大者上移 L[i] = L[j]; i = j; j = 2*j+1; //i下降到子女位置 } } L[i] = temp; //temp放到合适位置 }; 最大堆堆顶L.Vector[0]具有最大的排序码，将L.Vector[0]与L.Vector[n-1]对调, 把具有最大 基于初始堆进行堆排序 140-* 排序码的元素交换到最后，再对前面的n-1个元素, 使用堆的调整算法siftDown(L, 0, n-2)，重新建立最大堆，具有次最大排序码的元素又上浮到L.Vector[0]位置。 再对调L.Vector[0]和L.Vector[n-2]，再调用siftDown(L, 0, n-3), 对前面的n-2个元素重新调整，…。 如此反复执行，最后得到全部排序好的元素序列。这个算法即堆排序算法，其细节在下面的程序中给出。 140-* 49 25 25* 21 16 08 0 1 2 3 4 5 08 25 25* 16 21 49 0 2 5 4 3 1 49 25 21 25* 16 08 08 25 21 25* 16 49 交换 0 号与 5 号元素, 5 号元素就位 初始最大堆 140-* 25 25* 08 21 16 49 0 1 2 3 4 5 16 25* 08 25 21 49 0 2 5 4 3 1 25 25* 21 08 16 49 16 25* 21 08 25 49 交换 0 号与 4 号元素, 4 号元素就位 从 0 号到 4 号 重新 调整为最大堆 140-* 25* 16 08 21 25 49 0 1 2 3 4 5 08 16 25* 25 21 49 0 2 5 4 3 1 25* 16 21 08 25 49 08 16 21 25* 25 49 交换 0 号与 3 号元素, 3 号元素就位 从 0 号到 3 号 重新 调整为最大堆 140-* 21 16 25* 08 25 49 0 1 2 3 4 5 08 16 25* 25 21 49 0 2 5 4 3 1 21 16 08 25* 25 49 08 16 21 25* 25 49 交换 0 号与 2 号元素, 2 号元素就位 从 0 号到 2 号 重新 调整为最大堆 140-* 16 08 25* 21 25 49 0 1 2 3 4 5 08 16 25* 25 21 49 0 2 5 4 3 1 16 08 21 25* 25 49 08 16 21 25* 25 49 交换 0 号与 1 号元素, 1 号元素就位 从 0 号到 1 号 重新 调整为最大堆 140-* 堆排序的算法 template class T void HeapSort (dataListT L) { //对表L.Vector[0]到L.Vector[n-1]进行排序, 使得表 //中各个元素按其排序码非递减有序 int i, n = L.length(); for (i = (n-2)/2; i = 0; i--) //将表转换为堆 siftDown (L, i, n-1); for (i = n-1; i = 0; i--) { //对表排序 L.Swap(0, i); siftDown (L, 0, i-1); } }; 140-* 算法分析 设堆中有 n 个结点, 且 2k-1 ≤ n 2k, 则对应的完全二叉树有 k 层。在第 i 层上的结点数≤2i-1 (i = 1, …, k)。在