第十章 排序62833.ppt

《第十章 排序62833.ppt》由会员分享，可在线阅读，更多相关《第十章 排序62833.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第10章章 内部排序内部排序10.1 概述概述10.2 插入排序插入排序10.3 快速排序快速排序10.4 选择排序选择排序10.5 归并排序归并排序10.6 基数排序基数排序10.7 各种内部排序方法的比较讨论各种内部排序方法的比较讨论110.1 概述概述排序排序 是将是将数据元素的一个任意序列，重新排列成一数据元素的一个任意序列，重新排列成一个按关键字有序的序列。个按关键字有序的序列。排序的一个确切定义：排序的一个确切定义：假设含假设含n个记录的序列为个记录的序列为 R1,R2,R3,Rn其相应的关键字序列为其相应的关键字序列为K1,K2,K3,Kn需确定需确定1,2,n的一种排列的一种

2、排列P1,P2,P3,Pn,使其使其相应的关相应的关键字满足如下的递增键字满足如下的递增(或递减或递减)关系关系:Kp1Kp2Kpn即使序列即使序列R1,R2,R3,Rn成为一个按关键字有序的序列成为一个按关键字有序的序列:Rp1,Rp2,Rp3,Rpn这种操作称为这种操作称为排序排序.2稳定排序方法稳定排序方法假设假设Ki=Kj(1=i,j=n,ij),且在排序前的且在排序前的序列中序列中Ri领先于领先于Rj，若在排序后的序列中若在排序后的序列中Ri仍领先仍领先Rj，则称所用的排序方法是则称所用的排序方法是稳定的稳定的。不稳定排序方法不稳定排序方法假设假设Ki=Kj(1=i,j=n,ij),

3、且在排序前的且在排序前的序列中序列中Ri领先于领先于Rj，若在排序后的序列中若在排序后的序列中Rj领领先先Ri，则称所用的排序方法是则称所用的排序方法是不稳定的不稳定的。例：例：姓名姓名年龄年龄体重体重1李由李由57622王天王天54763七明七明24754张强张强24725陈华陈华2453按某种按某种稳定稳定方法对年龄方法对年龄关键字进行关键字进行排序排序姓名姓名年龄年龄体重体重3七明七明24754张强张强24725陈华陈华24532王天王天54761李由李由57623姓名姓名年龄年龄体重体重1李由李由57622王天王天54763七明七明24754张强张强24725陈华陈华2453按某种按某

4、种不稳不稳定定方法对年方法对年龄关键字进龄关键字进行排序行排序姓名姓名年龄年龄体重体重4张强张强24723七明七明24755陈华陈华24532王天王天54761李由李由5762待排序记录存放在计算机随机存储器中进待排序记录存放在计算机随机存储器中进行的排序过程；行的排序过程；内部排序内部排序待排序记录的数量很大，以致内存一次不待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。存进行访问的排序过程。外部排序外部排序4按按排序过程中依据的不同原则对内排方法分类：排序过程中依据的不同原则对内排方法分类：（1）插入排序）插

5、入排序（2）交换排序）交换排序（3）选择排序）选择排序（4）归并排序）归并排序（5）基数排序）基数排序按内排按内排过程中所需的工作量分类：过程中所需的工作量分类：（1）简单的排序方法，其时间复杂度为）简单的排序方法，其时间复杂度为O(nn)（2）先进的排序方法，其时间复杂度为先进的排序方法，其时间复杂度为O(nlogn);（3）基数排序，其时间复杂度为基数排序，其时间复杂度为O(dn)排序算法的两种基本操作：排序算法的两种基本操作：（1）比较比较两个关键字的大小；两个关键字的大小；（2）将记录从一个位置）将记录从一个位置移移至另一个位置；至另一个位置；5待待排序的记录序列可有三种存储方式：排序

6、的记录序列可有三种存储方式：（1）待排序的记录存放在地址连续的一组存储单元上。）待排序的记录存放在地址连续的一组存储单元上。（2）待排序的记录存放在静态链表中。）待排序的记录存放在静态链表中。（3）待排序的记录本身存储在一组地址连续的存储单元）待排序的记录本身存储在一组地址连续的存储单元 内内,同时另设一个指示各个记录存储位置的地址向量。同时另设一个指示各个记录存储位置的地址向量。待待排序记录的数据类型设为：排序记录的数据类型设为：P2646#define MAXSIZE 20 /示例小顺序表的最大长度typedef int KeyType;/定义关键字类型为整数类型typedef struc

7、t KeyType key;/关键字项 InfoType otherinfo;/其他数据项 RedType；/记录类型typedef struct RedType rMAXSIZE+1;/r0闲置或作哨兵单元 int length;/顺序表的当前长度 SqList;/顺序表类型710.2 插入排序插入排序插入排序插入排序直接插入排序直接插入排序折半插入排序折半插入排序2-路插入排序路插入排序表插入排序表插入排序希尔排序希尔排序10.2.1 直接插入排序直接插入排序基本操作：基本操作：将一个记录插入到已排好序的有序表中，从将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增而得到一个新

8、的、记录数增1的有序表。的有序表。例例:有一组待排序的记录的关键字初始序列如下有一组待排序的记录的关键字初始序列如下:(49,38,65,97,76,13,27,49)用用L(SqList L)的的L.r1.key.L.r8.key依次存储依次存储L.r1.key.L.r8.key是递增有序的是递增有序的直接插直接插入排序入排序8直接插入排序的过程直接插入排序的过程:初始关键字初始关键字r0 r1 r2 r3 r4 r5 r6 r7 r8 49 38 65 97 76 13 27 49第一趟插入第一趟插入384965 97 76 13 27 49第二趟插入第二趟插入38496597 76 13

9、 27 49第三趟插入第三趟插入38 49 65 97 76 13 27 49第四趟插入第四趟插入38 49 65 76 9713 27 49第五趟插入第五趟插入13 38 49 65 76 9727 49第六趟插入第六趟插入13 27 38 49 65 76 9749第七趟插入第七趟插入13 27 38 49 49 65 76 97i=2i=3i=4i=5i=6i=7i=89直接插入排序算法分析直接插入排序算法分析:有有n个记录待排序个记录待排序,需进行需进行2.n共共n-1趟插入趟插入;一级算一级算法：法：void InsertSort(SqList&L)for (i=2;i=L.leng

10、th;+i)第第i趟插入；趟插入；第第i趟插入完成的功能趟插入完成的功能:在含有在含有i-1个记录的有序序列个记录的有序序列r1.i-1 中插入一个记录中插入一个记录ri,插入后变成含插入后变成含 有有i个记录的有序序列个记录的有序序列r1.i。10第第i趟插入的算法趟插入的算法二级算二级算法：法：例：第例：第i=7趟插入：趟插入：if (LT(L.ri.key,L.ri-1.key)L.ri插入到插入到 L.r1.L.ri-1中中 L.r0=L.ri;复制为哨兵复制为哨兵L.ri=L.ri-1;for (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L

11、.rj+1=L.r0;13 38 49 65 76 97 27 491 2 3 4 5 6 7 811三级算三级算法：法：void InsertSort(SqList&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;for (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;12直接插入排序的性能分析直接插入排序的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间r0.(2)时间时间:基本运算基本运算:比较和移动记录

12、比较和移动记录;比较和移动记录的次数与关键字的初始序列有关比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序待排序序列关键字正序排序:关键字比较次数关键字比较次数:n-1 移动记录的次数移动记录的次数:0(2)待排序序列关键字逆序排序待排序序列关键字逆序排序:关键字比较次数关键字比较次数:2+3+n=(n+2)(n-1)/2 移动记录的次数移动记录的次数:3+4+5+(n+1)=(n+4)(n-1)/2(3)待排序序列关键字随机排序待排序序列关键字随机排序:关键字比较次数关键字比较次数:(n-1)(n+4)/4 移动记录的次数移动记录的次数:(n+4)(n-1)/4直接

13、插入排序算直接插入排序算法的时间复杂度法的时间复杂度为为O(nn)1310.2.2 其它插入排序其它插入排序折半插入排序折半插入排序:把把直接插入算法中对插入位置的搜索从直接插入算法中对插入位置的搜索从顺序搜索顺序搜索改进为改进为折半搜索折半搜索.void BInsertSort(SqList&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;for (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.rj+1=L.r0;P267算法算法10.214折半插入

14、排序的性能分析折半插入排序的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间r0;(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;折半插入排序算法的时间复杂度为折半插入排序算法的时间复杂度为O(nn)152-路插入排序：路插入排序：为减少排序过程中移动记录的次数，在折半插入排序为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：的基础上加以改进：例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)另另设设一个和一个和r r同类型的数组同类型的数组d d,首先将首先

15、将r r11赋值给赋值给d d1,1,并将并将d d11看成是在排好序的序列中处于中间位置的记录看成是在排好序的序列中处于中间位置的记录,然后从然后从r r中第中第2 2个记个记录起依次插入到录起依次插入到d d11之前或之后的有序序列中：之前或之后的有序序列中：先将待插记录的关先将待插记录的关键字和键字和d1的关键字进行比较的关键字进行比较.若若ri.keyd1.key,则将则将ri插入到插入到d1之前的有序表中之前的有序表中,反之反之,则将则将ri插入到插入到d1之后的有序表中之后的有序表中.算法实现的关键设计算法实现的关键设计:将将d看成是一个循环数组看成是一个循环数组,并设两个指针并设

16、两个指针first和和final分别指示排序过分别指示排序过程中得到的有序序列中的第一个记录和最后一个记录在程中得到的有序序列中的第一个记录和最后一个记录在d中的位置中的位置.16 d1 d2 d3 d4 d5 d6 d7 d8 初始关键字初始关键字49 38 65 97 76 13 27 49i=1:49first finali=2:4938firstfinali=3:493865finalfirsti=4:49386597finalfirsti=5:4938657697finalfirsti=6:493865769713finalfirsti=7:49386576971327finalfi

17、rsti=8:4949657697132738finalfirst172-路插入排序的性能分析路插入排序的性能分析:(1)空间空间:(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;2-路插入排序算法的时间复杂度为路插入排序算法的时间复杂度为O(nn)1810.2.3 希尔排序希尔排序从直接插入排序从直接插入排序待待排序序列基本有序可提高效率排序序列基本有序可提高效率待排序序列的记录数待排序序列的记录数n很小时可提高效率很小时可提高效率希尔希尔排序的基本思想排序的基本思想:先将整个待排记录序列分割成为若干子序列分别进行先将整个待排记录序列分割成为若干子序列分别进行直接插入排序直接

18、插入排序,待整个序列中的记录待整个序列中的记录“基本有序基本有序”时时,再对再对全全体记录进行一次直接插入排序体记录进行一次直接插入排序.例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)19初始关键字初始关键字r0 r1 r2 r3 r4 r5 r6 r7 r8 49 38 65 97 76 13 27 49第一趟排序后第一趟排序后:(d1=3)27 38 13 49 49 65 97 76第二趟排序后第二趟排序后:(d2=2)13 27 49 97第三趟排序后第三趟排序后:(d3=1)13 27 38 49

19、 49 65 76 97 38 49 65 7620希尔排序算法的实现希尔排序算法的实现:Void shellsort(sqlist&L,int dlta,int t)for (i=0;it;+i)以以dltai为增量的一趟排序；为增量的一趟排序；Shellinsert（sqlist&L,dltai);Void insertsort(sqlist&L)for (i=2;i=L.length;+i)if (LT(L.ri.key,L.ri-1.key)L.r0=L.ri;L.ri=L.ri-1;For (j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;L.r

20、j+1=L.r0;(1)记录的增量记录的增量为为dk;(2)r0不是哨不是哨兵。兵。j=0，插，插入位置已找到。入位置已找到。P272算法算法10.421希尔排序的性能分析：希尔排序的性能分析：(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间r0;(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;时间复杂度为：时间复杂度为：O（n3/2）增量的取法应注意：使增量序列中的值没有除增量的取法应注意：使增量序列中的值没有除1之外的公之外的公 因子，并且最后一个增量值必须为因子，并且最后一个增量值必须为1。2210.3 快速排序快速排序起泡排序的基本思想起泡排序的基本思想:首

21、先将第一个记录的关键字和第二个记录的关键字进首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字。直至第个记录和第三个记录的关键字。直至第n-1个记录和第个记录和第n个个记录的关键字进行过比较为止。记录的关键字进行过比较为止。然后进行第二趟起泡排序，对前然后进行第二趟起泡排序，对前n-1个记录进行同样操作。个记录进行同样操作。结束的条件结束的条件:(1)趟数为趟数为n-1;(2)直到在某趟排序过程中没有直到在某趟排序过程中没有进行过交换进行过交换记录的操作为止。记录的操作为止

22、。23例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)第一趟第一趟:49386597761327493849659776132749384965977613274938496597761327493849657697132749384965761397274938496576132797493849657613274997第一趟进行第一趟进行7次比较次比较2449386597761327493849657613274997初初始始关关键键字字第第一一趟趟排排序序后后38496513274976第第二二趟趟排排

23、序序后后384913274965第第三三趟趟排排序序后后3813274949第第四四趟趟排排序序后后13273849第第五五趟趟排排序序后后132738第第六六趟趟排排序序后后1327第第七七趟趟排排序序后后整整个个排排序序过过程程25起泡排序算法的性能分析起泡排序算法的性能分析:(1)空间空间:只需一个记录的辅助空间只需一个记录的辅助空间.(2)时间时间:基本运算基本运算:比较和移动记录比较和移动记录;比较和移动记录的次数与关键字的初始序列有关比较和移动记录的次数与关键字的初始序列有关:(1)待排序序列关键字正序排序待排序序列关键字正序排序:关键字比较次数关键字比较次数:n-1 移动记录的次

24、数移动记录的次数:0(2)待排序序列关键字逆序排序待排序序列关键字逆序排序:关键字比较次数关键字比较次数:(n-1)+(n-2)+1=n(n-1)/2 移动记录的次数移动记录的次数:3n(n-1)/2(3)待排序序列关键字随机排序待排序序列关键字随机排序:关键字比较次数关键字比较次数:(n-1)(n+2)/4 移动记录的次数移动记录的次数:3n(n-1)/4起泡排序算法的起泡排序算法的时间复杂度为时间复杂度为O(nn)26快速排序的基本思想快速排序的基本思想:通过一趟排序将待排记录分割成独立的两部分，其中一部分记通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的

25、关键字小，则可分别对这两部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。录继续进行排序，以达到整个序列有序。算法实现分析：算法实现分析：（1）假设待排序的序列为）假设待排序的序列为L.rs,L.rs+1,L.rt；（2）任意选取一个记录作为枢轴，然后重新排列其余记录，将所任意选取一个记录作为枢轴，然后重新排列其余记录，将所 有关键字较它小的记录都安置在它的位置之前，所有关键字有关键字较它小的记录都安置在它的位置之前，所有关键字 较它大的记录都安置在它的位置之后。较它大的记录都安置在它的位置之后。由此可由此可以该枢轴记录所在的位置以该枢轴记录所

26、在的位置i作分界线作分界线，将序列分割成两，将序列分割成两 个子序列个子序列:L.rs,L.rs+1,L.ri-1和和 L.ri+1,L.ri+2,L.rt 这个过程称作一趟快速排序。这个过程称作一趟快速排序。（3）对子序列）对子序列L.rs,L.rs+1,L.ri-1和和L.ri+1,L.ri+2,L.rt 分别重复（分别重复（1）、（）、（2）。）。27一趟一趟快速排序的具体做法：快速排序的具体做法：(1)附设两个指针附设两个指针i和和j，它们的初值分别为它们的初值分别为s和和t，设枢设枢 轴记录的关键字为轴记录的关键字为pivotkeyL.rs.key.(2)从从j所指位置起向前搜索找到

27、第一个关键字所指位置起向前搜索找到第一个关键字小于小于 pivotkey的记录和枢轴记录互相交换，然后从的记录和枢轴记录互相交换，然后从i所所 指位置起向后搜索，找到第一个关键字指位置起向后搜索，找到第一个关键字大于大于 pivotkey的记录和枢轴记录互相交换的记录和枢轴记录互相交换;(3)重复重复(2)直到直到i=j为止。为止。例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)28第一趟快速排序：第一趟快速排序：初始关键字初始关键字49 38 65 97 76 13 27 49pivotkey=ijj进行进

28、行1次交换之后次交换之后27 38 65 97 76 13 49 49iji进行进行2次交换之后次交换之后27 38 49 97 76 13 65 49ijj进行进行3次交换之后次交换之后27 38 13 97 76 49 65 49iji进行进行4次交换之后次交换之后27 38 13 49 76 97 65 49ijj完成一趟排序完成一趟排序27 38 13 49 76 97 65 4929int Partition(SqList&L,int low,int high)pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.r

29、lowL.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rlowL.rhigh;return low;/Partition30int Partition(SqList&L,int low,int high)L.r0=L.rlow;pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey)-high;L.rlow=L.rhigh;while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;L.rlow=L.r0;return low;/Partition

30、31快速排序算法的实现：快速排序算法的实现：void QSort(SqList&L,int low,int high)if(lowhigh)pivotloc=partition(L,low,high);QSort(L,low,pivotloc-1);QSort(L,pivotloc+1,high);/QSort32整个快速排序过程整个快速排序过程:初始关键字初始关键字49 38 65 97 76 13 27 49第一趟快速排序：第一趟快速排序：27 38 13 49 76 97 65 49第二趟快速排序：第二趟快速排序：13 27 3849 65 76 97结束结束结束结束第三趟快速排序：第三

31、趟快速排序：49 65结束结束结束结束有序有序序列：序列：13 27 38 49 49 65 76 97第四趟快速排序：第四趟快速排序：33快速排序算法的性能分析：快速排序算法的性能分析：（1）空间：需一个栈空间来实现递归。）空间：需一个栈空间来实现递归。（3）时间：基本运算：比较关键字和移动记录操作）时间：基本运算：比较关键字和移动记录操作 平均时间复杂度：平均时间复杂度：Tavg(n)=3410.4 选择排序选择排序选择排序的基本思想选择排序的基本思想:每一趟在每一趟在n-i+1(i=1,2,.n-1)个记录中个记录中 选取关键字最小的记录作为有序序选取关键字最小的记录作为有序序 列中第列

32、中第i个记录。个记录。选择排序选择排序简单选择排序简单选择排序树形选择排序树形选择排序堆排序堆排序10.4.1 简单选择排序简单选择排序简单选择排序的算法设计简单选择排序的算法设计:(1)需进行需进行n-1趟选择操作趟选择操作;(2)第第i趟选择操作为趟选择操作为:通过通过n-i次关键字间比较次关键字间比较,从从n-i+1个记录中选出关个记录中选出关 键字最小的记录键字最小的记录,并和第并和第i个记录交换个记录交换;35简单选择排序的算法实现简单选择排序的算法实现:void SelectSort(SqList&L)for(i=1;iL.length;+i)/选择第选择第i小的记录，并交换到位小

33、的记录，并交换到位 j=SelectMinKey(L,i);/在在L.ri.L.length中选择中选择key最小的记录最小的记录 if (i!=j)L.riL.rj;/与第与第i个记录交换个记录交换 /SelectSort算法性能分析算法性能分析:(1)空间空间:一个辅助空间一个辅助空间;(2)时间时间:基本操作基本操作:关键字的比较和记录的移动关键字的比较和记录的移动;关键字的比较次数关键字的比较次数:(n-1)+(n-2)+1=n(n-1)/2 记录的移动次数记录的移动次数:0+3(n-1)/2=3(n-1)/23610.4.2 树形选择排序树形选择排序在在简单选择排序中简单选择排序中,

34、在在n个关键字中进行个关键字中进行n-1次比较选出最次比较选出最小值小值,然后继续在剩余的然后继续在剩余的n-1个关键字中进行个关键字中进行n-2次比较选次比较选出次小值出次小值,在在8个数中选出前个数中选出前3个数个数需需进行进行7+6+5=18次比较次比较改进改进在在n个关键字中进行个关键字中进行n-1次比较选出最小值之后次比较选出最小值之后,利用本次利用本次比较的信息比较的信息,在剩余的在剩余的n-1个关键字中并非一定要进行个关键字中并非一定要进行n-2次比较就可选出次小值次比较就可选出次小值,在在8个数中选出前个数中选出前3个数个数只需进行只需进行11次比较次比较37例例:有有8个运动

35、员参加体育锦标比赛个运动员参加体育锦标比赛,要决出前要决出前3名名,比赛规比赛规则则 依据依据:若甲胜乙若甲胜乙,乙胜丙乙胜丙,则甲胜丙的原则则甲胜丙的原则;则此则此8名运动名运动员员 需进行需进行11场比赛场比赛,而不是而不是18场场.选拔冠军的比赛程序选拔冠军的比赛程序:BAOHELILIUBAOLILINBAOHUWUXEILINLINHUBAO需进行需进行7场比赛场比赛38选拔亚军的比赛程序选拔亚军的比赛程序:LIHELILIULIULILIN*HUWUXEILINLINHULIN需进行需进行2场比赛场比赛选拔季军的比赛程序选拔季军的比赛程序:LIHELILIULIULI*HUWUXE

36、IWUHUHUHU需进行需进行2场比赛场比赛39 又称又称锦标赛排序锦标赛排序，首先对，首先对n个记录的关键字进行两两比较，然个记录的关键字进行两两比较，然后在其中一半较小者之间再进行两两比较，如此重复，直到选出最后在其中一半较小者之间再进行两两比较，如此重复，直到选出最小关键字的记录为止。小关键字的记录为止。树形树形选择排序的基本思想选择排序的基本思想:树形树形选择排序算法的执行步骤选择排序算法的执行步骤:用一棵有用一棵有n个叶子结点的完全二叉树表示排序过程个叶子结点的完全二叉树表示排序过程:(1)n个叶子结点依次存放排序之前的个叶子结点依次存放排序之前的n个关键字个关键字;(2)构造非叶子

37、结点构造非叶子结点:每个非叶子结点的值为其左、右孩子结点中的每个非叶子结点的值为其左、右孩子结点中的 较小值，则根结点是所有叶子中的最小关键字，输出根结点的值；较小值，则根结点是所有叶子中的最小关键字，输出根结点的值；(3)修改叶子结点的关键字：把具有根结点值的叶子结点的值改为修改叶子结点的关键字：把具有根结点值的叶子结点的值改为“最最 大值大值”，然后从叶子开始，和其左（或右）兄弟的值进行比较，然后从叶子开始，和其左（或右）兄弟的值进行比较，修改从叶子结点到根的路径上各结点的值，输出根结点的值；修改从叶子结点到根的路径上各结点的值，输出根结点的值；(4)重复（重复（3），直到输出），直到输出

38、n个值为止。个值为止。4049 38976576 13 27 4949 38976576 13 27 4938651327381313输出输出1349 38976576 27 4938657627382727例例:一组待排序的记录的关键字初始如下一组待排序的记录的关键字初始如下:(49,38,65,97,76,13,27,49)输出输出2749 38976576 4938657649384938输出输出3841算法性能分析算法性能分析:(1)空间空间:较多辅助空间较多辅助空间;(2)时间时间:基本操作基本操作:关键字的比较和记录的移动关键字的比较和记录的移动;算法时间复杂度：算法时间复杂度：1

39、0.4.3 堆排序堆排序堆的定义堆的定义:n个元素的序列个元素的序列k1,k2,.,kn当且仅当满足下列关系时，当且仅当满足下列关系时，称之为堆称之为堆:关系一：关系一：ki=k2i)关系二：关系二：ki=k2i+1)（i=1,2,.,|n/2|)42若将和此若将和此序列对应的一维数组看成是一个完全二叉树序列对应的一维数组看成是一个完全二叉树,则则堆的含义表明堆的含义表明:（1）完全二叉树中所有非叶子结点的值均不大）完全二叉树中所有非叶子结点的值均不大(小小)于其于其 左、右孩子结点的值。左、右孩子结点的值。（2）若序列）若序列k1,k2,.,kn为为堆，则堆顶元素（完全二叉堆，则堆顶元素（完

40、全二叉树树 的根）是序列中的最小的根）是序列中的最小(大大)值。值。例例1：96,83,27,38,11,099683273811 9堆顶堆顶元素是序列最大值元素是序列最大值例例1：12,36,24,85,47,30,53堆顶堆顶元素是序列最小值元素是序列最小值1236248547 305343堆堆排序排序若在若在输出堆顶元素之后，使得剩余输出堆顶元素之后，使得剩余n-1个元素个元素的序列重又建成一个堆，则得到的序列重又建成一个堆，则得到n个元素中的个元素中的次小值。如此反复执行，便能得到一个有序序次小值。如此反复执行，便能得到一个有序序列，这个过程称之为堆排序。列，这个过程称之为堆排序。堆排

41、序要解决两个问题：堆排序要解决两个问题：1、如何由一个无序序列建成一个堆？、如何由一个无序序列建成一个堆？2、如何在输出堆顶元素之后，、如何在输出堆顶元素之后，调整剩余元素成为一个新的堆？调整剩余元素成为一个新的堆？问题问题2的解决的解决:(1)输出堆顶元素输出堆顶元素;(2)用堆中最后一个元素代替堆顶元素用堆中最后一个元素代替堆顶元素;(3)从堆顶至叶子进行调整从堆顶至叶子进行调整(筛选筛选);44例例:有一个堆如下有一个堆如下:1397273849657649输出输出1397替代堆顶替代堆顶9713273849657649筛选筛选271397384965764927134938976576

42、49输出输出2797替代堆顶替代堆顶459713493827657649筛选筛选38134997276576493813494927657697输出输出3865替代堆顶替代堆顶结论结论:对于一个具有对于一个具有n个结点的堆个结点的堆,经过经过n次输出、次输出、n-2次筛选，则可次筛选，则可得到一个关键字递增的输出序列和一个关键字递减的数组得到一个关键字递增的输出序列和一个关键字递减的数组r；971365762738494946问题问题1的解决：的解决：（1）将此无序序列看成是一个完全二叉树，则最后一个）将此无序序列看成是一个完全二叉树，则最后一个 非叶子结点是第非叶子结点是第|n/2|个元素。

43、个元素。（2）依次对第）依次对第|n/2|，|n/2|-1,|n/2|-2,1个元素进行筛选。个元素进行筛选。例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)49496538271376974997653827137649对对97进进行筛选行筛选对对65进进行筛选行筛选474997133827657649对对38进进行筛选行筛选4997133827657649对对49进进行筛选行筛选1397273849657649堆堆排序算法的实现：排序算法的实现：P282 算法算法10.10P282 算法算法10.11堆排

44、序算法的性能分析堆排序算法的性能分析：（1）空间：一个辅助空间；）空间：一个辅助空间；（2）时间：基本操作）时间：基本操作:关键字的比较和记录的移动关键字的比较和记录的移动;算法的时间复杂度：算法的时间复杂度：O(nlogn)4810.5 归并排序归并排序将两个或两个以上的有序表组合成一个新的有将两个或两个以上的有序表组合成一个新的有序表的方法。序表的方法。归并归并2-路归并排序的基本思想：路归并排序的基本思想：假设初始序列含有假设初始序列含有n个记录，则可看成是个记录，则可看成是n个有序的子个有序的子序列，每个子序列的长度为序列，每个子序列的长度为1，然后两两归并，得到，然后两两归并，得到n

45、/2个长度为个长度为2或或1的有序子序列；再两两归并，的有序子序列；再两两归并，如此重复如此重复,直至得到一个长度为直至得到一个长度为n的有序序列为止。的有序序列为止。例例:有一组待排序的记录的关键字初始排列如下有一组待排序的记录的关键字初始排列如下:(49,38,65,97,76,13,27,49)49初始关键字初始关键字49 38 65 97 76 13 27 49第一趟归并之后第一趟归并之后38 49 65 9713 7627 49第二趟归并之后第二趟归并之后38 49 65 9713 27 49 76第三趟归并之后第三趟归并之后13 27 38 49 49 65 76 97 50归并算

46、法的核心操作是将一维数组中前后相邻的两个有序序列归归并算法的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列：并为一个有序序列：void Merge(RcdType SR,RcdType&TR,int i,int m,int n)/已知已知SRi.m和和SRm+1.n分别按关键字有序，将它们归并为分别按关键字有序，将它们归并为 一个有序序列并存放在一个有序序列并存放在TRi.n中中/for(j=m+1,k=i;i=m&j=n;+k)/将将SR中记录从小到大并入中记录从小到大并入TR if (LQ(SRi.key,SRj.key)TRk=SRi+;else TRk=SRj+;if

47、(i=m)TRk.n=SRi.m;/将剩余的将剩余的SRim复制到复制到TR if (j=n)TRk.n=SRj.n;/将剩余的将剩余的SRjn复制到复制到TR /Merge51 调用调用 n/2h|次次Merge将将SR1.n中前后相邻且长度为中前后相邻且长度为h的有序段进行的有序段进行两两归并两两归并,得到前后相邻、长度为得到前后相邻、长度为2h的有序的有序段段,并存放在并存放在TR1.n中。中。一趟归并排序的操作是：一趟归并排序的操作是：整个归并排序需进行整个归并排序需进行|log2n|趟。趟。算法算法10.13、10.14归并排序算法的性能分析归并排序算法的性能分析：（1）空间：）空间

48、：n（2）时间：基本操作）时间：基本操作:关键字的比较和记录的移动关键字的比较和记录的移动;算法的时间复杂度：算法的时间复杂度：5210.6 基数排序基数排序10.6.1 多关键字的排序多关键字的排序例例:52张扑克牌的次序为张扑克牌的次序为:2 3 A 2 3 A 2 3 A 2 3 A将整付牌整理成如上次序将整付牌整理成如上次序,可有两种方法可有两种方法:(1)先先对整付牌对整付牌按按“花色花色”分成花色递增的四堆分成花色递增的四堆,然后再分然后再分别别 对每一堆对每一堆按按“面值面值”递增排序递增排序;(2)先对先对整付牌整付牌按按“面值面值”分成面值递增的十三堆分成面值递增的十三堆,然

49、后然后再再 对整付牌对整付牌按按“花色花色”分成按四堆分成按四堆;有两个有两个关键字关键字53 2 3 A 2 5 3 7 3 8 6 A 6 10 11 9 9 12 4 8 2 3 A 2 3 A 2 3 A(1)按按花花色对色对整付整付牌排牌排序序按面按面值对值对各子各子序列序列排序排序54(2)2 2 2 2 3 3 3 3 4 4 4 4 A A A A 2 3 A 2 3 A 2 3 A 2 3 A按按面面值值对对整付整付牌排牌排序序按按花花色色对对整付整付牌排牌排序序55一般情况下一般情况下,假设有假设有n个记录的序列个记录的序列 R1,R2,.,Rn且每个记录且每个记录Ri中含

50、有中含有d个关键字个关键字序列序列R1,R2,.,Rn对对关键字关键字有序是指有序是指:对于序列中任意两个记录对于序列中任意两个记录Ri和和Rj(1=i=j=n)都满足都满足下列关系下列关系:其中其中 称为最高位关键字，称为最高位关键字，称为最低位关键字称为最低位关键字56（1）最高位优先法（）最高位优先法（MSD）：）：先对最高位关键字先对最高位关键字 进进行排序，将序列分成若干子序列，每个子序列中的记录都行排序，将序列分成若干子序列，每个子序列中的记录都具有相同的具有相同的 值，然后分别就每个子序列对关键字值，然后分别就每个子序列对关键字 进行排序，将子序列分成若干更小的子序列，依次重复，