大名名城首府有现房吗?:9.7.1 堆排序算法（2）

来源：百度文库 编辑：偶看新闻 时间：2024/04/29 02:06:03

9.7.1 堆排序算法（2）

7．再循环因为j=2*j=16，m=9，j>m，因此跳出循环。

8．第14行，将temp=30赋值给L.r[s]=L.r[8]，完成30与60的交换工作。如图9‐7‐7所示。本次函数调用完成。

图9-7-7

9．再次调用HeapAdjust，此时s=3，m=9。第4行，temp=L.r[3]=90，第7～8行，由于40<80得到j+1=2*s+1=7。9～10行，由于90>80，因此退出循环，最终本次调用，整个序列未发什么改变。

10．再次调用HeapAdjust，此时s=2，m=9。第4行，temp=L.r[2]=10，第7～8行，60<70，使得j=5。最终本次调用使得10与70进行了互换。


图9-7-811．再次调用HeapAdjust，此时s=1，m=9。第4行，temp=L.r[1]=50，第7～8行，70<90，使得j=3。第11～12行，L.r[1]被赋值了90，并且s=3，再循环，由于2j=6并未大于m，因此再次执行循环体，使得L.r[3]被赋值了80，完成循环后，L.[7]被赋值为50，最终本次调用使得50、90、80进行了轮换。
图9-7-9

到此为止，我们构建大顶堆的过程算是完成了，也就是HeapSort函数的第4～5行循环执行完毕。或许是有点复杂，如果不明白，多试着模拟计算机执行的方式走几遍，应该就可以理解其原理。

接下来HeapSort函数的第6～11行就是正式的排序过程，由于有了前面的充分准备，其实这个排序就比较轻松了。下面是这部分代码。

  1. 6 for（i=L->length;i>1;i--）  
  2. 7 {  
  3. 8 swap（L,1,i）; /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */  
  4. 9 HeapAdjust（L,1,i-1）; /* 将L->r[1..i-1]重新调整为大顶堆 */  
  5. 10 }

1．当i=9时，第8行，交换20与90，第9行，将当前的根结点20进行大顶堆的调整，调整过程和刚才流程一样，找到它左右子结点的较大值，互换，再找到其子结点的较大值互换。此时序列变为{80,70,50,60,10,40,20,30,90}，如图9‐7‐10所示。

（点击查看大图）图9-7-102．当i=8时，交换30与80，并将30与70交换，再与60交换，此时序列变为{70,60,50,30,10,40,20,80,90}，如图9‐7‐11所示。
（点击查看大图）图9-7-113．后面的变化完全类似，不解释，只看图。
（点击查看大图）图9-7-12最终就得到一个完全有序的序列了。
堆排序的具体算法 1、 完整的堆排序由三部分组成，请分析写出堆排序的各部分的算法及PAD图。 堆排序法 堆排序发明人 堆排序的源代码 堆排序的用途 结构体排序算法 asp排序算法 什么是起泡排序算法?? 急求一排序算法 合并排序算法 vb选择排序算法 内部排序算法比较 内部排序算法比较 谁知道空间复杂度为o(1)的归并排序算法？ C算法.第1卷,基础、数据结构、排序和搜索 C算法.第1卷,基础、数据结构、排序和搜索 求堆排序法的C++代码 整数排序算法的问题？ 快速排序的循环算法 求几种排序法的算法 全排序的算法(PASCAL) 一、题目：三种典型排序算法及其比较（直接法、插入法、shell排序比较） 2堆西瓜，3堆橘子，4堆苹果，5堆香蕉，一共是多少堆？