数据结构与算法 教学 张晓莉 王苗 排序.pptx

《数据结构与算法 教学 张晓莉 王苗 排序.pptx》由会员分享，可在线阅读，更多相关《数据结构与算法 教学 张晓莉 王苗 排序.pptx（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/1711.教学内容：排序的概念、5类排序(10种方法)2.教学目的：领会排序的基本思想和基本概念；理解并掌握各种排序方法的基本思想、步骤、算法及时空效率分析；了解外排序的定义和基本方法。3.教学重点：常用排序方法的基本思想、基本步骤和算法。4.教学难点：(1)快速排序 (2)堆排序 (3)基数排序 5.学时安排：10学时第1页/共103页2023/3/1728.1 基本概念1记录、关键码和排序表：记录：数据元素 关键码：作为排序依据的数据项称为数据元素的关键码。排序表：若干个（n个）排序纪录组成的集合。排序表也称成为文件，主要操作是排序。2非递减序列、递减序列、非递增序列、递增有

2、序3稳定排序和非稳定排序第2页/共103页2023/3/1734内部排序和外部排序5对排序方法的评价空间性能：除排序表以外的内存占用情况。时间性能：比较关键码的次数，数据移动的次数。它们往往是排序表规模（n）的函数第3页/共103页2023/3/1746.记录和排序表的数据结构 在本章的讨论中，除特殊声明外，一般采用顺序结构存储排序表。记录和排序表的类型定义如下：#define MAXNUM /*MAXNUM 为足够大的数*/typedef struct keytype key;/*关键码字段*/*其它信息*/datatype;/*记录类型*/datatype RMAXNUM;/*定义排序表的

3、存储*/如不加特别说明，排序表中的记录R1Rn存放在R1Rn分量中，R0分量闲置或做监视哨（n是排序表中记录的个数）。第4页/共103页2023/3/1758.2 插入排序直接插入排序折半插入排序表插入排序（重排算法*）希尔排序(Shells Sort)！插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表的适当位置，直到全部记录插入完成，整个表有序为止。第5页/共103页2023/3/176直接插入排序直接插入排序是一种简单的插入排序方法，基本思想为：在R1至Ri-1长度为i-1的子表已经有序的情况下，将Ri插入，得到R1至Ri长度为i 的子表有序，这样通过

4、n-1趟（i=2.n）之后，R1至Rn有序。第6页/共103页2023/3/177例如，对于以下序列（为简便起见，每一个记录只列出其排序码，用排序码代表记录）：10 18 20 36 60 25 30 18 12 56 其中，前5个记录组成的子序列是有序的，这时要将第6个记录插入到前5个记录组成的有序子序列中去，得到一个含有6个记录的新有序序列。完成这个插入首先需要找到插入位置：202536，因此25应插入到记录20和记录36之间，从而得到以下新序列：10 18 20 25 36 60 30 18 12 56 这就是一趟直接插入排序的过程。第7页/共103页2023/3/178直接插入排序：仅

5、有一个记录的表总是有序的，因此，对n个记录的表，可从第二个记录开始直到第n个记录，逐个向有序表中进行插入操作，从而得到n个记录按关键码有序的表。第8页/共103页2023/3/179 R0 R1 R2 R3 R4 R5 R6 R7 R8 R9 R10初始序列：36 20 18 10 60 25 30 18 12 56i=2 ：(20)20 36 18 10 60 25 30 18 12 56 i=3 ：(18)18 20 36 10 60 25 30 18 12 56 i=4 ：(10)10 18 20 36 60 25 30 18 12 56第9页/共103页2023/3/1710【算法8-

6、1】直接插入排序void D_InsertSort(datatype R,int n)/*对排序表R1.Rn进行直接插入排序，n是记录的个数*/for(i=2;i=n;i+)if(Ri.keyRi-1.key)R0=Ri;/*将Ri插入R1.Ri-1中，R0为监测哨*/for(j=i-1;R0.keyRj.key;j-)Rj+1=Rj;/*后移记录*/Rj+1=R0;/*插入到合适位置*/第10页/共103页2023/3/1711【性能分析：】空间性能：仅用了一个辅助单元R0作为监视哨，空间复杂度为O(1)。时间性能：向有序表中逐个插入记录的操作，进行了n1趟，每趟操作分为比较关键码和移动记录

7、，而比较的次数和移动记录的次数取决于初始序列的排列情况。分三种情况讨论：第11页/共103页2023/3/1712总比较次数总比较次数总移动次数总移动次数(2)最坏情况下：即第j趟操作，插入记录需要同前面的j个记录进行j次关键码比较，移动记录的次数为j+2次。(1)最好情况下：即待排序列已按关键码有序，每趟操作只需1次比较，0次移动。即：总比较次数=n-1次总移动次数=0次第12页/共103页2023/3/1713(3)平均情况下：即第j趟操作，插入记录大约同前面的j/2个记录进行关键码比较，移动记录的次数为j/2+2次。总比较次数总比较次数总移动次数总移动次数 由此，直接插入排序的时间复杂度

8、为O(n2)。直接插入排序是一个稳定的排序方法。直接插入排序也可以在链式结构上实现。第13页/共103页2023/3/1714折半插入排序 直接插入排序的基本操作是向有序表中插入一个记录，在直接插入排序中，插入位置的确定是通过对有序表中关键码的顺序比较得到的。既然是在有序表中确定插入位置，因此在寻找Ri的插入位置时，就可以采用折半查找的方法，用折半查找方法查找Ri的插入位置，再将Ri插入进去，使得Ri到Ri有序，这种方法就是折半插入排序。第14页/共103页2023/3/1715【算法8-2】折半插入排序算法void B_InsertSort(datatype R,int n)/*对排序表R1

9、.Rn作折半插入排序,n是记录的个数*/for(i=2;i=n;i+)R0=Ri;/*保存待插入元素*/low=1;high=i1;/*设置初始区间*/while(lowRmid.key)low=mid+1;/*插入位置在高半区中*/else high=mid-1;/*插入位置在低半区中*/for(j=i-1;j=high+1;j-)/*high+1为插入位置*/Rj+1=Rj;/*后移元素，留出插入空位*/Rhigh+1=R0;/*将元素插入*/第15页/共103页2023/3/1716【时间效率时间效率】确定插入位置所进行的折半查找，定位一个关键码的位置需要比较次数至多为 次，所以比较次数

10、时间复杂度为O(nlog2n)。相对直接插入排序，折半插入排序只能减少关键字间的比较次数，而移动记录的次数和直接插入排序相同，故时间复杂度仍为O(n2)。折半插入排序是一个稳定的排序方法。折半插入排序只适合于顺序存储的排序表。第16页/共103页2023/3/1717表插入排序及重排1、表插入排序：表插入排序就是直接插入排序应用于用链表存储的排序表。直接插入排序、折半插入排序均要大量移动记录，时间开销大。若不移动记录完成排序，需要改变存储结构，将排序表按链表存储。表插入排序：用单链表做排序表的存储结构，通过改变链接指针，实现关键码有序的过程。与顺序存储的排序表所不同的是：直接插入排序要移动记录

11、，而表插入排序是修改链接指针。第17页/共103页2023/3/1718设排序表用静态链表作为存储结构，定义如下：#define MAXNUM /*足够大的数*/typedef struct datatype data；/*元素类型*/int next；/*指针项*/SNodeType；/*表结点类型*/SNodeType RMAXNUM；/*R是静态链表存储的排序表*/设数据元素已存储在静态链表中，且0号单元作为头结点，根据链表的特点可以通过不移动记录而只是改变链接指针，将记录按关键码组织成一个有序静态链表。第18页/共103页2023/3/1719【例8-2】设排序表为：49,38,65,

12、97,76,13,27,49。表插入排序过程如图 8-2所示。第19页/共103页2023/3/1720第20页/共103页2023/3/1721性能分析:表插入排序的基本操作是将一个记录插入到已排好序的有序链表中。设有序表长度为i，则需要比较至多i+1次，修改指针2次。因此，总比较次数与直接插入排序相同。所以，时间复杂度仍为O(n2)。没有移动数据。第21页/共103页2023/3/1722MAXINT4938659776132749681504723012345678MAXINT1327384949657697123456780(a)(b)2、重排：表插入排序得到一个逻辑上有序的链表，物理

13、上无序，查找则只能进行顺序查找。有时还需要关键码按物理存储有序，这是需要将逻辑上有序的链表进行重排，使得关键码按物理存储有序。如下图:第22页/共103页2023/3/1723重排记录方法：按链表顺序扫描各结点，将逻辑上的第i个数据元素调整到数组的第i个分量上。问题：调整前的第i个纪录可能在数组的第j个分量上，因此需要将两个分量进行交换，但交换后会破坏指向i分量的链。解决方法：为了保持原有的链，需要将第i个结点的指针域改变为j，起一个引导的作用。MAXINT4938659776132749681504723MAXINT1338659776492749671504823012345678第23页

14、/共103页2023/3/1724MAXINT4938659776132749681504723012345678MAXINT13386597764927496(6)1504823MAXINT13276597764938496(6)(7)50481313-27-38-49-49-65-76-97表排序之后的重排示意图-i:第几次，j:当前元素的位置i=1j=6i=2j=7初始状态i=3j=(2)、7第24页/共103页2023/3/1725MAXINT13273897764965496(6)(7)(7)04853012345678MAXINT13273849769765496(6)(7)(7)

15、(6)4053MAXINT13273849499765766(6)(7)(7)(6)(8)054MAXINT13273849496597766(6)(7)(7)(6)(8)(7)04MAXINT13273849496576976(6)(7)(7)(6)(8)(7)(8)0i=5j=8i=7j=(5)、8i=6j=(3)、7i=4j=(1)、6i=8j=8第25页/共103页2023/3/1726【算法8-3】表插入排序位置重排算法void B_InsertSort(SNodeType R,int n)/*将按表插入排序方法已排好序的静态链表记录位置重排,n为记录个数*/int i,j,p;/*

16、j指当前重拍元素，i为应该到的位置*/*p指下一个待排元素的初始位置*/datetype s;j=R0.next;/*第一个元素的位置*/R0.next=1;i=1;第26页/共103页2023/3/1727 while(in)/*将j分量上元素调整到i分量上*/if(i=j)j=Rj.next;/*恰好在i分量上*/i+;else if(ij)/*将j分量向前调整到i分量*/p=Rj.next;/*保存下一个待重排的元素的初始指针*/s=Ri;Ri=Rj;Rj=s;/*Ri 和Rj交换*/Ri.next=j;/*保存引导指针*/j=p;i+;else /*待排元素已移动，需要按照引导向后寻找

17、待排元素*/while(ji)j=Rj.next;/*ji,按引导指针找到待重排的元素*/第27页/共103页2023/3/1728希尔排序(Shells Sort)直接插入排序算法简单，特点为：在n值较小时，效率比较高，在n值很大时，若序列按关键码基本有序，效率依然较高，其时间效率可提高到O(n)。希尔排序(Shells Sort)是从这两点出发，给出插入排序的改进方法。希尔排序又称缩小增量排序，是1959年由提出来的。在有序性差时尽量不让排序表太大，随着有序性变好，排序表逐渐加大。第28页/共103页2023/3/17291、希尔排序的思想是：先选取一个小于n的整数di（称之为步长），然后

18、把排序表中的n个记录分为di个组，从第一个记录开始，间隔为di的记录为同一组，各组内进行直接插入排序，一趟之后，间隔di的记录有序，随着有序性的改善，减小步长di（排序子表变大），重复进行，直到di=1（全部记录成为一个排序表），使得间隔为1的记录有序，也就使整体达到了有序。步长为1时就是前面讲的直接插入排序。第29页/共103页2023/3/17302、【例】排序列表为：39,80,76,41,13,29,50,78,30,11,100,7,41,86 步长因子分别取5、3、1，则排序过程如下：3980764113295078301110074186P=5间隔为5的子序列分别为：39，29，

19、100，80，50，7，76，78，41，41，30，86，13，11。第30页/共103页2023/3/1731第一趟排序结果，使得间隔为5的字表有序：2974130113950764113100807886P=3子序列分别为:29,30,50,13,78，7,11,76,100,86，41,39,41,80。第二趟排序结果：1373929114130764150868078100P=1此时，序列“基本有序”，对其进行直接插入排序，得到最终结果：7111329303941415076788086100第31页/共103页2023/3/1732【算法8-4】希尔排序的算法void ShellS

20、ort(datatype R,int n,int d,int t)/*按增量序列d0,d1 dt1对排序表R1.Rn进行希尔排序*/int i,j,k,h;for(k=0;kt;k+)h=dk;/*本趟的增量*/for(i=h+1;i=n;i+)if(Ri.key0&R0.keyRj.key;j=jh)Rj+h=Rj;/*记录后移*/Rj+h=R0;/*插入到正确位置*/第32页/共103页2023/3/1733【时效分析】希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于步长因子序列的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的步长因子序

21、列的方法。步长因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：步长因子中除1外没有公因子，且最后一个步长因子必须为1。希尔排序方法是一个不稳定的排序方法。第33页/共103页2023/3/17348.3 交换排序交换排序的基本思想是：通过排序表中两个记录关键码的比较，若与排序要求相逆，则将二者进行交换，直至没有反序的记录为止。交换排序的特点是：排序码值较小记录的向序列的一端移动，排序码值较大记录的向序列的另一端移动。冒泡排序快速排序第34页/共103页2023/3/1735冒泡排序设排序表为R1.Rn，对n个记录的排序表进行冒泡排序(Bubble Sort)的过程是：第1趟，从第

22、1个记录开始到第n个记录，对n1对相邻的两个记录关键字进行比较，若与排序要求相逆，则将二者交换。一趟之后，具有最大关键字的记录交换到了Rn，第2趟，从第1个记录开始到第n1个记录继续进行第二趟冒泡。两趟之后，具有次最大关键字的记录交换到了Rn1，如此重复，n1趟后，在R1.Rn中，n个记录按关键码有序。冒泡排序最多进行 n1趟，在某趟的两两比较过程中，如果一次交换都未发生，表明已经有序，则排序提前结束。第35页/共103页2023/3/1736【算法8-5】冒泡排序算法 void Bubble_Sort(datetype R,int n)/*对排序表R1.Rn进行冒泡排序，n是记录个数*/in

23、t i,j;int swap;/*交换标志变量*/for(i=1;in1;i+)swap=0;for(j=1;jRj+1.key)R0=Rj+1;Rj=Rj+1;Rj+1=R0;swap=1;/*置交换标志*/if(swap=0)break;第36页/共103页2023/3/1737【效率分析】空间效率：仅用了一个辅助单元。时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。总比较次数总比较次数移动次数：最好情况下：待排序列已有序，不需移动。最坏情况下：每次比较后均要进行三次移动。移动次数移动次数第37页/共103页2023/3/1738快速排序1、快速排序的思

24、想 快速排序是通过比较关键码、交换记录，以某个记录为界(该记录称为支点)，将待排序列分成两部分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次划分。对各部分不断划分，直到整个序列按关键码有序。第38页/共103页2023/3/17392、划分示例【例8-5】对排序表：49,14,38,74,96,65,8,49,55,27进行划分。划分过程如图8-5所示。设初始状态:49 14 38 74 96 65 8 49 55 27 14 38 74 96 65 8 49 55 27 low

25、high从high向前搜索小于49的记录，找到后将其调整到low位置，得到结果：27 14 38 74 96 65 8 49 55 low high从low向后搜索大于49的记录，找到后将其调整到high位置，得到结果：27 14 38 96 65 8 49 55 74 low high 第39页/共103页2023/3/1740再从high向前搜索小于49的记录，找到后将其调整到low位置，得到结果：27 14 38 8 96 65 49 55 74 low high 再从low向后搜索大于49的记录，找到后将其调整到high位置，得到结果：27 14 38 8 65 96 49 55 74

26、 low high 再继续，得到结果：27 14 38 8 65 96 49 55 74 low=high 当low=high，划分结束，填入支点记录：27 14 38 8 49 65 96 49 55 74第40页/共103页2023/3/17413、快速排序一次划分算法【算法8-6】划分算法int Partition(datatype R,int low,int high)/*以Rlow为支点对Rlow.R high进行划分，返回支点记录最终的位置*/R0=Rlow;/*暂存支点记录*/while(lowhigh)/*从表的两端交替地向中间扫描*/while(low=R0.kry)High

27、-;if(lowhigh)Rlow=Rhigh;low+;/*将比支点小的交换到前面*/while(lowhigh&Rlow.keyR0.key)low+;if(lowhigh)Rhigh=Rlow;high;/*将比支点大的交换到后面*/Rlow=R0;/*支点记录到位*/return low;/*返回支点记录所在位置*/第41页/共103页2023/3/17424、快速排序经过划分之后，支点则到了最终排好序的位置上，再分别对支点前后的两组继续划分下去，直到每一组只有一个记录为止，则是最后的有序序列，这就是快速排序。快速排序过程就是反复划分的过程，算法如下：【算法8-7】快速排序算法void

28、Quick_Sort(datatypeR,ints,intt)/*对Rs.Rt进行快速排序*/if(st)i=Partition(R,s,t)/*将表一分为二*/Quick_Sort(R,s,i1);/*对支点前端子表递归排序*/Quick_Sort(R,i+1,t);/*对支点后端子表递归排序*第42页/共103页2023/3/174349143874966584914387496658494955275527 快速排序的递归过程可用生成一棵二叉树形象地给出，右图为上例中待排序列对应递归调用过程的二叉树。38749684927554965145、【效率分析】第43页/共103页2023/3/

29、1744 空间效率：快速排序是递归的，每层递归调用时的指针和参数均要用栈来存放，递归调用层次数与上述二叉树的深度一致。因而，存储开销在理想情况下为O(log2n)，即树的高度；在最坏情况下，即二叉树是一个单链，为O(n)。时间效率：在n个记录的待排序列中，一次划分需要约有=n次关键码比较，时效为O(n)，理想情况下：每次划分，正好将分成两个等长的子序列，则需要的排序趟数为=log2n，故时间性能为O(nlog2n)。第44页/共103页2023/3/1745 最坏情况下：即每次划分，只得到一个子序列，时效为O(n2)。快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好

30、的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取支点记录，即将排序区间的两个端点与中点三个记录关键码居中的作为支点记录。快速排序是一个不稳定的排序方法（如：2，2，1）。可以证明平均性能为：O(nlog2n)第45页/共103页2023/3/17468.4 选择排序选择排序仍然是基于排序码的比较而进行的。特点：顾名思义，选择排序是在每一趟排序中通过关键码比较，选择出关键码值最小（以正序为例）的记录，输出或置入相应的位置上，然后再从其余元素中选择最小。第1趟，从n个记录中找出关键码最小的记录；第2趟，从剩余的n-1个记录中找出关键码最小的记

31、录；第n-1趟，从剩余的2个记录中找出关键码最小的记录。排序结束。故选择排序需要n-1趟。第46页/共103页2023/3/1747 根据选择最小关键码记录的方式不同，选择排序又有多种方法，在本节中我们重点讲两种选择排序：简单选择排序堆排序第47页/共103页2023/3/1748简单选择排序 -特点：每次选择的过程是顺序进行的。1、基本思想：第1趟，从第1个到第n个记录中选择关键码最小的记录与第1个记录交换；第2趟，从第2个到第n个记录中选择关键码最小的记录与第2个记录交换；第i趟，从第i个到第n个记录中选择关键码最小的记录与第i个记录交换;直到第n-1趟，从最后两个记录中选择较小的记录放置

32、在第n-1 位置。排序结束。第48页/共103页2023/3/17492、示例：设排序表：49 14 38 74 96 65 49 14 38 74 96 65 4949 8 55 8 55 2727第1趟之后：8 8 14 38 74 96 65 49 49 55 27第2趟之后：8 8 1414 38 74 96 65 49 49 55 27 （在本位就不用交换）第3趟之后：8 8 1414 2727 74 96 65 49 49 55 38 第4趟之后：8 8 1414 2727 49 96 65 74 49 55 38 。第9趟之后：8 8 1414 2727 38 38 4949 4

33、9 55 65 49 55 65 74 9674 96 第49页/共103页2023/3/17503、算法实现【算法8-8】简单选择排序voidSelect_Sort(datatypeR,intn)/*对排序表R1.Rn进行冒泡排序，n是记录个数*/for(i=1;in;i+)/*作n-1趟选取*/k=i;/*在i开始的n-i+1个记录中选关键码最小的记录*/for(j=i+1;j=n;j+)if(Rj.keyRk.key)k=j;/*k中存放关键码最小记录的下标*/if(i!=k)/*关键码最小的记录与第i个记录交换*/R0=Rk;Rk=Ri;Ri=R0;注意i,j,k的意义：i：控制趟循环

34、；j:控制每趟中从第i个元素到第n个元素选择最小值的循环；k:用来指向本趟中到当前为止找到的最小元素。第50页/共103页2023/3/17514、性能分析：从算法中可看出，简单选择排序移动记录的次数较少，最多数据移动3(n-1)次，最少0次。但关键码的比较次数：第1趟(n-1)次，第2趟(n-2)次，第i趟 (n-i)次,（i=1，2，n-1)依然是(n*(n+1)/2，所以时间复杂度仍为O(n2)。第51页/共103页2023/3/17525、问题 (1)简单选择排序是稳定排序吗？举例说明。(2)最好和最坏的情况下是出自什么情况？(3)如排序表用链式存储，可否采用此方法？第52页/共103

35、页2023/3/1753堆排序(Heap Sort)-继承了前面的工作简单选择排序的思想简单，易于实现，但其时间性能没有优势，这是因为在每趟的选择中，没有把前面选择过程中的一些有用信息继承下来，因此每趟选择都是顺序的一一进行，如果某一趟的选择能够把前面有用的一些信息继承下来，则定会减少本趟的比较次数，提高排序效率，堆排序就做到了这一点。第53页/共103页2023/3/1754如：序列 12,36,24,85,47,30,53,91是一个小顶堆；序列 91,47,85,24,36,53,30,16是一个大顶堆。1.堆的定义 设有n个元素的序列 R1，R2，Rn，当且仅当满足下述关系之一时，称之

36、为堆。前者称为小顶堆，后者称为大顶堆。kik2ik2i+1kik2ik2i+1或其中i=1,2,n/2 第54页/共103页2023/3/1755 在完全二叉树上，双亲和左右孩子之间的编号就是i和2i、2i+1的关系。因此一个序列可以和一棵完全二叉树对应起来，用双亲其左、右孩子之间的关系可以直观的分析是否符合堆的特性。如果该序列是一个堆，则对应的这棵完全二叉树的特点是：所有分支结点的值均不小于(或不大于)其子女的值，即每棵子树根结点的值是最大(或最小)的。堆特点：堆顶元素是整个序列中最大(或最小)的元素。8516364730532491小顶堆：16，36，24，85，47，30，53，9147

37、91243653308516大顶堆：91，47，85，24，36，53，30，16第55页/共103页2023/3/17562堆排序堆特点：堆顶元素是整个序列中最大(或最小)的元素。若将排序表按关键码建成堆，堆顶元素就是选择出的最大元素（或最小），这样就得到n个元素中的第一个的元素。然后，再对剩下的n-1个元素建成堆，得到n个元素中关键码次大(或次小)的元素。以此类推，如此反复，直到进行n-1次后，排序结束，便得到一个按关键码有序的序列。称这个过程为堆排序。第56页/共103页2023/3/1757 因此，实现堆排序需解决两个问题：1.如何将n个元素的排序序列按关键码建成堆（初始堆）；2.怎样

38、将剩余的n-1个元素按其关键码调整为一个新堆。第57页/共103页2023/3/17589147243653308516a.初始堆输出堆顶元素,再将最后一个元素放入堆顶(为了操作简便，将堆顶元素R1与Rn交换)。b.堆被破坏调整：根结点与左右子女较大者比较，若比根小，交换。c.右子树不满足堆，继续调整。d.到了叶子结点，调整结束，堆建成。858547471630539116472436533085918547243653301691第58页/共103页2023/3/1759R1与Rn-1交换，堆被破坏。对R1与Rn-2调整。仅需调整一次，堆建成。堆调整结束。858547471630539185

39、304747168553918553474716853091第59页/共103页2023/3/1760第二个问题的背景第二个问题的背景第二个问题的背景第二个问题的背景：输出堆顶元素后，将堆底元素送入堆顶（或将堆顶元素与堆底元素交换），堆可能被破坏。破坏的情况仅是根结点和其左右孩子之间可能不满足堆的特性，而其左右子树仍然是局部的堆。在这种情况下，将其R1 Ri整理成堆。（i=n-1.1)第60页/共103页2023/3/1761调整方法：调整方法：调整方法：调整方法：将根结点与左、右孩子中较小(大顶堆为较大)的进行交换。若与左孩子交换，则左子树堆可能被破坏，且仅左子树的根结点处不满足堆的性质；若

40、与右孩子交换，则右子树堆可能被破坏，且仅右子树的根结点处不满足堆的性质。继续对不满足堆性质的子树进行上述操作，直到满足了堆性质或者到叶子结点，堆被建成。称这个自根结点到叶子结点的调整过程为筛选筛选筛选筛选。第61页/共103页2023/3/17629147243653308516a.初始堆。输出堆顶元素,再将最后一个元素放入堆顶(为了操作简便，将堆顶元素R1与Rn交换)。b.堆被破坏调整：根结点与左右子女较大者比较，若比根大，交换c.右子树不满足堆，继续调整 d.到了叶子结点，调整结束，堆建成。164724365330859124854736533016912485473616305312第6

41、2页/共103页2023/3/17633.【算法8-9】筛选算法voidHeapAdjust(datetypeR,ints,intt)/*以Rs为根的子树只有Rs与其左右孩子之间可能不满足堆特性*/*进行调整使以Rs为根的子树成为大顶堆*/datetyperc;/*缓冲变量*/rc=Rs；i=s;for(j=2*i;j=t;j=2*j)/*沿关键码较大的孩子结点向下筛选*/if(jt&Rj.keyRj.key)break;/*不用调到叶子就到位了*/Ri=Rj;i=j;/*准备继续向下调整*/Ri=rc；/*插入*/第63页/共103页2023/3/17644、堆排序的实现 初步的堆排序算法：

42、1、建成初始堆；2、for(i=n;i1;i-)R1Ri;HeapAdjust(R,1,i-1);第64页/共103页2023/3/1765再讨论第一个问题：对原始排序表建初始堆的过程。对原始序列建堆过程，就是一个反复进行筛选的过程。对原始序列建堆过程，就是一个反复进行筛选的过程。仍然通过对应的完全二叉树分析：对n个结点的完全二叉树，可以认为：以叶子为根的子树（只有它自己）已满足堆特性，因此从最后一个分支结点开始，把每棵子树调整为堆，直到根结点为止，整棵树成为堆。最后一个分支结点是第 个结点。第65页/共103页2023/3/1766【例】建堆的过程：设初始排序序列：30 24 85 16 3

43、6 53 91 47，建成大顶堆。3024163653918547a.8个结点的初始状态。从R4结点开始调整；b.调整结束后，以R4为根的子树满足堆特性。再将以R3结点为根的子树调整为堆；3024473653918516c.以R3为根的子树满足堆特性。再将以R2结点为根的子树调整为堆；30244736 53859116第66页/共103页2023/3/1767建堆过程示例91472436538530169147243653308516以R2为根的子树满足堆特性。再将以R1结点为根的子树调整为堆d.调整结束后，整棵树为堆。3047243653859116第67页/共103页2023/3/1768

44、可见，初始建堆的过程也是反复筛选的过程.借助于筛选算法，排序表建立初始堆的过程为：for(i=n/2;i0;i-)HeapAdjust(R,i,n);第68页/共103页2023/3/1769堆排序：对n个元素的序列进行堆排序，先将其建成堆，以根结点与第n个结点交换；调整前n-1个结点成为堆，再以根结点与第n-1个结点交换；重复上述操作，直到整个序列有序。【算法8-10】堆排序算法voidHeapSort(datetypeR,intn)/*将序列R1.Rn按堆排序方法进行排序*for(i=n/2;i0;i-)HeapAdjust(R,i,n);/*将序列R1.Rn建成初始堆*/for(i=n;

45、i1;i-)R0=R1;/*堆顶R1与堆底元素Ri交换*/R1=Ri;Ri=R0;HeapAdjust(R,1,i-1);/*将R1.Ri-1重新调整为堆*/第69页/共103页2023/3/17705、性能分析：设树高为k，由二叉树的性质知：k=log2n+1。从根到叶的筛选，关键码比较次数至多为2(k-1)次，移动记录至多k次。共n-1次。因此堆排序最坏情况下，时间复杂度为O(nlog2n)。6、问题：(1)堆排序是稳定排序吗？举例说明。(2)如排序表用链式存储，可否采用此方法？(3)它的性能和快速排序相同，比较各自的特点。第70页/共103页2023/3/17718.5 归并排序归并排序

46、的思想是将几个相邻的有序表合并成一个总的有序表，本节主要介绍2-路归并排序。1两个有序表的合并二路归并排序的基本操作是将两个有序表合并为一个有序表。R:2538 46 75 18 37 40 46 78 80 s m m+1 tR1:182537384646757880st第71页/共103页2023/3/1772【算法算法8-118-11】两个有序表的合并void Merge(datatype R,datatype R1,int s,int m,int t)/*设两个有序子表Rs.Rm和Rm+1.Rt*/*将两个有序子表合并为一个有序表R1s.R1t*/i=s;j=m+1;k=s;while

47、(i=m&j=t)if(Ri.keyRj.key)R1k+=Ri+;else R1k+=Rj+;while(i=m)R1k+=Ri+;while(j=t)R1k+=Rj+;要注意：该合并算法的要求是两个有序子表是相邻的，即Rs.Rm和Rm+1.Rt。第72页/共103页2023/3/17732.2-路归并算法2-路归并的基本思想是：只有1个元素的表总是有序的，所以将排序表R1.n，看作是n个长度为len=1的有序子表，对相邻的两个有序子表两两合并到R11.n，使之生成表长len=2的有序表；再进行两两合并到R1.n中，直到最后生成表长len=n的有序表。这个过程需要log2n趟。第73页/共1

48、03页2023/3/177456 47 69 48 27 98 56 59 38 28 6647 56 48 69 27 98 56 59 28 38 6647 48 56 69 27 56 59 98 28 38 6627 47 48 56 56 59 69 98 28 38 6627 28 38 47 48 56 56 59 66 69 98第74页/共103页2023/3/1775【算法8-12】一趟归并算法void MergePass(datatype R,datatype R1,int len,int n)/*len是本趟归并中有序表的长度，从R1.Rn归并到R11.R1n中*/fo

49、r(i=1;i+2*len-1=n;i=i+2*len)Merge(R,R1,i,i+len-1,i+2*len-1);/*对两个长度为len 的有序表合并*/if(i+len-1n)Merge(R,R1,i,i+len-1,n);/*一组半的情况*/else if(i=n)while(i=n)R1i+=Ri+;/*最后一组没有合并者*/【算法8-13】2-路归并排序 void MergeSort(datatype R,datatype R1,int n)int len=1;while(lenn)MergePass(R,R1,len,n);len=2*len;MergePass(R1,R,le

50、n,n);第75页/共103页2023/3/177632-路归并排序的递归算法【算法8-14】2-路归并递归算法void MSort(datatype R,datatype R1,int s,int t)/*将RsRt归并排序为R1sR1t*/if(s=t)R1s=Rs;else m=(s+t)/2;/*平分*p表*/MSort(R,R1,s,m);/*递归地将Rsm归并为有序的R1sm*/MSort(R,R1,m+1,t);/*递归地将Rm+1t归并为有序的R1m+1t*/Merge(R1,R,s,m,t);/*将R1sm和R1m+1t归并到Rst*/void MergeSort(datat