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行,由于4080,因此退出循环,最终本次调用,整个序列未发什么改变。
10.再次调用HeapAdjust,此时s=2,m=9。第4行,temp=L.r[2]=10,第7~8行,60
图9-7-8
11.再次调用HeapAdjust,此时s=1,m=9。第4行,temp=L.r[1]=50,第7~8行,70
图9-7-9
到此为止,我们构建大顶堆的过程算是完成了,也就是HeapSort函数的第4~5行循环执行完毕。或许是有点复杂,如果不明白,多试着模拟计算机执行的方式走几遍,应该就可以理解其原理。
接下来HeapSort函数的第6~11行就是正式的排序过程,由于有了前面的充分准备,其实这个排序就比较轻松了。下面是这部分代码。
6 for(i=L->length;i>1;i--) 7 { 8 swap(L,1,i); /* 将堆顶记录和当前未经排序子序列的最后一个记录交换 */ 9 HeapAdjust(L,1,i-1); /* 将L->r[1..i-1]重新调整为大顶堆 */ 10 }
1.当i=9时,第8行,交换20与90,第9行,将当前的根结点20进行大顶堆的调整,调整过程和刚才流程一样,找到它左右子结点的较大值,互换,再找到其子结点的较大值互换。此时序列变为{80,70,50,60,10,40,20,30,90},如图9‐7‐10所示。
(点击查看大图)图9-7-10
2.当i=8时,交换30与80,并将30与70交换,再与60交换,此时序列变为{70,60,50,30,10,40,20,80,90},如图9‐7‐11所示。
(点击查看大图)图9-7-11
3.后面的变化完全类似,不解释,只看图。
(点击查看大图)图9-7-12
最终就得到一个完全有序的序列了。