数据结构课件第十章2分解优秀PPT.ppt

《数据结构课件第十章2分解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第十章2分解优秀PPT.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、10.1 10.1 概述概述10.2 10.2 插入排序插入排序10.3 10.3 交换排序交换排序10.4 10.4 选择排序选择排序10.5 10.5 归并排序归并排序10.6 10.6 基数排序基数排序第第1010章章 内部排序内部排序110.2 10.2 插入排序插入排序插入排序有多种具体实现算法：插入排序有多种具体实现算法：1)干脆插入排序干脆插入排序2)折半插入排序折半插入排序3）2-路插入排序路插入排序4)表插入排序表插入排序5)希尔排序希尔排序边插入边排序，保证子序列中随时都是排好序的。边插入边排序，保证子序列中随时都是排好序的。边插入边排序，保证子序列中随时都是排好序的。边插

2、入边排序，保证子序列中随时都是排好序的。小改进小改进大改进大改进2课堂练习：课堂练习：以以关关键键字字序序列列（256，301，751，129，937，863，742，694，076，438）为为例例，分分别别写写出出执执行行以以下下算算法法的的各各趟趟排排序序结结束束时时，关关键键字字序序列列的的状状态态，并并说说明明这这些些排排序序方方法法中中，哪哪些些易易于于在在链链表表（包包括括各各种种单单、双双、循循环环链链表表）上上实现？实现？干脆插入排序干脆插入排序希尔排序（取希尔排序（取dk=5,3,1）答：明显，干脆插入排序方法易于在链表上实现；但希尔排答：明显，干脆插入排序方法易于在链表上

3、实现；但希尔排序方法因为是按增量选择记录，不易于在链表上实现。序方法因为是按增量选择记录，不易于在链表上实现。两种排序方法的中间状态分别描述如后：两种排序方法的中间状态分别描述如后：3原始序列：原始序列：256256，301301，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301，751751，129129，937937，863863，742742，694694，076076，438438 256256，301301，751751，129129，937937，863863，742742，694694，07

4、6076，438438 129129，256256，301301，751751，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751，937937，863863，742742，694694，076076，438438 129129，256256，301301，751751，863863，937937，742742，694694，076076，438438 129129，256256，301301，742742，751751，863863，937937，694694，076076，438438 129129，2

5、56256，301301，694694，742742，751751，863863，937937，076076，438438 076076，129129，256256，301301，694694，742742，751751，863863，937937，438438 076076，129129，256256，301301，438438，694694，742742，751751，863863，937937 第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟第第6趟趟第第7趟趟第第8趟趟第第9趟趟4原始序列：原始序列：256256，301301，751751，129129，937937，863863，

6、742742，694694，076076，438438(取取取取dk=5,3,1)dk=5,3,1)256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，751751，129129，937937，863863，742742，694694，076076，438438256256，301301，694694，129129，937937，863863，742742，751751，076076，438438256256，301301，694694，076076，937937，863863，7

7、42742，751751，129129，438438256256，301301，694694，076076，438438，863863，742742，751751，129129，937937第第1趟趟dk=5dk=5第第2趟趟dk=3dk=3第第3趟趟dk=1dk=1256256，301301，694694，076076，438438，863863，742742，751751，129129，937937256256，301301，694694，076076，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，

8、438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，694694，256256，438438，863863，742742，751751，129129，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，301301，129129，256256，438438，694694，742742，751

9、751，863863，937937076076，301301，129129，256256，438438，694694，742742，751751，863863，937937076076，129129，256256，301301，438438，694694，742742，751751，863863，9379375voidShellSort(SqList&L，intdlta，intt)/按增量序列按增量序列dlta0t-1对依次表对依次表L作作Shell排序排序for(k=0；kt；+k)ShellSort(L，dltak)；/ShellSort时间效率：时间效率：空间效率：空间效率：O O O

10、O（1 1 1 1）因为仅占用因为仅占用1 1个缓冲单元个缓冲单元(与算法有关）与算法有关）算法的稳定性：算法的稳定性：不稳定不稳定不稳定不稳定因为因为4949*排序后却到了排序后却到了4949的前面的前面希尔排序算法希尔排序算法希尔排序算法希尔排序算法（主程序）（主程序）（主程序）（主程序）参见教材参见教材P272P272O(n1.25O(n1.25O(n1.25O(n1.25）O O O O（1.6n1.251.6n1.251.6n1.251.6n1.25）由阅历公式得由阅历公式得由阅历公式得由阅历公式得到到到到dkdk值依次装在值依次装在dltadltat t 中中/增量为增量为dlta

11、k的一趟插入排序的一趟插入排序6理解难点：理解难点：整理动作是二合一的，整理动作是二合一的，r0仍是每个仍是每个dk子集的哨兵，用于子集的彻子集的哨兵，用于子集的彻底排序！底排序！for(i=dk+1；i=L.length；+i)if(ri.key0&(r0.key0&(r0.keyrj.key);j-=dk)rj+dk=rj；rj+dk=r0；5 7 45 7 4 i=1 i+dk=6 i+2dk=11 i=1 i+dk=6 i+2dk=11 假如不用假如不用forfor循环，比较的结果是循环，比较的结果是 5 5，4 4，7 7 只有执行只有执行forfor循环后，比较结果才会是循环后，比

12、较结果才会是 4 4，5 5，7 7for(i=dk+1；i=L.length；+i)if(ri.keyri-dk.key)r0=ri；大者后移大者后移空间效率与算法设计有关空间效率与算法设计有关810.3 10.3 交换排序交换排序两两比较待排序记录的关键码，假如发生逆序两两比较待排序记录的关键码，假如发生逆序两两比较待排序记录的关键码，假如发生逆序两两比较待排序记录的关键码，假如发生逆序（即排列依次与排序后的次序正好相反），则交换之，（即排列依次与排序后的次序正好相反），则交换之，（即排列依次与排序后的次序正好相反），则交换之，（即排列依次与排序后的次序正好相反），则交换之，直到全部记录都

13、排好序为止。直到全部记录都排好序为止。直到全部记录都排好序为止。直到全部记录都排好序为止。交换排序的主要算法有：交换排序的主要算法有：1)冒泡排序冒泡排序2)快速排序快速排序交换排序的基本思想是：交换排序的基本思想是：交换排序的基本思想是：交换排序的基本思想是：91)冒泡排序冒泡排序冒泡排序冒泡排序基本思路：每趟不断将记录两两比较，并按基本思路：每趟不断将记录两两比较，并按“前小后大前小后大”（或（或“前大后小前大后小”）规则交换。）规则交换。优点：每趟结束时，不仅能挤出一个最大值到最终面位置，优点：每趟结束时，不仅能挤出一个最大值到最终面位置，还能同时部分理顺其他元素；一旦下趟没有交换发还能

14、同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。生，还可以提前结束排序。前提：依次存储结构前提：依次存储结构 例：关键字序列例：关键字序列T=(21，25，49，25*，16，08），请写出），请写出冒泡排序的具体实现过程。冒泡排序的具体实现过程。21，25，49，25*，16，0821，25，25*，16，08，4921，25，16，08，25*，4921，16，08，25，25*，4916，08，21，25，25*，4908，16，21，25，25*，49初态：初态：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟10冒泡排序的算法分析冒泡排序的算法分析最好状况：初始排列

15、已经有序，只执行一趟起泡，做最好状况：初始排列已经有序，只执行一趟起泡，做n-1次关键码比较，不移动对象。次关键码比较，不移动对象。最坏情形：初始排列逆序，算法要执行最坏情形：初始排列逆序，算法要执行n-1趟起泡，第趟起泡，第i趟趟(1i n)做了做了n-i次关键码比较，执行了次关键码比较，执行了n-i次对象交换。此次对象交换。此时的比较总次数时的比较总次数KCN和记录移动次数和记录移动次数RMN为：为：因此：因此：因此：因此：时间效率：时间效率：时间效率：时间效率：O O O O（n2)n2)n2)n2)因为要考虑最坏状况因为要考虑最坏状况因为要考虑最坏状况因为要考虑最坏状况空间效率：空间效

16、率：空间效率：空间效率：O O O O（1 1 1 1）只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元只在交换时用到一个缓冲单元稳稳稳稳 定定定定 性：性：性：性：稳定稳定稳定稳定 25 25 25 25和和和和25*25*25*25*在排序前后的次序未变更在排序前后的次序未变更在排序前后的次序未变更在排序前后的次序未变更11 冒泡排序的优点：冒泡排序的优点：冒泡排序的优点：冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一每一趟整理元素时，不仅可以完全确定一每一趟整理元素时，不仅可以完全确定一每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾

17、），还可以对前面的元个元素的位置（挤出一个泡到表尾），还可以对前面的元个元素的位置（挤出一个泡到表尾），还可以对前面的元个元素的位置（挤出一个泡到表尾），还可以对前面的元素作一些整理，所以比一般的排序要快。素作一些整理，所以比一般的排序要快。素作一些整理，所以比一般的排序要快。素作一些整理，所以比一般的排序要快。有没有比冒泡排序更快的算法？有没有比冒泡排序更快的算法？有没有比冒泡排序更快的算法？有没有比冒泡排序更快的算法？有！有！有！有！快速排序法快速排序法快速排序法快速排序法全球公认！全球公认！全球公认！全球公认！因为它每趟都能精确定位不止因为它每趟都能精确定位不止因为它每趟都能精确定位不止

18、因为它每趟都能精确定位不止1 1 1 1个个个个元素！元素！元素！元素！122 2）快速排序快速排序快速排序快速排序从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素从待排序列中任取一个元素(例如取第一个例如取第一个例如取第一个例如取第一个)作为中心，作为中心，作为中心，作为中心，全部比它小的元素一律前放，全部比它大的元素一律后放，全部比它小的元素一律前放，全部比它大的元素一律后放，全部比它小的元素一律前放，全部比它大的元素一律后放，全部比它小的元素一律前放，全部比它大的元素一律后放，形成左右两个子表；形成左右两个子表；形成左右两个子表；形成左右两个子表；然后再对各子表重

19、新选择中心元素并依此规则调整，直然后再对各子表重新选择中心元素并依此规则调整，直然后再对各子表重新选择中心元素并依此规则调整，直然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。到每个子表的元素只剩一个。此时便为有序序列了。到每个子表的元素只剩一个。此时便为有序序列了。到每个子表的元素只剩一个。此时便为有序序列了。基本思想：基本思想：基本思想：基本思想：优点：因为每趟可以确定不止一个元素的位置，而且呈指数增优点：因为每趟可以确定不止一个元素的位置，而且呈指数增优点：因为每趟可以确定不止一个元素的位置，而且呈指数增优点：因为每趟可以确定不止一个元素的位

20、置，而且呈指数增加，所以特殊快！加，所以特殊快！加，所以特殊快！加，所以特殊快！前提：依次存储结构前提：依次存储结构前提：依次存储结构前提：依次存储结构 13()，设以首元素为枢轴中心设以首元素为枢轴中心例例1：关键字序列关键字序列T=(21，25，49，25*，16，08），请），请写出快速排序的算法步骤。写出快速排序的算法步骤。21，25，49，25*，16，08初态：初态：第第1趟：趟：第第2趟：趟：第第3趟：趟：探讨：探讨：探讨：探讨：1.1.这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？这种不断划分子表的过程，计算机如何自动实现？这种不断划分

21、子表的过程，计算机如何自动实现？2.“2.“快速排序快速排序快速排序快速排序”是否真的比任何排序算法都快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？08，16，21，25，25*，(49)2116，08，()25，25*，49(08)，16，21，25，(25*，49)14pivotkey=21pivotkey=21(08，16）21（25*，49，25）Low=high=Low=high=Low=high=Low=high=3 3 3 3，本趟停止，将本趟停止，将本趟停止，将本趟停止，将中枢点定位并返回位置信息中枢点定位并返回位置信息中枢点定位并返回

22、位置信息中枢点定位并返回位置信息例例2：关键字序列关键字序列T=(21，25，49，25*，16，08），计算），计算机如何实现快速排序算法的某机如何实现快速排序算法的某一趟一趟过程？过程？ri0123456初态初态21254925*1608第第1趟趟highhighlowlow2125*3210825164925252525*跑到了前面，跑到了前面，跑到了前面，跑到了前面，不稳定不稳定不稳定不稳定！设计技巧：交替设计技巧：交替/振荡式靠近振荡式靠近15例例3：以关键字序列（以关键字序列（256，301，751，129，937，863，742，694，076，438）为例，写出执行快速算法的）

23、为例，写出执行快速算法的各趟各趟排排序结束时，关键字序列的状态。序结束时，关键字序列的状态。原始序列：原始序列：256256，301301，751751，129129，937937，863863，742742，694694，076076，438438第第1趟趟第第2趟趟第第3趟趟第第4趟趟256256，301301，751751，129129，937937，863863，742742，694694，076076，438438076076076076，129129，256256256256，751751751751，937937，863863，742742，694694，301301，43843

24、8意即模拟算法实现步骤意即模拟算法实现步骤256256256256076076301301129129751751256256256256076076076076，129129，256256256256，438438，301301，694694，742742，694694，863863，937937751751751751076076076076，129129129129，256256256256，438438438438，301301，694694，742742，751751751751，863863863863，937937076076076076，129129129129，2562562

25、56256，301301，301301，694694，742742，751751751751，863863863863，937937438438438438076076076076，129129129129，256256256256，301301301301，438438438438，694694694694，742742，751751751751，863863863863，937937937937时间效率：时间效率：时间效率：时间效率：O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加因为每趟确定的元素呈指数增加因

26、为每趟确定的元素呈指数增加空间效率：空间效率：空间效率：空间效率：O O O O（log2nlog2nlog2nlog2n）因为递归要用栈因为递归要用栈因为递归要用栈因为递归要用栈(存每层存每层存每层存每层lowlowlowlow，highhighhighhigh和和和和pivot)pivot)pivot)pivot)稳稳稳稳 定定定定 性：性：性：性：不不不不 稳稳稳稳 定定定定 因为有跳动式交换。因为有跳动式交换。因为有跳动式交换。因为有跳动式交换。16探讨探讨1 1：如何编程实现？：如何编程实现？分析：分析：每一趟子表的形成是接受从两头向中间交替式靠近法；每一趟子表的形成是接受从两头向中

27、间交替式靠近法；由于每趟中对各子表的操作都相像，主程序可接受递由于每趟中对各子表的操作都相像，主程序可接受递归算法。归算法。见教材见教材P275int int PartitionPartitionPartitionPartition(SqList&L,int(SqList&L,int low low,int,int high high)/一趟快排一趟快排/交换子表交换子表 rlowhigh rlowhigh的记录，使支点（枢轴）记录到位，并的记录，使支点（枢轴）记录到位，并返回其位置返回其位置。返回时，在支点之前的记录均不大于它，支点之后的记录均不小于它。返回时，在支点之前的记录均不大于它，支

28、点之后的记录均不小于它。r0=r0=rlowrlow;/以子表的首记录作为支点记录，放入以子表的首记录作为支点记录，放入r0r0单元单元（续下页）（续下页）一趟快速排序算法一趟快速排序算法（针对一个子表的操作）（针对一个子表的操作）17pivotkey=pivotkey=rlow.keyrlow.key;/取支点的关键码存入取支点的关键码存入pivotkeypivotkey变量变量while(low high)while(low high)/从表的两端交替地向中间扫描从表的两端交替地向中间扫描while(while(lowhighlow=pivotkeyrhigh.key=pivotkey)-

29、high-high-high-high;rlow=rhigh;rlow=rhigh;/比支点小的记录交换到低端；比支点小的记录交换到低端；while(while(lowhighlowhigh&rlow.key=pivotkeyrlow.key=pivotkey)+low+low+low+low;rhigh=rlow;rhigh=rlow;/比支点大的记录交换到高端；比支点大的记录交换到高端；rlow=r0;rlow=r0;/支点记录到位；支点记录到位；return return lowlow;/返回支点记录所在位置。返回支点记录所在位置。/PartitionPartitionPartition

30、Partition18从高端扫描从高端扫描找寻小于找寻小于pivot的元素的元素从低端扫描从低端扫描找寻大于找寻大于pivot的元素的元素一趟快速排序算法流程图一趟快速排序算法流程图一趟快速排序算法流程图一趟快速排序算法流程图r0=rlow;pivot=rlow.key;lowhighlow=pivot-high;rlow=rhigh;lowhigh&rlow.key=pivot-low;rhigh=rlow;rlow=r0;returnlow;Y YY YY YN NN NN N19if(low 1/对依次表对依次表L中的子序列中的子序列rlowhigh作快速排序作快速排序/一趟快排，将一趟

31、快排，将r一分为二一分为二/在左子区间进行递归快排，直到长度为在左子区间进行递归快排，直到长度为1/在右子区间进行递归快排，直到长度为在右子区间进行递归快排，直到长度为1pivotpivot是局部变量是局部变量voidvoidQ QuickuickSort Sort(SqList SqList&L)&L)QSort QSort(L L,1,L.length););对依次表对依次表对依次表对依次表L L进行快速进行快速进行快速进行快速排序的操作函数为：排序的操作函数为：排序的操作函数为：排序的操作函数为：20探讨探讨探讨探讨2.“2.“2.“2.“快速排序快速排序快速排序快速排序”是否真的比任何

32、排序算法都快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？是否真的比任何排序算法都快？设每个子表的支点都在中间（比较均衡），则：设每个子表的支点都在中间（比较均衡），则：第第1 1趟比较，可以确定趟比较，可以确定1 1个元素的位置；个元素的位置；第第2 2趟比较（趟比较（2 2个子表），可以再确定个子表），可以再确定2 2个元素的位置；个元素的位置；第第3 3趟比较（趟比较（4 4个子表），可以再确定个子表），可以再确定4 4个元素的位置；个元素的位置；第第4 4趟比较（趟比较（8 8个子表），可以再确定个子表），可以再确定8 8个元素的位置；个元素的位置；只需只需 loglog2

33、 2n n 1 1趟便可排好序。趟便可排好序。基本上是，因为每趟可以确定的数据元素是呈指数增加的。基本上是，因为每趟可以确定的数据元素是呈指数增加的。基本上是，因为每趟可以确定的数据元素是呈指数增加的。基本上是，因为每趟可以确定的数据元素是呈指数增加的。而且，每趟须要比较和移动的元素也呈指数下降，加上编程而且，每趟须要比较和移动的元素也呈指数下降，加上编程时运用了交替靠近技巧，更进一步削减了移动次数，所以速度特时运用了交替靠近技巧，更进一步削减了移动次数，所以速度特殊快。殊快。教材教材P276P276有证明：快速排序的平均排序效率为有证明：快速排序的平均排序效率为O(nlog2n)O(nlog

34、2n)；但最坏状况下但最坏状况下(例如自然有序例如自然有序)仍为仍为O(n2),O(n2),改进措施见改进措施见P277P277。2110.4 10.4 选择排序选择排序选择排序有多种具体实现算法：选择排序有多种具体实现算法：1)简洁选择排序简洁选择排序2)锦标赛排序锦标赛排序3)堆排序堆排序选择排序的基本思想是：选择排序的基本思想是：选择排序的基本思想是：选择排序的基本思想是：每一趟在后面每一趟在后面每一趟在后面每一趟在后面n-in-i 个待排记录中个待排记录中个待排记录中个待排记录中选取关键字最小的记录作为有序序列中的第选取关键字最小的记录作为有序序列中的第选取关键字最小的记录作为有序序列

35、中的第选取关键字最小的记录作为有序序列中的第i i 个记录。个记录。个记录。个记录。221 1）简洁选择排序）简洁选择排序）简洁选择排序）简洁选择排序思思思思路路路路异异异异样样样样简简简简洁洁洁洁：每每每每经经经经过过过过一一一一趟趟趟趟比比比比较较较较就就就就找找找找出出出出一一一一个个个个最最最最小小小小值值值值，与待排序列最前面的位置互换即可。与待排序列最前面的位置互换即可。与待排序列最前面的位置互换即可。与待排序列最前面的位置互换即可。首首首首先先先先，在在在在n n n n个个个个记记记记录录录录中中中中选选选选择择择择最最最最小小小小者者者者放放放放到到到到r1r1r1r1位位位

36、位置置置置；然然然然后后后后，从从从从剩剩剩剩余余余余的的的的n-1n-1n-1n-1个个个个记记记记录录录录中中中中选选选选择择择择最最最最小小小小者者者者放放放放到到到到r2r2r2r2位位位位置置置置；如此进行下去，直到全部有序为止。如此进行下去，直到全部有序为止。如此进行下去，直到全部有序为止。如此进行下去，直到全部有序为止。优点：实现简洁优点：实现简洁优点：实现简洁优点：实现简洁缺点：每趟只能确定一个元素，表长为缺点：每趟只能确定一个元素，表长为缺点：每趟只能确定一个元素，表长为缺点：每趟只能确定一个元素，表长为n n n n时须要时须要时须要时须要n-1n-1n-1n-1趟趟趟趟前

37、提：依次存储结构前提：依次存储结构前提：依次存储结构前提：依次存储结构 23例：关键字序列例：关键字序列T=T=（2121，2525，4949，25*25*，1616，0808），请给出简洁选择排序的具体实现过程。），请给出简洁选择排序的具体实现过程。原始序列：原始序列：21，25，49，25*，16，08第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟08，25，49，25*，16，2108，16,49，25*，25，2108，16,21，25*，25，4908，16,21，25*，25，4908，16,21，25*，25，49时间效率：时间效率：O(nO(nO(nO(n2 2 2 2)虽

38、移动次数较少，但比较次数仍多。虽移动次数较少，但比较次数仍多。空间效率：空间效率：O O O O（1 1 1 1）没有附加单元（仅用到没有附加单元（仅用到1 1个个temp)temp)算法的稳定性：算法的稳定性：不稳定不稳定不稳定不稳定因为排序时，因为排序时，25*25*到了到了2525的前面。的前面。最小值最小值 0808 与与r1r1交换位置交换位置24简洁选择排序的算法如下：（亦可参见教材简洁选择排序的算法如下：（亦可参见教材简洁选择排序的算法如下：（亦可参见教材简洁选择排序的算法如下：（亦可参见教材P276P276P276P276）VoidSelectSort(SqList&L)for

39、(i=1;i0;-i)/把把r1length建成大建成大根堆根堆 HeapAdjust(r,i,length);/使使rilength成为大根成为大根堆堆 /HeapSort建堆算法建堆算法建堆算法建堆算法(等同于堆排序算法中的第一步）等同于堆排序算法中的第一步）等同于堆排序算法中的第一步）等同于堆排序算法中的第一步）HeapAdjust是针对结点是针对结点 i 的堆调整函数，其含的堆调整函数，其含义是：从结点义是：从结点i起先到堆尾为止，自上向下比起先到堆尾为止，自上向下比较，假如子女的值大于双亲结点的值，则相互较，假如子女的值大于双亲结点的值，则相互交换，即把局部调整为大根堆。交换，即把局

40、部调整为大根堆。参见教材参见教材P281-28238while(child=m)/检查是否到达当前堆尾，未到尾则整理检查是否到达当前堆尾，未到尾则整理 if(childm&rchild.key=rchild.key)breack;/根大则不必调整，函数结根大则不必调整，函数结束束 else rcurrent=rchild;/否则子女中的大者上移否则子女中的大者上移 current=child;child=2*child;/将根下降到子女位置并接着向将根下降到子女位置并接着向下整理！下整理！/while rcurrent=temp;/直到自下而上都满足堆定义，再安置入口直到自下而上都满足堆定义，

41、再安置入口结点结点 /HeapAdjust针对结点针对结点i 的堆调整函数的堆调整函数HeapAdjust 表述如下：表述如下：HeapAdjust(r,i,m)current=i;temp=ri;child=2*i;/temp暂存暂存ri值，值，child是其左孩子是其左孩子 从结点从结点i i起先到当前堆尾起先到当前堆尾m m为止，自上向下比较，假如子女的为止，自上向下比较，假如子女的值大于双亲结点的值，则相互交换，即把局部调整为大根堆。值大于双亲结点的值，则相互交换，即把局部调整为大根堆。39难点：难点：难点：难点：将堆的当前顶点输出后，如何将剩余序列将堆的当前顶点输出后，如何将剩余序列

42、将堆的当前顶点输出后，如何将剩余序列将堆的当前顶点输出后，如何将剩余序列重新调整为堆？重新调整为堆？重新调整为堆？重新调整为堆？方法：方法：方法：方法：将当前顶点将当前顶点将当前顶点将当前顶点与堆尾记录交换与堆尾记录交换与堆尾记录交换与堆尾记录交换，然后，然后，然后，然后仿建堆仿建堆仿建堆仿建堆动作动作动作动作重新调整，如此反复直至排序结束。重新调整，如此反复直至排序结束。重新调整，如此反复直至排序结束。重新调整，如此反复直至排序结束。3.3.3.3.怎样进行整个序列的堆排序？怎样进行整个序列的堆排序？怎样进行整个序列的堆排序？怎样进行整个序列的堆排序？即：将任务转化为即：将任务转化为即：将任

43、务转化为即：将任务转化为H.rim中除中除ri外，其他都具有堆特征。外，其他都具有堆特征。现调整现调整ri的值的值，使，使H.rim为堆。为堆。40基于初始堆进行堆排序的算法步骤：基于初始堆进行堆排序的算法步骤：基于初始堆进行堆排序的算法步骤：基于初始堆进行堆排序的算法步骤：堆的第一个对象堆的第一个对象堆的第一个对象堆的第一个对象r0r0具有最大的关键码，将具有最大的关键码，将具有最大的关键码，将具有最大的关键码，将r0r0与与与与rnrn对调，把具有最大关键码的对象交换对调，把具有最大关键码的对象交换对调，把具有最大关键码的对象交换对调，把具有最大关键码的对象交换到最终到最终到最终到最终;再

44、对前面的再对前面的再对前面的再对前面的n-1n-1个对象，运用堆的调整算法，个对象，运用堆的调整算法，个对象，运用堆的调整算法，个对象，运用堆的调整算法，重新建立堆。结果具有次最大关键码的对象又重新建立堆。结果具有次最大关键码的对象又重新建立堆。结果具有次最大关键码的对象又重新建立堆。结果具有次最大关键码的对象又上浮到堆顶，即上浮到堆顶，即上浮到堆顶，即上浮到堆顶，即r0r0位置位置位置位置;再对调再对调再对调再对调r0r0和和和和rn-1rn-1，然后对前，然后对前，然后对前，然后对前n-2n-2个对象重个对象重个对象重个对象重新调整，新调整，新调整，新调整，如此反复，最终得到全部排序好的如

45、此反复，最终得到全部排序好的如此反复，最终得到全部排序好的如此反复，最终得到全部排序好的对象序列。对象序列。对象序列。对象序列。410808252125*16252125*164949交换交换交换交换 1 1号与号与号与号与66号记录号记录号记录号记录r0rnr0rn4949252525*25*21211616080812345649252125*160849252125*1608初始最大堆初始最大堆初始最大堆初始最大堆252525*25*1616212113654208084949例：例：例：例：对刚才建好的大根堆进行排序：对刚才建好的大根堆进行排序：对刚才建好的大根堆进行排序：对刚才建好的

46、大根堆进行排序：42161625*210825*210825492549交换交换交换交换 1 1号与号与号与号与55号记录号记录号记录号记录0808 2521252125*1625*164949从从从从11号到号到号到号到55号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆0808252525*25*212116164949123456161625*25*08082525212149491365420808252525*25*0808252525*25*2121 0808161649494308081621162125*254925*2549交换交换交换交换 1 1号

47、与号与号与号与44号记录号记录号记录号记录25*16210825*16210825492549从从从从1 1号到号到号到号到4 4号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆25*25*161608082121252549491234560808161625*25*252521214949136542161625*25*44080816162125*25492125*2549交换交换交换交换 1 1号与号与号与号与3 3号记录号记录号记录号记录21160821160825*254925*2549从从从从11号到号到号到号到3 3号号号号 重新重新重新重新调整为最大

48、堆调整为最大堆调整为最大堆调整为最大堆2121161625*25*0808252549491234560808161625*25*25252121494913654221210808450808 162125*2549162125*2549交换交换交换交换 1 1号与号与号与号与2 2号记录号记录号记录号记录排序完毕。排序完毕。排序完毕。排序完毕。160816082121 25*254925*2549从从从从11号到号到号到号到22号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆1616080825*25*2121252549491234560808161625*25

49、*2525212149491365421616080846void HeapSort(HeapType&H)/对依次表对依次表H进行堆排序进行堆排序 for(i=H.length/2;i 0;-i)HeapAdjust(H,i,H.length);/for,建立初始堆建立初始堆 for(i=H.length;i 1;-i)H.r1 H.ri;/交换，要借用交换，要借用temp HeapAdjust(H,1,i-1);/重建最大堆重建最大堆,i-1=m 堆排序的算法堆排序的算法堆排序的算法堆排序的算法参见教材参见教材参见教材参见教材P281-282P281-282因为每次从堆顶起先调整，故每次调

50、用耗时因为每次从堆顶起先调整，故每次调用耗时O(log2n)O(log2n)47堆排序算法分析：堆排序算法分析：堆排序算法分析：堆排序算法分析：时间效率：时间效率：时间效率：时间效率：O(nlog2n)O(nlog2n)O(nlog2n)O(nlog2n)。因为整个排序过程中须。因为整个排序过程中须。因为整个排序过程中须。因为整个排序过程中须要调用要调用要调用要调用n-1n-1n-1n-1次次次次HeapAdjust()HeapAdjust()HeapAdjust()HeapAdjust()算法，而算法本身耗算法，而算法本身耗算法，而算法本身耗算法，而算法本身耗时为时为时为时为log2nlog