数据结构c语言5.pptx

《数据结构c语言5.pptx》由会员分享，可在线阅读，更多相关《数据结构c语言5.pptx（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 排排序序是是指指将将一一组组数数据据元元素素按按某某个个数数据据项项值值的的大大小小排排列列成成一个有序序列的过程。一个有序序列的过程。排排序序是是计计算算机机程程序序设设计计中中经经常常使使用用的的一一种种重重要要操操作作，是是组织数据和处理数据的最基本最重要的运算之一。组织数据和处理数据的最基本最重要的运算之一。排排序序被被广广泛泛应应用用于于数数据据处处理理、情情报报检检索索、商商业业金金融融等等许许多领域。多领域。第1页/共92页9.6 分配排序（基数排序）分配排序（基数排序）第2页/共92页1 1记录、关键码和排序表：记录、关键码和排序表：记录：数据元素 关键码（或排序码）：作为排

2、序依据的数据项称为数据元素的关键码。排序表：若干个（n个）排序纪录组成的集合。排序表也称成为文件，主要操作是排序。2 2非递减序列、递减序列、非递增序列、递增有序非递减序列、递减序列、非递增序列、递增有序3 3稳定排序和非稳定排序稳定排序和非稳定排序 稳定排序稳定排序 ：记录的相对位置在排序前后不发生变化：记录的相对位置在排序前后不发生变化 不稳定排序：不稳定排序：第3页/共92页4 4内部排序和外部排序内部排序和外部排序 待排序的表完全放在内存中待排序的表完全放在内存中称为称为内排序内排序5 5对排序方法的评价对排序方法的评价空间性能：除排序表以外的内存占用情况。空间性能：除排序表以外的内存

3、占用情况。时间性能：时间性能：比较关键码的次数比较关键码的次数，数据移动的次数数据移动的次数。它们往往是排序表规模（它们往往是排序表规模（n n）的函数）的函数第4页/共92页6.6.记录和排序表的数据结构记录和排序表的数据结构 在本章的讨论中，除特殊声明外，一般采用在本章的讨论中，除特殊声明外，一般采用顺序结构顺序结构存存储排序表。储排序表。记录和排序表的类型定义如下：记录和排序表的类型定义如下：#define MAXNUM#define MAXNUM /*MAXNUM /*MAXNUM 为足够大的数为足够大的数*/typedef struct typedef struct keytype

4、key;keytype key;/*/*关键码字段关键码字段*/*/*其它信息其它信息*/datatypedatatype;/*/*记录类型记录类型 RecNode*/RecNode*/datatype RMAXNUM;datatype RMAXNUM;/*/*定义排序表定义排序表的存的存储储*/如不加特别说明，排序表中的记录如不加特别说明，排序表中的记录R1R1RnRn存放在存放在R1R1RnRn分量中，分量中，R0R0分量闲置或做监视哨分量闲置或做监视哨（n n是排序是排序表中记录的个数）。表中记录的个数）。第5页/共92页9.6 分配排序（基数排序）分配排序（基数排序）第6页/共92页

5、1 1 直接插入排序直接插入排序 2 2 折半插入排序折半插入排序 3 *3 *表插入排序表插入排序 3 3 希尔排序希尔排序 插入排序的基本思想是：每次将一个待排序的记录，插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表的适当位按其关键字大小插入到前面已经排好序的子表的适当位置，直到全部记录插入完成，整个表有序为止。置，直到全部记录插入完成，整个表有序为止。第7页/共92页9.2.1 9.2.1 直接插入排序直接插入排序 直直接接插插入入排排序序是是一一种种简简单单的的插插入入排排序序方方法法，基基本本思思想想为为：在在R1R1至至Ri-1Ri-1长长度

6、度为为i-1i-1的的子子表表已已经经有有序序的的情情况况下下，将将RiRi插插入入，得得到到R1R1至至RiRi长长度度为为i i 的的子子表表有有序序，这这样样通通过过n-1n-1趟趟（i=2.ni=2.n）之之后后，R1R1至至RnRn有序。有序。第8页/共92页例如例如，对于以下序列（为简便起见，对于以下序列（为简便起见，每一个记录只列出其排每一个记录只列出其排序码序码，用排序码代表记录）：，用排序码代表记录）：10 18 20 36 60 25 30 18 12 56 10 18 20 36 60 25 30 18 12 56 其中，前其中，前5 5个记录组成的子序列是有序的，这时要

7、将第个记录组成的子序列是有序的，这时要将第6 6个记录插入到前个记录插入到前5 5个记录组成的有序子序列中去，得到一个含个记录组成的有序子序列中去，得到一个含有有6 6个记录的新有序序列。完成这个插入首先需要找到插入位个记录的新有序序列。完成这个插入首先需要找到插入位置：置：202536202536，因此，因此2525应插入到记录应插入到记录2020和记录和记录3636之间，从而之间，从而得到以下新序列：得到以下新序列：10 18 20 25 36 60 30 18 12 56 10 18 20 25 36 60 30 18 12 56 这就是一趟直接插入排序的过程。这就是一趟直接插入排序的过

8、程。直直接接插插入入排排序序：仅仅有有一一个个记记录录的的表表总总是是有有序序的的，因因此此，对对n n个个记记录录的的表表，可可从从第第二二个个记记录录开开始始直直到到第第n n个个记记录录，逐逐个个向向有有序序表表中中进进行行插插入入操操作，从而得到作，从而得到n n个记录按关键码有序的表。个记录按关键码有序的表。第9页/共92页 R0R1R2R3R4R5R6R7R8R9R10初始:36201810602530181256i=2：(20)(2036)1810602530181256i=3：(18)(182036)10602530181256i=4：(10)(10182036)6025301

9、81256i=7：(30)(10182025303660)181256i=8：(18)(1018182025303660)1256第10页/共92页【算法算法9-19-1】直接插入排序直接插入排序void D_InsertSort(datatypeD_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、到合适位置*/第11页/共92页性能分析性能分析 空间性能空间性能：仅用了一个辅助单元：仅用了一个辅助单元R0R0作为监视哨，空间复作为监视哨，空间复杂度为杂度为O(1)O(1)。时间性能时间性能：向有序表中逐个插入记录的操作，进行了：向有序表中逐个插入记录的操作，进行了n n 1 1趟，每趟操作分为趟，每趟操作分为比较比较关键码和关键码和移动移动记录，而比较的次数和移记录，而比较的次数和移动记录的次数取决于初始序列的排列情况动记录的次数取决于初始序列的排列情况 。分三种情况讨论：。分三种情况讨论：第12页/共92页总比较次数总比较次数总移动次数总移动次数(2)(2)最坏情况下最坏情况下：即第

11、即第j j趟操作，插入记录需要同前面的趟操作，插入记录需要同前面的j j个记录进行个记录进行j j次次关键码比较，移动记录的次数为关键码比较，移动记录的次数为j+2j+2次。次。(1)(1)最好情况下最好情况下：即待排序列已按关键码有序，每趟操作只需即待排序列已按关键码有序，每趟操作只需1 1次比较，次比较，0 0次移动。即：次移动。即：总比较次数=n-1次 总移动次数=0次第13页/共92页(3)(3)平均情况下：平均情况下：即第即第j j趟操作，插入记录大约同前面的趟操作，插入记录大约同前面的j/2j/2个记录进行关键个记录进行关键码比较，移动记录的次数为码比较，移动记录的次数为j/2+2

12、j/2+2次。次。总比较次数总比较次数总移动次数总移动次数 由此，直接插入排序的时间复杂度为O(n2)。直接插入排序是一个稳定的排序方法。直接插入排序也可以在链式结构上实现。第14页/共92页9.2.2 9.2.2 折半插入排序折半插入排序直直接接插插入入排排序序的的基基本本操操作作是是向向有有序序表表中中插插入入一一个个记记录录，在在直直接接插插入入排排序序中中，插插入入位位置置的的确确定定是是通通过过对对有有序序表表中中关关键键码码的顺序比较得到的。的顺序比较得到的。既既然然是是在在有有序序表表中中确确定定插插入入位位置置，因因此此在在寻寻找找RiRi的的插插入入位位置置时时，就就可可以以

13、采采用用折折半半查查找找的的方方法法，用用折折半半查查找找方方法法查查找找RiRi的的插插入入位位置置，再再将将RiRi插插入入进进去去，使使得得RiRi到到RiRi有有序序，这种方法就是折半插入排序。这种方法就是折半插入排序。第15页/共92页【算法9-2】折半插入排序算法折半插入排序算法void B_InsertSort(datatype R,int n)/*对排序表R1.Rn作折半插入排序,n是记录的个数*/for(i=2;i=n;i+)R0=Ri;/*保存待插入元素*/low=1;high=i1;/*设置初始区间*/while(lowRmid.key)low=mid+1;/*插入位置在

14、高半区中*/else high=mid-1;/*插入位置在低半区中*/for(j=i-1;j=high+1;j-)/*high+1为插入位置*/Rj+1=Rj;/*后移元素，留出插入空位*/Rhigh+1=R0;/*将元素插入*/第16页/共92页时间效率时间效率 确定插入位置所进行的折半查找，定位一个关键码的位置需要比较次数至多为 次，所以比较次数时间复杂度为O(nlog2n)。相对直接插入排序，折半插入排序只能减少关键字间的比较次数，而移动记录的次数和直接插入排序相同，故时间复杂度仍为O(n2)。折半插入排序是一个稳定的排序方法。折半插入排序只适合于顺序存储的排序表。折半插入排序只适合于顺

15、序存储的排序表。第17页/共92页9.2.3 9.2.3 希尔排序希尔排序又又称称为为“缩缩小小增增量量排排序序”。是是19591959年年由由D.L.ShellD.L.Shell提提出出来来的的 基本思想：先选取一个小于先选取一个小于n n的整数的整数didi（称之为（称之为步长步长），），然后把排序表中的然后把排序表中的n n个记录分为个记录分为didi个组，从第一个记录开始，个组，从第一个记录开始，间隔为间隔为didi的记录为同一组的记录为同一组，各组内进行直接插入排序，一趟，各组内进行直接插入排序，一趟之后，间隔之后，间隔didi的记录有序，随着有序性的改善，减小步长的记录有序，随着有

16、序性的改善，减小步长didi（排序子表变大），重复进行，（排序子表变大），重复进行，直到直到di=1di=1（全部记录成为（全部记录成为一个排序表），使得间隔为一个排序表），使得间隔为1 1的记录有序，也就使整体达到了的记录有序，也就使整体达到了有序。有序。步长为步长为1 1时就是前面讲的直接插入排序。时就是前面讲的直接插入排序。第18页/共92页例：例：排序列表为：39,80,76,41,13,29,50,78,30,11,100,7,41,86 步长因子分别取5、3、1，则排序过程如下：3980764113295078301110074186P=5间隔为5的子序列分别为：39，29，100

17、，80，50，7，76，78，41，41，30，86，13，11。第19页/共92页第一趟排序结果，使得间隔为第一趟排序结果，使得间隔为5 5的字表有序：的字表有序：2974130113950764113100807886P=3子序列分别为子序列分别为:29,30,50,13,78:29,30,50,13,78，7,11,76,100,867,11,76,100,86，41,39,41,8041,39,41,80。第二趟排序结果：第二趟排序结果：1373929114130764150868078100P=1此此时时，序序列列“基基本本有有序序”，对对其其进进行行直直接接插插入入排排序序，得得到

18、到最最终结果：终结果：7111329303941415076788086100第20页/共92页【算法9-4】希尔排序的算法希尔排序的算法void ShellSort(datatype R,int n,int d,int t)/*按增量序列d0,d1 dt 1对排序表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=j h)Rj+h=Rj;/*记录后移*/Rj+h=R0;/*插入到正确位置*/第21页/共92页时效分析时效分析 希希尔尔排排序序时时效效分

19、分析析很很难难，关关键键码码的的比比较较次次数数与与记记录录移移动动次次数数依依赖赖于于步步长长因因子子序序列列的的选选取取，特特定定情情况况下下可可以以准准确确估估算算出出关关键键码码的的比比较较次次数数和和记记录录的的移移动动次次数数。目目前前还还没没有有人人给给出出选选取取最最好的步长因子序列的方法。好的步长因子序列的方法。步步长长因因子子序序列列可可以以有有各各种种取取法法，有有取取奇奇数数的的，也也有有取取质质数数的的，但但需需要要注注意意：步步长长因因子子中中除除1 1外外没没有有公公因因子子，且且最最后后一一个个步长因子必须为步长因子必须为1 1。希尔排序方法是一个希尔排序方法是

20、一个不稳定不稳定的排序方法。的排序方法。第22页/共92页9.6 分配排序（基数排序）分配排序（基数排序）第23页/共92页 交交换换排排序序的的基基本本思思想想是是：通通过过排排序序表表中中两两个个记记录录关关键键码码的的比比较较，若若与与排排序序要要求求相相逆逆，则则将将二二者者进进行行交交换换，直直至至没有反序的记录为止。没有反序的记录为止。交交换换排排序序的的特特点点是是：排排序序码码值值较较小小记记录录的的向向序序列列的的一一端移动，排序码值较大记录的向序列的另一端移动。端移动，排序码值较大记录的向序列的另一端移动。9.3.1 9.3.1 冒泡排序冒泡排序9.3.2 9.3.2 快速

21、排序快速排序第24页/共92页9.3.1 9.3.1 冒泡排序冒泡排序 设排序表为设排序表为R1.RnR1.Rn，对，对n n个记录的排序表进行冒泡排序个记录的排序表进行冒泡排序(Bubble Sort)(Bubble Sort)的过程是：的过程是：第第1 1趟，从第趟，从第1 1个记录开始到第个记录开始到第n n个记录，对个记录，对n n 1 1对对相邻的两相邻的两个个记录关键字进行比较，若与排序要求相逆，则将二者交换。记录关键字进行比较，若与排序要求相逆，则将二者交换。一趟之后，具有最大关键字的记录交换到了一趟之后，具有最大关键字的记录交换到了RnRn，第第2 2趟，从第趟，从第1 1个记

22、录开始到第个记录开始到第n n 1 1个记录继续进行第二趟冒个记录继续进行第二趟冒泡。泡。两趟之后，具有次最大关键字的记录交换到了两趟之后，具有次最大关键字的记录交换到了RnRn 11，如此重复，如此重复，n n 1 1趟后，在趟后，在R1.RnR1.Rn中，中，n n个记录按关键码有个记录按关键码有序。序。冒泡排序最多进行冒泡排序最多进行 n n 1 1趟，趟，在某趟的两两比较过程中，如果在某趟的两两比较过程中，如果一次交换都未发生，表明已经有序，一次交换都未发生，表明已经有序，则排序提前结束。则排序提前结束。第25页/共92页【算法9-5】冒泡排序算法冒泡排序算法 void Bubble_

23、Sort(datetype R,int n)/*对排序表R1.Rn进行冒泡排序，n是记录个数*/int 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;第26页/共92页效率分析效率分析空间效率：仅用了一个辅助单元。时间效率：总共要进行n-1趟冒泡，对j个记录的表进行一趟冒泡需要j-1次关键码比较。总比较次数总比较次数移动次数：最好情况下：待排序列已有序，不需移动。最坏情况下：每次比较后均要进行三次移动。移

24、动次数移动次数第27页/共92页9.3.2 9.3.2 快速排序快速排序1 1、快速排序的思想、快速排序的思想 快速排序是通过比较关键码、交换记录，以以某某个个记记录录为为界界(该该记记录录称称为为支支点点，通通常常取取第第一一个个元元素素)，将将待待排排序序列列分分成成两两部部分分。其中，一部分所有记录的关键码大于等于支点记录的关键码，另一部分所有记录的关键码小于支点记录的关键码。我们将待排序列按关键码以支点记录分成两部分的过程，称为一次（趟）划分划分。对各部分不断划分，直到每一步分只剩一个元素，整个序列则按关键码有序。第28页/共92页2 2、一次划分示例、一次划分示例【例9-5】对排序表

25、：49,14,38,74,96,65,8,49,55,27进行划分。划分过程如图9-5所示。设初始状态:49 14 38 74 96 65 8 49 55 27 14 38 74 96 65 8 49 55 27 low 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 第29页/共92页再从high向前搜索小于49的记录，找到后将其调整到low位置，得到结

26、果：27 14 38 8 96 65 49 55 74 low high 再从low向后搜索大于49的记录，找到后将其调整到high位置，得到结果：27 14 38 8 65 96 49 55 74 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第30页/共92页3 3、快速排序一次划分算法、快速排序一次划分算法【算法9-6】划分算法划分算法int Partition(datatype R,int low,int high)/*以Rlo

27、w为支点对Rlow.R high进行划分，返回支点记录最终的位置*/R0=Rlow;/*暂存支点记录*/while(lowhigh)/*从表的两端交替地向中间扫描*/while(low=R0.key)High-;if(lowhigh)Rlow=Rhigh;low+;/*将比支点小的交换到前面*/while(lowhigh&Rlow.keyR0.key)low+;if(lowhigh)Rhigh=Rlow;high ;/*将比支点大的交换到后面*/Rlow=R0;/*支点记录到位*/return low;/*返回支点记录所在位置*/第31页/共92页4 4、快速排序、快速排序经过划分之后，支点则

28、到了最终排好序的位置上，再分别对经过划分之后，支点则到了最终排好序的位置上，再分别对支点前后的两组继续划分下去，直到每一组只有一个记录为止，支点前后的两组继续划分下去，直到每一组只有一个记录为止，则是最后的有序序列，这就是快速排序。则是最后的有序序列，这就是快速排序。快速排序过程就是反复划分的过程，算法如下：【算法9-7】快速排序算法快速排序算法voidQuick_Sort(datatypeR,ints,intt)/*对Rs.Rt进行快速排序*/if(st)i=Partition(R,s,t)/*将表一分为二*/Quick_Sort(R,s,i1);/*对支点前端子表递归排序*/Quick_S

29、ort(R,i+1,t);/*对支点后端子表递归排序*/第32页/共92页49143874966584914387496658494955275527 快速排序的递归过程可用生成一棵二叉树形象地给出，右图为上例中待排序列对应递归调用过程的二叉树。38749684927554965145 5、效率分析、效率分析第33页/共92页 空空间间效效率率：快快速速排排序序是是递递归归的的，每每层层递递归归调调用用时时的的指指针针和和参参数数均均要要用用栈栈来来存存放放，递递归归调调用用层层次次数数与与上上述述二二叉叉树树的的深深度度一一致致。因因而而，存存储储开开销销在在理理想想情情况况下下为为O(lo

30、gO(log2 2n)n)，即即树树的的高高度；在最坏情况下，即二叉树是一个单链，为度；在最坏情况下，即二叉树是一个单链，为O(n)O(n)。时时间间效效率率：在在n n个个记记录录的的待待排排序序列列中中，一一次次划划分分需需要要约约有有=n n次次关关键键码码比比较较，时时效效为为O(n)O(n)，理理想想情情况况下下：每每次次划划分分，正正好好将将分分成成两两个个等等长长的的子子序序列列，则则需需要要的的排排序序趟趟数数为为=loglog2 2n n，故时间性能为故时间性能为O(nlogO(nlog2 2n)n)。第34页/共92页 最最坏坏情情况况下下：即即每每次次划划分分，只只得得到

31、到一一个个子子序序列列，时时效效为为O O(n(n2 2)。快快速速排排序序是是通通常常被被认认为为在在同同数数量量级级（O(nlogO(nlog2 2n)n)）的的排排序序方法方法中平均性能最好的。中平均性能最好的。但但若若初初始始序序列列按按关关键键码码有有序序或或基基本本有有序序时时，快快排排序序反反而而蜕蜕化化为为冒冒泡泡排排序序。为为改改进进之之，通通常常以以“三三者者取取中中法法”来来选选取取支支点点记记录录，即即将将排排序序区区间间的的两两个个端端点点与与中中点点三三个个记记录录关关键键码码居中的作为支点记录。居中的作为支点记录。快速排序是一个不稳定的排序方法（如：快速排序是一个

32、不稳定的排序方法（如：2 2，2 2，1 1）。第35页/共92页9.6 分配排序（基数排序）分配排序（基数排序）第36页/共92页选择排序仍然是基于排序码的比较而进行的。特特点点：顾名思义，选择排序是在每一趟排序中通过关键码比较，选择出关键码值最小（以正序为例）的记录，输出或置入相应的位置上，然后再从其余元素中选择最小。第第1 1趟趟，从n个记录中找出关键码最小的记录；第第2 2趟趟，从剩余的n-1个记录中找出关键码最小的记录；第第n-1n-1趟趟，从剩余的2个记录中找出关键码最小的记录。排序结束。选择排序需要选择排序需要n-1n-1趟趟。第37页/共92页 根据选择最小关键码记录的方式不同

33、，选择排序根据选择最小关键码记录的方式不同，选择排序又有多种方法，在本节中我们重点讲两种选择排序：又有多种方法，在本节中我们重点讲两种选择排序：9.4.1 9.4.1 简单选择排序简单选择排序9.4.3 9.4.3 堆排序堆排序第38页/共92页9.4.1 9.4.1 简单选择排序简单选择排序 特点：每次选择的过程是顺序进行的。特点：每次选择的过程是顺序进行的。1 1、基本思想、基本思想：第第1 1趟趟，从第，从第1 1个到第个到第n n个记录中选择关键码最小的记个记录中选择关键码最小的记录与第录与第1 1个记录交换；个记录交换；第第2 2趟趟，从第，从第2 2个到第个到第n n个记录中选择关

34、键码最小的记个记录中选择关键码最小的记录与第录与第2 2个记录交换；个记录交换；第第i i趟趟，从第从第i i个到第个到第n n个记录中选择关键码最小的记个记录中选择关键码最小的记录与第录与第i i个记录交换个记录交换;直到直到第第n-1n-1趟趟，从最后两个记录中选择较小的记录放置在，从最后两个记录中选择较小的记录放置在第第n-1 n-1 位置。排序结束。位置。排序结束。第39页/共92页2 2、示例、示例：设排序表：49 14 38 74 96 65 49 8 55 27第1趟之后：8 14 38 74 96 65 49 49 55 27第2趟之后：8 14 38 74 96 65 49

35、49 55 27 （在本位就不用交换）第3趟之后：8 14 27 74 96 65 49 49 55 38 第4趟之后：8 14 27 49 96 65 74 49 55 38。第9趟之后：8 14 27 38 49 49 55 65 74 96 第40页/共92页3 3、算法实现、算法实现【算法9-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

36、.key)k=j;/*k中存放关键码最小记录的下标*/if(i!=k)/*关键码最小的记录与第i个记录交换*/R0=Rk;Rk=Ri;Ri=R0;注意i,j,k的意义：i：控制趟循环；j:控制每趟中从第i个元素到第n个元素选择最小值的循环；k:用来指向本趟中到当前为止找到的最小元素。第41页/共92页4 4、性能分析、性能分析：从从算算法法中中可可看看出出，简简单单选选择择排排序序移移动动记记录录的的次次数较少，数较少，最多数据移动最多数据移动3(n-1)3(n-1)次，最少次，最少0 0次。次。但关键码的比较次数：但关键码的比较次数：第第1 1趟趟 (n-1)(n-1)次，次，第第2 2趟趟

37、 (n-2)(n-2)次，次，第第i i趟趟 (n-i)(n-i)次次,（i=1i=1，2 2，n-1)n-1)依依 然然 是是 (n*(n+1)/2(n*(n+1)/2，所所 以以 时时 间间 复复 杂杂 度度 仍仍 为为O(nO(n2 2)。第42页/共92页9.4.3 9.4.3 堆排序堆排序 继承了前面的工作继承了前面的工作简单选择排序的思想简单，易于实现，但其时间性能没有优势，这是因为在每趟的选择中，没有把前面选择过程中的一些有用信息继承下来，因此每趟选择都是顺序的一一进行，如果某一趟的选择能够把前面有用的一些信息继承下来，则定会减少本趟的比较次数，提高排序效率，堆排序就做到了这一点

38、。第43页/共92页如：序列 12,36,24,85,47,30,53,91是一个小顶堆；序列 91,47,85,24,36,53,30,16是一个大顶堆。1.1.堆的定义堆的定义 设有n个元素的序列 R1，R2，Rn，当且仅当满足下述关系之一时，称之为堆。前者称为小顶堆，后者称为大顶堆。kik2ik2i+1kik2ik2i+1或其中i=1,2,n/2 第44页/共92页 在完全二叉树上，双亲和左右孩子之间的编号就是i和2i、2i+1的关系。因此一个序列可以和一棵完全二叉树对应起来，用双亲其左、右孩子之间的关系可以直观的分析是否符合堆的特性。如果该序列是一个堆，则对应的这棵完全二叉树的特点是：

39、所有分支结点的值均不小于(或不大于)其子女的值，即每棵子树根结点的值是最大(或最小)的。堆特点：堆顶元素是整个序列中最大(或最小)的元素。8516364730532491小顶堆：16，36，24，85，47，30，53，914791243653308516大顶堆：91，47，85，24，36，53，30，16第45页/共92页2 2堆排序堆排序 堆特点：堆顶元素是整个序列中最大堆特点：堆顶元素是整个序列中最大(或最小或最小)的元素。的元素。若若将将排排序序表表按按关关键键码码建建成成堆堆，堆堆顶顶元元素素就就是是选选择择出出的的最最大元素（或最小），这样就得到大元素（或最小），这样就得到n n

40、个元素中的第一个的元素。个元素中的第一个的元素。然然后后，再再对对剩剩下下的的n-1n-1个个元元素素建建成成堆堆，得得到到n n个个元元素素中中关关键键码码次次大大 (或或次次小小)的的元元素素。以以此此类类推推，如如此此反反复复，直直到到进进行行n-1n-1次次后后，排排序序结结束束，便便得得到到一一个个按按关关键键码码有有序序的的序序列列。称称这这个过程为堆排序。个过程为堆排序。因此，实现堆排序需解决两个问题：因此，实现堆排序需解决两个问题：1.1.如何将如何将n n个元素的排序序列按关键码建成堆（初始堆）；个元素的排序序列按关键码建成堆（初始堆）；2.2.怎样将剩余的怎样将剩余的n-1

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

42、918553474716853091第48页/共92页第二个问题的背景第二个问题的背景：输出堆顶元素后，将堆底元素送入堆顶（或将堆顶元素与堆底元素交换），堆可能被破坏。破坏的情况仅是根结点和其左右孩子之间可能不满足堆的特性，而其左右子树仍然是局部的堆。在这种情况下，将其R1 Ri整理成堆。（i=n-1.1)调整方法：调整方法：将根结点与左、右孩子中较小(大顶堆为较大)的进行交换。若与左孩子交换，则左子树堆可能被破坏，且仅左子树的根结点处不满足堆的性质；若与右孩子交换，则右子树堆可能被破坏，且仅右子树的根结点处不满足堆的性质。继续对不满足堆性质的子树进行上述操作，直到满足了堆性质或者到叶子结点，

43、堆被建成。称这个自根结点到叶子结点的调整过程为筛选筛选。第49页/共92页9147243653308516a.初始堆。输出堆顶元素,再将最后一个元素放入堆顶(为了操作简便，将堆顶元素R1与Rn交换)。b.堆被破坏调整：根结点与左右子女较大者比较，若比根大，交换c.右子树不满足堆，继续调整 d.到了叶子结点，调整结束，堆建成。164724365330859124854736533016912485473616305312第50页/共92页3.3.【算法算法9-99-9】筛选算法筛选算法voidHeapAdjust(datetypeR,ints,intt)/*以Rs为根的子树只有Rs与其左右孩子之

44、间可能不满足堆特性*/*进行调整使以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；/*插入*/第51页/共92页4 4、堆排序的实现、堆排序的实现 初步的堆排序算法：初步的堆排序算法：1 1、建成初始堆；、建成初始堆；2 2、for(i=n;i1;i-)for(i=n;i1;i-)R1Ri;R1Ri;HeapAdjust(R,1,i-1);Hea

45、pAdjust(R,1,i-1);第52页/共92页再讨论第一个问题：对原始排序表建初始堆的过程。对原始序列建堆过程，就是一个反复进行筛选的过程。对原始序列建堆过程，就是一个反复进行筛选的过程。仍然通过对应的完全二叉树分析：对n个结点的完全二叉树，可以认为：以叶子为根的子树（只有它自己）已满足堆特性，因此从最后一个分支结点开始，把每棵子树调整为堆，直到根结点为止，整棵树成为堆。最后一个分支结点是第 个结点。第53页/共92页例：建堆的过程例：建堆的过程：设初始排序序列：30 24 85 16 36 53 91 47，建成大顶堆。3024163653918547a.8个结点的初始状态。从R4结点

46、开始调整；b.调整结束后，以R4为根的子树满足堆特性。再将以R3结点为根的子树调整为堆；3024473653918516c.以R3为根的子树满足堆特性。再将以R2结点为根的子树调整为堆；30244736 53859116第54页/共92页91472436538530169147243653308516以R2为根的子树满足堆特性。再将以R1结点为根的子树调整为堆d.调整结束后，整棵树为堆。3047243653859116可见，初始建堆的过程也是反复筛选的过程.借助于筛选算法，排序表建立初始堆的过程为：for(i=n/2;i0;i-)HeapAdjust(R,i,n);第55页/共92页堆排序堆排

47、序：对n个元素的序列进行堆排序，先将其建成堆，以根结点与第n个结点交换；调整前n-1个结点成为堆，再以根结点与第n-1个结点交换；重复上述操作，直到整个序列有序。【算法9-10】堆排序算法堆排序算法voidHeapSort(datetypeR,intn)/*将序列R1.Rn按堆排序方法进行排序*for(i=n/2;i0;i-)HeapAdjust(R,i,n);/*将序列R1.Rn建成初始堆*/for(i=n;i1;i-)R0=R1;/*堆顶R1与堆底元素Ri交换*/R1=Ri;Ri=R0;HeapAdjust(R,1,i-1);/*将R1.Ri-1重新调整为堆*/第56页/共92页5 5、性

48、能分析、性能分析：设树高为设树高为k k，由二叉树的性质知：，由二叉树的性质知：k=k=loglog2 2n n +1+1。从根到叶的筛选，关键码比较次数至多为。从根到叶的筛选，关键码比较次数至多为2(k-2(k-1)1)次，移动记录至多次，移动记录至多k k次。共次。共n-1n-1次。次。因此堆排序最坏情况下，时间复杂度为因此堆排序最坏情况下，时间复杂度为O(nlogO(nlog2 2n)n)。第57页/共92页9.6 分配排序（基数排序）分配排序（基数排序）第58页/共92页9.5 9.5 归并排序归并排序归并排序的思想是将几个相邻的有序表合并成一个总的有序表，本节主要介绍2-路归并排序。

49、1 1两个有序表的合并两个有序表的合并二路归并排序的基本操作是将两个有序表合并为一个有序表。R:2538 46 75 18 37 40 46 78 80 s m m+1 tR1:182537384646757880st第59页/共92页【算法算法9-119-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(i=m&j=t)if(Ri.keyRj.key)R1k+=Ri

50、+;else R1k+=Rj+;while(i=m)R1k+=Ri+;while(j=t)R1k+=Rj+;要注意：该合并算法的要求是两个有序子表是相邻的，即Rs.Rm和Rm+1.Rt。第60页/共92页2.2-2.2-路归并算法路归并算法2-路归并的基本思想是：只有1个元素的表总是有序的，所以将排序表R1.n，看作是n个长度为len=1的有序子表，对相邻的两个有序子表两两合并到R11.n，使之生成表长len=2的有序表；再进行两两合并到R1.n中，直到最后生成表长len=n的有序表。这个过程需要log2n趟。第61页/共92页56 47 69 48 27 98 56 59 38 28 664