数据结构课程讲义8ppt课件.ppt

《数据结构课程讲义8ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构课程讲义8ppt课件.ppt（106页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程讲义8ppt课件 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望1内排序内排序(Sorting)？简单地说，排序就是将一组杂乱无章的数简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增或递减）。据按一定的规律排列起来（递增或递减）。排序是计算机中经常遇到的操作，通常称排序是计算机中经常遇到的操作，通常称为分类或整序。为分类或整序。排序的几个基本概念排序的几个基本概念数据表数据表数据表数据表(Data List)(Data List)(Da

2、ta List)(Data List)待排序的数据对象的有限集待排序的数据对象的有限集待排序的数据对象的有限集待排序的数据对象的有限集合。合。合。合。关键字关键字关键字关键字(Key)(Key)作为排序依据的数据对象中的属性作为排序依据的数据对象中的属性作为排序依据的数据对象中的属性作为排序依据的数据对象中的属性域。域。域。域。主关键字主关键字主关键字主关键字 不同的数据对象若不同的数据对象若不同的数据对象若不同的数据对象若关键字互不相同关键字互不相同关键字互不相同关键字互不相同，则这种关键字称为主关键字。则这种关键字称为主关键字。则这种关键字称为主关键字。则这种关键字称为主关键字。排序的确切

3、定义排序的确切定义 使一组任意排列的对象变成使一组任意排列的对象变成使一组任意排列的对象变成使一组任意排列的对象变成一组一组一组一组按关键字线性有序按关键字线性有序按关键字线性有序按关键字线性有序的对象。的对象。的对象。的对象。用于排序测度的关键字通常称为排序码。用于排序测度的关键字通常称为排序码。用于排序测度的关键字通常称为排序码。用于排序测度的关键字通常称为排序码。排序的几个基本概念排序的几个基本概念排序算法的稳定性排序算法的稳定性排序算法的稳定性排序算法的稳定性 判断标准：排序码相同的数据判断标准：排序码相同的数据判断标准：排序码相同的数据判断标准：排序码相同的数据对象在排序过程中是否保

4、持前后次序不变。如对象在排序过程中是否保持前后次序不变。如对象在排序过程中是否保持前后次序不变。如对象在排序过程中是否保持前后次序不变。如 2,2,2*,12*,1，排序后若为，排序后若为，排序后若为，排序后若为1,2*,2 1,2*,2 则该排序方法是不稳定的。则该排序方法是不稳定的。则该排序方法是不稳定的。则该排序方法是不稳定的。内排序内排序内排序内排序与外排序与外排序 区分标准：区分标准：排序过程是否全部排序过程是否全部排序过程是否全部排序过程是否全部在在在在内存内存内存内存进行。进行。进行。进行。排序的时间开销排序的时间开销排序的时间开销排序的时间开销 它是衡量算法好坏的最重要的标它是

5、衡量算法好坏的最重要的标它是衡量算法好坏的最重要的标它是衡量算法好坏的最重要的标志。通常用算法执行中的志。通常用算法执行中的志。通常用算法执行中的志。通常用算法执行中的数据比较次数数据比较次数数据比较次数数据比较次数和和和和数据移动数据移动数据移动数据移动次数次数次数次数来衡量。来衡量。来衡量。来衡量。排序的方法有很多，但简单地判断那一种算排序的方法有很多，但简单地判断那一种算 法最好，以便能够普遍选用则是困难的。法最好，以便能够普遍选用则是困难的。评价排序算法好坏的标准主要有两条：算法评价排序算法好坏的标准主要有两条：算法 执行所需要的时间和所需要的附加空间。执行所需要的时间和所需要的附加空

6、间。另外，算法本身的复杂程度也是需要考虑另外，算法本身的复杂程度也是需要考虑 的一个因素。的一个因素。排序算法所需要的附加空间一般都不大，矛排序算法所需要的附加空间一般都不大，矛 盾并不突出。而排序是一种经常执行的一盾并不突出。而排序是一种经常执行的一 种运算，往往属于系统的核心部分，因此种运算，往往属于系统的核心部分，因此 排序的时间开销是算法好坏的最重要的标排序的时间开销是算法好坏的最重要的标 志。志。排排序序亦亦称称分分类类，是是计计算算机机进进行行数数据据处处理理的的一一种种基基本本运运算算，其其功功能能是是将将一一个个数数据据元元素素的的无无序序序序列列调调整整为为一一个个有有序序序

7、序列列。目目的的是是达达到到当当计计算算机机中中的的数数据据经经过过排排序序后后，提提高高工工作作效效率率和质量。是在线性表上施加的操作。和质量。是在线性表上施加的操作。排排序序码码就就是是指指作作为为排排序序依依据据的的数数据据项项。数数据元素可以有多个排序码。据元素可以有多个排序码。排序的精确定义：排序的精确定义：有有n个记录（元素）：个记录（元素）：R1，R2，R3，Rn及其对应的排序码序列：及其对应的排序码序列：K1，K2，K3，Kn所所确确定定的的1，2，.n的的一一种种排排列列p1,p2,p3,pn，使使得得相相应应的的排排序序码码满满足非递减（或非递增）关系：足非递减（或非递增）

8、关系：Kp1Kp2Kp3Kpn或或Kp1Kp2Kp3Kpn即成为即成为：Rp1,Rp2,Rp3,Rpn自自然然，不不同同的的排排序序策策略略就就得得到到不不同同的的排序过程；排序过程；策策略略相相同同但但排排序序所所采采用用的的排排序序方方法法不不同，都会有不同的排序算法。同，都会有不同的排序算法。常见的排序策略和方法有：常见的排序策略和方法有：直接插入排序直接插入排序shell插入排序（缩小增量排序）插入排序（缩小增量排序）插入策略插入策略二分插入排序二分插入排序表插入排序表插入排序直接交换排序（冒泡排序）直接交换排序（冒泡排序）交换策略交换策略快速排序快速排序直接选择排序直接选择排序选择策

9、略选择策略堆排序堆排序归并策略归并策略分配策略分配策略基数排序基数排序 为简单起见，数据的存储结构采用记为简单起见，数据的存储结构采用记录数组形式。记录数组的类型说明如下：录数组形式。记录数组的类型说明如下：typedef struct typedef struct keytype key;keytype key;datatype other;datatype other;rectype;rectype;rectype Rn;rectype Rn;其中其中n为记录总数加为记录总数加12插入排序插入排序 基本原理，每步将一个待排序的基本原理，每步将一个待排序的对象，按其关键字大小，插入到前面对象

10、，按其关键字大小，插入到前面已经排好序的一组对象适当位置上，已经排好序的一组对象适当位置上，直到对象全部插入为止。直到对象全部插入为止。直接插入排序直接插入排序(InsertSort)希尔排序希尔排序(ShellSort)2.1 直接插入排序直接插入排序(Insert Sort)基本思想：当插入第基本思想：当插入第i个对象时，个对象时，前面的前面的V0,V1,Vi-1已经排好序，已经排好序，此时，用此时，用vi的关键字与的关键字与Vi-1,Vi-2,的关键字顺序进行比较，找到插的关键字顺序进行比较，找到插入位置即将入位置即将Vi插入，原来位置上对插入，原来位置上对象向后顺移。象向后顺移。直接插

11、入排序举例直接插入排序举例i (0)(1)(2)(3)(4)(5)temp 21 25 49 25*16 08 251 21 25 49 25*16 08 492 21 25 49 25*16 08 25*3 21 25 25*49 16 08 164 16 21 25 25*49 08 08 5 08 16 21 25 25*49 直接插入排序算法直接插入排序算法INSERTSORT(rectype R)INSERTSORT(rectype R)INSERTSORT(rectype R)INSERTSORT(rectype R)int i,j;int i,j;int i,j;int i,j;

12、for(i=1;in;i+)for(i=1;in;i+)for(i=1;in;i+)for(i=1;i=0&temp.key=0&temp.key=0&temp.key=0&temp.keyRj.key)Rj+1 Rj+1 Rj+1 Rj+1Rj;j+;Rj;j+;Rj;j+;Rj;j+;Rj+1 Rj+1 Rj+1 Rj+1temp;temp;temp;temp;算法中引入附加记录算法中引入附加记录temp的作用：是进入的作用：是进入查找循环之前，它保存了查找循环之前，它保存了Ri的副本，使得的副本，使得不至于因记录的后移而丢失不至于因记录的后移而丢失Ri中的内容。中的内容。算法分析算法分析

13、直接插入排序算法由两重循环组成，对于有直接插入排序算法由两重循环组成，对于有直接插入排序算法由两重循环组成，对于有直接插入排序算法由两重循环组成，对于有n n个记录的排序，内循环表明完成一趟排序所需个记录的排序，内循环表明完成一趟排序所需个记录的排序，内循环表明完成一趟排序所需个记录的排序，内循环表明完成一趟排序所需进行的记录关键字间的比较和记录的后移。进行的记录关键字间的比较和记录的后移。进行的记录关键字间的比较和记录的后移。进行的记录关键字间的比较和记录的后移。若初始时关键字递增有序，这是最好情况。每若初始时关键字递增有序，这是最好情况。每若初始时关键字递增有序，这是最好情况。每若初始时关

14、键字递增有序，这是最好情况。每一趟排序中仅需进行一次关键字的比较，所以一趟排序中仅需进行一次关键字的比较，所以一趟排序中仅需进行一次关键字的比较，所以一趟排序中仅需进行一次关键字的比较，所以总的比较次数为总的比较次数为总的比较次数为总的比较次数为n-1n-1。在。在。在。在whilewhile循环之前和之中，循环之前和之中，循环之前和之中，循环之前和之中，至少要移动记录两次，所以总的比较次数为至少要移动记录两次，所以总的比较次数为至少要移动记录两次，所以总的比较次数为至少要移动记录两次，所以总的比较次数为2(n-1)2(n-1)。若初始时关键字递减有序，这是最坏情况。这若初始时关键字递减有序，

15、这是最坏情况。这若初始时关键字递减有序，这是最坏情况。这若初始时关键字递减有序，这是最坏情况。这时的记录比较和移动次数分别为：时的记录比较和移动次数分别为：时的记录比较和移动次数分别为：时的记录比较和移动次数分别为：直接插入排序的稳定性直接插入排序的稳定性直接插入排序是一种稳定的排序方直接插入排序是一种稳定的排序方法。法。原理：关键字相同的两个对象，在原理：关键字相同的两个对象，在整个排序过程中，不会通过比较而整个排序过程中，不会通过比较而相互交换。相互交换。2.2 希尔希尔(shell)排序排序1959年由年由D.L.Shell提出，又称缩小提出，又称缩小增量排序增量排序(Diminishi

16、ng-increment sort)。基本思想：在插入排序中，只比较相基本思想：在插入排序中，只比较相邻的结点，一次比较最多把结点移动邻的结点，一次比较最多把结点移动一个位置。如果对位置间隔较大距离一个位置。如果对位置间隔较大距离的结点进行比较，使得结点在比较以的结点进行比较，使得结点在比较以后能够一次跨过较大的距离，这样就后能够一次跨过较大的距离，这样就可以提高排序的速度。可以提高排序的速度。希尔排序的基本过程希尔排序的基本过程 设待排序的对象序列有设待排序的对象序列有n个对象，个对象，首先取一个整数首先取一个整数gapn作为间隔，将全作为间隔，将全部对象分为部对象分为gap个子序列，所有距

17、离为个子序列，所有距离为gap的对象放在同一个序列中，在每一的对象放在同一个序列中，在每一个子序列中分别施行直接插入排序，然个子序列中分别施行直接插入排序，然后缩小间隔后缩小间隔gap，如取，如取gap=gap/2，重，重复上述的子序列划分和排序工作，直到复上述的子序列划分和排序工作，直到最后取最后取gap为为1为止。为止。希尔排序示例希尔排序示例i (0)(1)(2)(3)(4)(5)gapi (0)(1)(2)(3)(4)(5)gap 21 25 49 25*16 08 21 25 49 25*16 08 1 21 -25*31 21 -25*3 25 -16 25 -16 49 -08

18、49 -08 21 16 08 25*25 49 21 16 08 25*25 492 21 -08 -25 22 21 -08 -25 2 16 -25*-49 16 -25*-49 08 16 21 25*25 49 08 16 21 25*25 493 08 16 21 25*25 49 13 08 16 21 25*25 49 1 08 16 21 25*25 49 08 16 21 25*25 49希尔排序算法希尔排序算法rectype Rn+d1;rectype Rn+d1;int dt;int dt;SHELLSORT(rectype R,int d)SHELLSORT(rect

19、ype R,int d)int i,j,k,h;int i,j,k,h;rectype temp;rectype temp;k k0;0;dl=1;dl=1;do do h hdk;dk;for(i=h+dl;in+dl;i+)for(i=h+dl;in+dl;i+)temp tempRi;Ri;j ji-h;i-h;while(temp.keyRj.key)while(temp.keyRj.key)pj+h pj+hRj;Rj;j jj-h;j-h;Rj+h Rj+htemp;temp;k+;k+;while(h!=1);while(h!=1);为什么为什么shellshell排序的时间性能

20、优于直接插入排排序的时间性能优于直接插入排序呢？因为直接插入排序在初态为正序时所需时间序呢？因为直接插入排序在初态为正序时所需时间最少，实际上，初态为基本有序时直接插入排序所最少，实际上，初态为基本有序时直接插入排序所需的比较和移动次数均较少。另一方面，当需的比较和移动次数均较少。另一方面，当n n值较值较小时，小时，n n和和n n2 2的差别也较小，即直接插入排序的最好的差别也较小，即直接插入排序的最好时间复杂度时间复杂度O(n)O(n)和最坏时间复杂度和最坏时间复杂度O(nO(n2 2)差别不大。差别不大。在在shellshell排序开始时增量较大，分组较多，每组的排序开始时增量较大，分

21、组较多，每组的记录数目少，故各组内直接插入较快，后来增量逐记录数目少，故各组内直接插入较快，后来增量逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素已经过多次排序，数组已经比较增多，但组内元素已经过多次排序，数组已经比较接近有序状态，所以新的一趟排序过程也较块。接近有序状态，所以新的一趟排序过程也较块。希尔排序中希尔排序中gapgap的取法的取法Shell最初的方案是最初的方案是 gap=n/2,gap=gap/2，直到，直到gap=1.Knuth的方案是的方案是gap=gap/3+1其它方案有：都取奇数为好；或其它方案有：都取奇数为好

22、；或gap互质为好等等。互质为好等等。希尔排序的时间复杂度希尔排序的时间复杂度对希尔排序的复杂度的分析很困难，在对希尔排序的复杂度的分析很困难，在特定情况下可以准确地估算关键字的比特定情况下可以准确地估算关键字的比较和对象移动次数，但是考虑到与增量较和对象移动次数，但是考虑到与增量之间的依赖关系，并要给出完整的数学之间的依赖关系，并要给出完整的数学分析，目前还做不到。分析，目前还做不到。Knuth的统计结论是，平均比较次数和的统计结论是，平均比较次数和对象平均移动次数在对象平均移动次数在n1.25 与与1.6n1.25之间。之间。希尔排序的稳定性希尔排序的稳定性希尔排序是一种不稳定的排序方法。

23、希尔排序是一种不稳定的排序方法。如序列如序列 3 2 2*53交换排序交换排序两种常见的交换排序两种常见的交换排序冒泡排序冒泡排序(Bubble Sort)快速排序快速排序(Quick Sort)基本原理基本原理：每一次两两比较待排序的记录每一次两两比较待排序的记录的排序码，只要是逆序的记录对，则进行的排序码，只要是逆序的记录对，则进行交换，直到所有的逆序对都交换完为止。交换，直到所有的逆序对都交换完为止。冒泡排序的基本思想冒泡排序的基本思想首首先先依依序序比比较较n个个待待排排序序记记录录的的一一端端开开始始，依依次次两两两两比比较较排排序序码码，只只要要是是逆逆序序，则则交交换换，这这样样

24、完完成成一一趟趟交交换换排排序序，结结果果就就是是将将最最大大（或或最最小小）的的记记录录交交换换到到最最后后面面（或或最最前前面面）；然然后后其其余余的的记记录录同同法法进进行行两两两两比比较较，每每一一趟趟都都将将较较大大（小小）元元素素交交换换到到最最后后（前前）面面，一一直直进进行行下下去去，直直到到最最后后一一个个记记录录排排完完或或没没有要交换的元素的时候为止。有要交换的元素的时候为止。3.1 冒泡排序冒泡排序冒泡排序的基本过程冒泡排序的基本过程首首先先从从R0到到Rn-1对对n个个元元素素比比较较其其排排序序码码，对对逆逆序序元元素素进进行行交交换换，完完成成一一趟趟排排序序时时

25、，将将排排序序码码值值最最到到的的元元素素几几交交换换到到最最后后一一个个位位置置，即即Rn-1，该过程相当于一趟冒泡；，该过程相当于一趟冒泡；然然后后，又又从从R0到到Rn-2中中又又进进行行一一趟趟交交换换冒冒泡泡，这这样样一一直直进进行行下下去去，直直到到最最后后一一个个元元素素R0或某一趟没有交换元素为止。或某一趟没有交换元素为止。3.1 ，冒泡排序，冒泡排序冒泡排序示例冒泡排序示例i (0)(1)(2)(3)(4)(5)21 25 49 25*16 08 1 08 21 25 49 25*16 2 08 16 21 25 49 25*3 08 16 21 25 25*49 4 08

26、16 21 25 25*49冒泡排序算法冒泡排序算法voidbubblesort(R)for(i=0;i=i;j+)if(Rj+1.key=temp.key)&(i=temp.key)&(i=temp.key)&(i=temp.key)&(ij)j-;if(ij)Ri+=Rj;if(ij)Ri+=Rj;if(ij)Ri+=Rj;if(ij)Ri+=Rj;while(Ri.key=temp.key)&(ij)i+;while(Ri.key=temp.key)&(ij)i+;while(Ri.key=temp.key)&(ij)i+;while(Ri.key=temp.key)&(ij)i+;if

27、(ij)Rj-=Ri;if(ij)Rj-=Ri;if(ij)Rj-=Ri;if(ij)Rj-=Ri;while(i!=j);while(i!=j);while(i!=j);while(i!=j);Ri=temp;Ri=temp;Ri=temp;Ri=temp;return i;return i;return i;return i;QUICKSORT(rectype R,int s1,int t1)QUICKSORT(rectype R,int s1,int t1)int i;int i;int i;int i;if(s1t1)if(s1t1)if(s1t1)if(s1t1)i=PARTITIO

28、N(R,s1,t1);i=PARTITION(R,s1,t1);i=PARTITION(R,s1,t1);i=PARTITION(R,s1,t1);QUICKSORT(R,s1,i-1);QUICKSORT(R,s1,i-1);QUICKSORT(R,s1,i-1);QUICKSORT(R,s1,i-1);QUICKSORT(R,i+1,t1);QUICKSORT(R,i+1,t1);QUICKSORT(R,i+1,t1);QUICKSORT(R,i+1,t1);快速排序的时间复杂度快速排序的时间复杂度2 2、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的、

29、最好情况是每次所取的基准都是当前无序区的、最好情况是每次所取的基准都是当前无序区的“中值中值中值中值”记录，划分的结果是基准的左右两个无序子区记录，划分的结果是基准的左右两个无序子区记录，划分的结果是基准的左右两个无序子区记录，划分的结果是基准的左右两个无序子区的长度大致相等。的长度大致相等。的长度大致相等。的长度大致相等。考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数考虑关键字的比较次数和对象移动次数1 1、最坏情况是每次划分选取的基准都是当前无序区、最坏情况是每次划分选取的基准都是当前无序区、最坏情况是每次划分选取的基准都是当前无序区

30、、最坏情况是每次划分选取的基准都是当前无序区中关键字最小（或最大）的记录，划分的结果是基中关键字最小（或最大）的记录，划分的结果是基中关键字最小（或最大）的记录，划分的结果是基中关键字最小（或最大）的记录，划分的结果是基准的左边（或右边）为空，划分前后无序区的元素准的左边（或右边）为空，划分前后无序区的元素准的左边（或右边）为空，划分前后无序区的元素准的左边（或右边）为空，划分前后无序区的元素个数减少一个，因此，排序必须做个数减少一个，因此，排序必须做个数减少一个，因此，排序必须做个数减少一个，因此，排序必须做n-1n-1趟，每一趟中趟，每一趟中趟，每一趟中趟，每一趟中需做需做需做需做n-in

31、-i次比较，所以最大比较次数为次比较，所以最大比较次数为次比较，所以最大比较次数为次比较，所以最大比较次数为 设设设设C(n)C(n)表示对长度为表示对长度为表示对长度为表示对长度为n n的序列进行快速排序所的序列进行快速排序所的序列进行快速排序所的序列进行快速排序所需的比较次数，显然，它应该等于对长度为需的比较次数，显然，它应该等于对长度为需的比较次数，显然，它应该等于对长度为需的比较次数，显然，它应该等于对长度为n n的无的无的无的无序区进行划分所需的比较次数序区进行划分所需的比较次数序区进行划分所需的比较次数序区进行划分所需的比较次数n-1n-1，加上递归地对，加上递归地对，加上递归地对

32、，加上递归地对划分所得的左右两个无序子区进行快速排序所需划分所得的左右两个无序子区进行快速排序所需划分所得的左右两个无序子区进行快速排序所需划分所得的左右两个无序子区进行快速排序所需的比较次数。假设文件长度的比较次数。假设文件长度的比较次数。假设文件长度的比较次数。假设文件长度n=2n=2k k ，k=logk=log2 2n n，因，因，因，因此有：此有：此有：此有：快速排序的记录移动次数不会大于比较快速排序的记录移动次数不会大于比较次数，所以，快速排序的最坏时间复杂度为次数，所以，快速排序的最坏时间复杂度为O(n2)；最好时间复杂度为；最好时间复杂度为O(nlog2n)。可以证明，快速排序

33、的平均时间复杂度可以证明，快速排序的平均时间复杂度也是也是O(nlog2n)。快速排序是不稳定的排序方法。快速排序是不稳定的排序方法。4选择排序选择排序两种常见的选择排序两种常见的选择排序直接选择排序直接选择排序堆排序堆排序基本原理基本原理:将待排序的结点分为已排序将待排序的结点分为已排序(初始为空初始为空)和为未排序两组，依次将未排和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组序的结点中值最小的结点插入已排序的组中。中。直接选择排序的基本思想直接选择排序的基本思想在在所所有有的的记记录录中中选选择择出出排排序序码码最最小小的的记记录，将其与第一个元素交换；录，将其与第一个元素

34、交换；然然后后其其余余的的记记录录中中选选择择出出次次小小的的记记录录与与第二个元素交换，一直进行下去；第二个元素交换，一直进行下去；直到最后一个记录排完为止。直到最后一个记录排完为止。4.1 直接选择排序直接选择排序直接选择排序过程直接选择排序过程首首先先从从R0到到Rn-1中中选选择择出出最最小小的的记记录录，将其与将其与R0交换；交换；然然后后，又又从从R1到到Rn-1中中选选择择出出最最小小的的记记录与录与R1交换；交换；这这样样，当当第第i趟趟时时从从R0到到Ri-1就就是是已已经经排排好序的，直到最后一个元素好序的，直到最后一个元素Rn-1排好为止。排好为止。4.1 直接选择排序直

35、接选择排序直直接接选选择择排排序序示示例例49386597761327491338659776492749132765977649384913273897764965491327384976976549132738494997657613273849496597761327384949657697直接选择排序算法直接选择排序算法SELECTSORT(rectype R)SELECTSORT(rectype R)int i,j,k;int i,j,k;int i,j,k;int i,j,k;rectype temp;rectype temp;rectype temp;rectype temp;f

36、or(i=0;in-1;i+)for(i=0;in-1;i+)for(i=0;in-1;i+)for(i=0;in-1;i+)k=i;k=i;k=i;k=i;for(j=i+1;jn;j+)for(j=i+1;jn;j+)for(j=i+1;jn;j+)for(j=i+1;jn;j+)if(Rj.keyRk.key)k=j;if(Rj.keyRk.key)k=j;if(Rj.keyRk.key)k=j;if(Rj.key=low(n/2)i=low(n/2)的结的结点都是叶子，因此以这些结点为根的子点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序树都已是堆。这样，我们只需依

37、次将序号为号为low(n/2)low(n/2)，low(n/2)-1low(n/2)-1，.，1 1的的结点作为根的子树都调整为堆即可。结点作为根的子树都调整为堆即可。我们以大根堆为例进行说明我们以大根堆为例进行说明 若已知结点若已知结点RiRi的左右子树已是堆，如何将以的左右子树已是堆，如何将以RiRi为为根的完全二叉树也调整为堆？根的完全二叉树也调整为堆？解决这一问题可采用解决这一问题可采用“筛选法筛选法”，其基本思想是：因，其基本思想是：因为为RiRi的左右子树已是堆，这两棵子树的根分别是各自子的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必须在树中关键字最大

38、的结点，所以我们必须在RiRi和它的左右和它的左右孩子中选取关键字最大的结点放到孩子中选取关键字最大的结点放到RiRi的位置上。若的位置上。若RiRi的关键字已是三者中的最大者，则无须做任何调整，以的关键字已是三者中的最大者，则无须做任何调整，以RiRi为根的子树已构成堆，否则必须将为根的子树已构成堆，否则必须将RiRi和具有最大关和具有最大关键字的左孩子键字的左孩子R2iR2i或右孩子或右孩子R2i+1R2i+1进行交换。假定进行交换。假定R2iR2i的关键字最大，将的关键字最大，将RiRi和和R2iR2i交换位置，交换之后交换位置，交换之后有可能导致有可能导致R2iR2i为根的子树不再是堆

39、，但由于为根的子树不再是堆，但由于R2iR2i的左的左右子树仍然是堆，于是可以重复上述过程，将以右子树仍然是堆，于是可以重复上述过程，将以R2iR2i为为根的子树调整为堆，根的子树调整为堆，.，如此逐层递推下去，最多可能，如此逐层递推下去，最多可能调整到树叶。调整到树叶。例子：例子：关键字序列为关键字序列为 42，13，91，23，24，16，05，88，n=8，故从第四个结点开始，故从第四个结点开始调整调整4242131391912323242416160505888842139123241605884242131391918888242416160505232342139188241605

40、23不调整不调整424213139191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆筛选算法筛选算法SIFT(rectype R,int i;int m)SIFT(rectype R,int i;int m)SIFT(rectype R,int i;int m)SIFT(rectype R,int i;int m)int j;int j;int j;int j;

41、rectype temp;rectype temp;rectype temp;rectype temp;temp=Ri;temp=Ri;temp=Ri;temp=Ri;j=2*i;j=2*i;j=2*i;j=2*i;while(j=m)while(j=m)while(j=m)while(j=m)if(jm)&(Rj.keyRj+1.key)j+;if(jm)&(Rj.keyRj+1.key)j+;if(jm)&(Rj.keyRj+1.key)j+;if(jm)&(Rj.keyRj+1.key)j+;if(temp.keyRj.key)if(temp.keyRj.key)if(temp.keyR

42、j.key)if(temp.key=1;i-)SIFT(R,i,n)由于建堆的结果把关键字最大的记录选到了堆顶的由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该将位置，而排序的结果应是升序，所以，应该将R1R1和和RnRn交换，这就得到了第一趟排序的结果。交换，这就得到了第一趟排序的结果。第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区R1R1到到Rn-1Rn-1调整调整为堆。这时对于当前堆来说，它的左右子树仍然是堆，所为堆。这时对于当前堆来说，它的左右子树仍然是堆，所以，可以调用以，可以调用SIFTSIFT函数将函数将R1R1到到Rn-1Rn-1

43、调整为大根堆，选调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录一个记录Rn-1Rn-1交换，如此反复进行下去。交换，如此反复进行下去。919188884242232324241616050513139188422324160513（a a）初始堆）初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591（b b）第一趟排序之后）第一趟排序之后（c c）重建的堆）重建的堆R1R1到到R7R788882424424223231313161605059191

44、8824422313160591050524244242232313131616888891910524422313168891（d d）第二趟排序之后）第二趟排序之后（e e）重建的堆）重建的堆R1R1到到R6R6424224241616232313130505888891914224162313058891（f f）第三趟排序之后）第三趟排序之后050524241616232313134242888891910524162313428891（g g）重建的堆）重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891（h h

45、）第四趟排序之后）第四趟排序之后131323231616050524244242888891911323160524428891（i i）重建的堆）重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891（j j）第五趟排序之后）第五趟排序之后050513131616232324244242888891910513162324428891（k k）重建的堆）重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891（l l）第六趟排序之后）第六趟排序之后0505

46、13131616232324244242888891910513162324428891（m m）重建的堆）重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891（n n）第七趟排序之后）第七趟排序之后050513131616232324244242888891910513162324428891堆排序算法堆排序算法HEAPSORT(rectype R)HEAPSORT(rectype R)int i;int i;rectype temp;rectype temp;for(i=n/2;i=1;i-)for(i=n/2;i=1

47、;i-)SIFT(R,i,n);SIFT(R,i,n);for(i=n;i=1;i-)for(i=n;i=1;i-)temp=R1;R1=Ri;temp=R1;R1=Ri;Ri=temp;Ri=temp;SIFT(R,1,i-1);SIFT(R,1,i-1);堆排序的时间复杂度堆排序的时间复杂度堆排序的时间复杂性为堆排序的时间复杂性为O(n log2n)空间复杂性为空间复杂性为 O(1)堆排序是不稳定的排序方法。堆排序是不稳定的排序方法。5归并排序归并排序基本原理，通过对两个有序结点序基本原理，通过对两个有序结点序列的合并来实现排序。列的合并来实现排序。所谓归并是指将若干个已排好序的所谓归并是

48、指将若干个已排好序的部分合并成一个有序的部分部分合并成一个有序的部分。两路归并的基本思想两路归并的基本思想归归并并排排序序是是利利用用“归归并并”技技术术来来进进行行排排序序，所所谓谓归归并并是是指指将将若若干干个个已已经经排排序序的的子子序序列列合合并并为为一一个个有有序序序序列列。其其算算法法比比较较简简单单，可可以以直直接接给给出。出。两路归并的示例两路归并的示例25 57 48 37 12 92 86 25 57 37 48 92 12 86 25 37 48 57 12 86 92 12 25 37 48 57 86 92 归并算法归并算法voidmerge(R,R1,low,mid

49、,hign)voidmerge(R,R1,low,mid,hign)/Rlow/Rlow到到到到RmidRmid与与与与Rmid+1Rmid+1到到到到RhighRhigh是是是是两两两两个个个个有有有有序序序序序序序序 列列列列，结结结结 果果果果 是是是是 合合合合 并并并并 为为为为 一一一一 个个个个 有有有有 序序序序 序序序序 列列列列 R1lowR1low到到到到R1high/R1high/i=low;j=mid+1;k=low;i=low;j=mid+1;k=low;while(i=mid&j=high)while(i=mid&j=high)if(Ri.key=Rj.key)i

50、f(Ri.key=Rj.key)R1k+=Ri+;R1k+=Ri+;else R1k+=Rj+;else R1k+=Rj+;while(i=mid)R1k+=Ri+;while(i=mid)R1k+=Ri+;while(j=high)R1k+=Rj+;while(j=high)R1k+=Rj+;归并排序就是利用上述归并操作实归并排序就是利用上述归并操作实现排序的。其基本思想是：将待排序列现排序的。其基本思想是：将待排序列R0R0到到Rn-1Rn-1看成看成n n个长度为个长度为1 1的有序子的有序子序列，把这些子序列两两归并，便得到序列，把这些子序列两两归并，便得到high(n/2)high(