数据结构 李云清 杨庆红 揭安全.pptx

《数据结构 李云清 杨庆红 揭安全.pptx》由会员分享，可在线阅读，更多相关《数据结构 李云清 杨庆红 揭安全.pptx（50页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第10章章 内排序内排序 排序是数据处理过程中经常使用的一种重要的运排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的各算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。算法的稳定性等进行了讨论。10.1 排序的基本概念 假设一个文件是由假设一个文件是由n n个记录个记录R R1 1，R R2 2，R Rn n组成，组成，所谓排序就是以记录中某个所谓排序就是以记录中某个(或几个或几个)字段值不减字段值不减(或或不增不增)的次序将这的次序将这n

2、n个记录重新排列，称该字段为排个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。键码可以作为排序码，但排序码不一定要是关键码。第1页/共50页 按排序过程中使用到的存储介质来分，可以将排按排序过程中使用到的存储介质来分，可以将排序分成序分成两大类两大类:内排序和外排序内排序和外排序。内排序内排序是指在排序过程中所有数据均放在内存中是指在排序过程中所有数据均放在内存中处理，不需要使用外存的排序方法。而对于数据量很处理，不需要使用外存的排序方法。而对于数据量很大的文件，在内存不足的情况下

3、，则还需要使用外存，大的文件，在内存不足的情况下，则还需要使用外存，这种排序方法称为这种排序方法称为外排序外排序。排序码相同的记录，若经过排序后，这些记录排序码相同的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是仍保持原来的相对次序不变，称这个排序算法是稳稳定的定的。否则，称为。否则，称为不稳定的排序算法不稳定的排序算法。第2页/共50页评价排序算法优劣的标准评价排序算法优劣的标准 ：首先考虑算法执行所需的时间，这主要是用执行首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动次数来度量；过程中的比较次数和移动次数来度量；其次考虑算法执行所需要的附加空间。其

4、次考虑算法执行所需要的附加空间。当然，保证算法的正确性是不言而喻的，可读性等当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。也是要考虑的因素。第3页/共50页排序算法如未作特别的说明，使用的有关定义如下排序算法如未作特别的说明，使用的有关定义如下 ：/*/*常见排序算法的头文件，文件名常见排序算法的头文件，文件名table.h*/table.h*/#define MAXSIZE 100 /*#define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/typedef int keytype;/*typedef int keytype;/*定义排序码类

5、型为整数类型定义排序码类型为整数类型*/typedef struct typedef struct keytype key;keytype key;/*/*此处还可以定义记录中除排序码外的其它域此处还可以定义记录中除排序码外的其它域*/recordtype;/*recordtype;/*记录类型的定义记录类型的定义*/typedef struct typedef struct recordtype rMAXSIZE+1;recordtype rMAXSIZE+1;int length;/*int length;/*待排序文件中记录的个数待排序文件中记录的个数*/table;/*table;/*

6、待排序文件类型待排序文件类型*/为了方便，r0一般不用于存放排序码，在一些排序算法中它可以用来作为中间单元存放临时数据。length域是待排序的记录个数，它必须不大于MAXSIZE，这样，第1length个记录的排序码分别存于r1.keyrlength.key中 第4页/共50页10.2 插入排序插入排序 插入排序的基本方法是插入排序的基本方法是:将待排序文件中的记录，将待排序文件中的记录，逐个地按其排序码值的逐个地按其排序码值的大小插入到目前已经排好序的若干个记录组成的文件中大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。的适当位置，并保持新文件有序。10.2.

7、1 直接插入排序 直接插入排序算法的思路是直接插入排序算法的思路是:初始可认为文件中的初始可认为文件中的第第1 1个记录己排好序，然后将第个记录己排好序，然后将第2 2个到第个到第n n个记录依次插个记录依次插入已排序的记录组成的文件中。在对第入已排序的记录组成的文件中。在对第i i个记录个记录R Ri i进行进行插入时，插入时，R R1 1，R R2 2，R Ri-1i-1已排序，将记录已排序，将记录R Ri i的排序码的排序码keykeyi i与已经排好序的排序码从右向左依次比较，找到与已经排好序的排序码从右向左依次比较，找到R Ri i应插入的位置，将该位置以后直到应插入的位置，将该位置

8、以后直到R Ri-1i-1各记录顺序后移，各记录顺序后移，空出该位置让空出该位置让R Ri i插入。插入。第5页/共50页一组记录的排序码分别为一组记录的排序码分别为:312312，126126，272272，226226，2828，165165，123 123 初初始始时时将将第第1 1个个排排序序码码作作为为已已经经排排好好序序的的，把把排排好好序序的的数数据据记记录录放放入入中中括括号号 中中，表表示示有有序序的的文文件件，剩剩下下的在中括号外，如下所示：的在中括号外，如下所示：312312，126126，272272，226226，2828，165165，123 123 设设前前3 3

9、个个记记录录的的排排序序码码已已重重新新排排列列有有序序，构构成成一一个个含含有有3 3个记录的有序文件个记录的有序文件:126126，272272，312312，226226，2828，165165，123 123 现在要将第现在要将第4 4个排序码个排序码226226插入插入 ！第6页/共50页126126，272272，312312，226226，2828，165165，123123现在要将第现在要将第4 4个排序码个排序码226226插入插入 ！将待插入的排序码将待插入的排序码226226和已经有序的最后一个排和已经有序的最后一个排序码序码312312比较，因为待插入的排序码比较，因为

10、待插入的排序码226226小于小于312312，所，所以以226226肯定要置于肯定要置于312312的前面，至于是否就是置于的前面，至于是否就是置于312312的前一个位置，此时还不能确定，需要继续向左比较；的前一个位置，此时还不能确定，需要继续向左比较；将所有大于待插入排序码将所有大于待插入排序码226226的那两个排序码的那两个排序码312312和和272272依次后移一个位置，在空出的位置插入待依次后移一个位置，在空出的位置插入待排序的排序码排序的排序码226226，得一含有，得一含有4 4个记录的有序文件：个记录的有序文件：126126，226226，272272，312312，28

11、28，165165，123 123 第7页/共50页需要注意的是，当待插入排序码小于所有已排序的需要注意的是，当待插入排序码小于所有已排序的排序码时，如在插入第排序码时，如在插入第5 5个值个值2828时：时：126126，226226，272272，312312，2828，165165，123123算法设计的时候如处理？算法设计的时候如处理？方法之一：设置“哨兵”第8页/共50页void insertsort(table*tab)void insertsort(table*tab)int i,j;int i,j;for(i=2;ilength;i+)/*for(i=2;ilength;i+)

12、/*依次插入从第依次插入从第2 2个开始的所有元素个开始的所有元素*/j=i-1;j=i-1;tab-r0.key=tab-ri.key;/*tab-r0.key=tab-ri.key;/*设置哨兵，准备找插入位置设置哨兵，准备找插入位置*/while(tab-r0.keyrj.key)/*while(tab-r0.keyrj.key)/*找插入位置并后移找插入位置并后移*/tab-rj+1.key=tab-rj.key;/*tab-rj+1.key=tab-rj.key;/*后移后移*/j=j-1;/*j=j-1;/*继续向前（左）查找继续向前（左）查找*/tab-rj+1.key=tab-

13、r0.key;tab-rj+1.key=tab-r0.key;/*/*插插入入第第i i个个元元素素的的副副本本，即即前前面面设设置置的的哨哨兵兵*/算法算法10.1 10.1 直接插入排序算法直接插入排序算法 第9页/共50页设设待待排排序序的的7 7记记录录的的排排序序码码为为312312，126126，272272，226226，2828，165165，123123，直直接接插插入入排排序序算法的执行过程如图算法的执行过程如图10.210.2所示。所示。哨兵哨兵 排序码排序码 312 312，126126，272272，226226，2828，165165，123123初始初始 （）（）

14、312312，126126，272272，226226，2828，165165，123123i=2i=2：（126126）126126，312312，272272，226226，2828，165165，123123i=3i=3：（272272）126126，272272，312312，226226，2828，165165，123123i=4i=4：（226226）126126，226226，272272，312312，2828，165165，123123i=5i=5：（2828）2828，126126，226226，272272，312312，165165，123123i=6i=6：（1651

15、65）2828，126126，165165，226226，272272，312312，123123i=7i=7：（123123）2828，123123，126126，165165，226226，272272，312312图图10.2 10.2 直接插入排序算法执行过程示意图直接插入排序算法执行过程示意图 第10页/共50页直接插入排序算法执行时间的分析：直接插入排序算法执行时间的分析：最好的情况最好的情况 ：即初始排序码开始就是有序的情况下，因为当插即初始排序码开始就是有序的情况下，因为当插入第入第i i个排序码时，该算法内循环个排序码时，该算法内循环whilewhile只进行一次条件只进行一

16、次条件判断而不执行循环体，外循环共执行判断而不执行循环体，外循环共执行n-1n-1次，其循环体次，其循环体内不含内循环每次循环要进行内不含内循环每次循环要进行2 2次移动操作，所以在最次移动操作，所以在最好情况下，直接插入排序算法的比较次数为好情况下，直接插入排序算法的比较次数为(n-1)(n-1)次，次，移动次数为移动次数为2*(n-1)2*(n-1)次。次。第11页/共50页最坏情况最坏情况 ：即初始排序码开始是逆序的情况下，因为当插入即初始排序码开始是逆序的情况下，因为当插入第第i i个排序码时，该算法内循环个排序码时，该算法内循环whilewhile要执行要执行i i次条件判次条件判断

17、，循环体要执行断，循环体要执行i-li-l次，每次要移动次，每次要移动1 1个记录，外循个记录，外循环共执行环共执行n-1n-1次，其循环体内不含内循环每次循环要次，其循环体内不含内循环每次循环要进行进行2 2次移动操作，所以在最坏情况下，比较次数为次移动操作，所以在最坏情况下，比较次数为(1+2+n)*(n-1)(1+2+n)*(n-1)，移动次数为，移动次数为(1+2+2+2+n+2)*(n-1)(1+2+2+2+n+2)*(n-1)。假设待排序文件中的记录。假设待排序文件中的记录以各种排列出现的概率相同，因为当插入第以各种排列出现的概率相同，因为当插入第i i个排序码个排序码时，该算法内

18、循环时，该算法内循环whilewhile平均约要执行平均约要执行i/2i/2次条件判断，次条件判断，循环体要执行（循环体要执行（i-li-l）/2/2次，外循环共执行次，外循环共执行n-1n-1次，所以次，所以平均比较次数约为平均比较次数约为(2+3+n)/2*(n-1)(2+3+n)/2*(n-1)，平均移动次，平均移动次数为数为(n-1)*(2+1+3+1+n+1)/2(n-1)*(2+1+3+1+n+1)/2，也即直接插入排序，也即直接插入排序算法的时间复杂度为算法的时间复杂度为O(nO(n2 2)。第12页/共50页10.2.2 二分法插入排序二分法插入排序 二分法插入排序的思想：二分

19、法插入排序的思想：根据插入排序的基本思想，在找第根据插入排序的基本思想，在找第i i个记录的插入个记录的插入位置时，前位置时，前i-li-l个记录已排序，将第个记录已排序，将第i i个记录的排序码个记录的排序码keyikeyi和已排序的前和已排序的前i-1i-1个的中间位置记录的排序码进行个的中间位置记录的排序码进行比较，如果比较，如果keyikeyi小于中间位置记录排序码，则可以在小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后半部继续使用前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定二分法查找，直到查找范围为空，即可确定keyikey

20、i的插的插入位置。入位置。第13页/共50页void binarysort(table*tab)void binarysort(table*tab)int i,j,left,right,mid;int i,j,left,right,mid;for(i=2;ilength;i+)/*for(i=2;ilength;i+)/*依次插入从第依次插入从第2 2个开始的所有元素个开始的所有元素*/tab-r0.key=tab-ri.key;/*tab-r0.key=tab-ri.key;/*保存待插入的元素保存待插入的元素*/left=1;right=i-1;/*left=1;right=i-1;/*设

21、置查找范围的左、右位置值设置查找范围的左、右位置值*/while(left=right)/*while(leftri.keyrmid.key)right=mid-1;if(tab-ri.keyrmid.key)right=mid-1;else left=mid+1;else left=mid+1;/*/*插入位置为插入位置为left*/left*/for(j=i-1;j=left;j-)tab-rj+1.key=tab-rj.key;/*for(j=i-1;j=left;j-)tab-rj+1.key=tab-rj.key;/*后移后移,空出插入位置空出插入位置*/tab-rleft.key=

22、tab-r0.key;/*tab-rleft.key=tab-r0.key;/*插入第插入第i i个元素的副本个元素的副本*/*/*算法算法10.2 10.2 二分法插入排序算法二分法插入排序算法*/第14页/共50页 设待排序的设待排序的7 7记录的排序码为记录的排序码为312312，126126，272272，226226，2828，165165，123123，在前，在前6 6个记录已经排序的情况个记录已经排序的情况下，使用二分法插入排序算法插入第下，使用二分法插入排序算法插入第7 7个记录的排序码个记录的排序码123123的执行过程示意如图的执行过程示意如图10.310.3所示（见书本）

23、。所示（见书本）。二分法插入排序算法，在查找第二分法插入排序算法，在查找第i i个记录的插入位个记录的插入位置时，每执行一次置时，每执行一次whilewhile循环体，查找范围缩小一半，循环体，查找范围缩小一半，和直接插入排序的比较次数对比，二分法插入的比较和直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的最多比较次数，而一般要多次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。总体上讲，当于直接插入排序的最少比较次数。总体上讲，当n n较较大时，二分法插入排序的比较次数远少于直接插入排大时，二分法插入排序的比较次数远少于直接插入排序的平均比较次数，

24、但二者所要进行的移动次数相等，序的平均比较次数，但二者所要进行的移动次数相等，故二分法插入排序的时间复杂度也是故二分法插入排序的时间复杂度也是O(nO(n2 2)，所需的附，所需的附加存储空间为一个记录空间。加存储空间为一个记录空间。第15页/共50页10.2.3 表插入排序表插入排序 二分法插入排序比较次数通常比直接插入排序的二分法插入排序比较次数通常比直接插入排序的比较次数少，但移动次数相等。表插入排序将在不进比较次数少，但移动次数相等。表插入排序将在不进行记录移动的情况下，利用存储结构有关信息的改变行记录移动的情况下，利用存储结构有关信息的改变来达到排序的目的。来达到排序的目的。给每个记

25、录附设一个所谓的指针域给每个记录附设一个所谓的指针域linklink，它的类型，它的类型为整型，为整型，表插入排序的思路：表插入排序的思路：在插入第在插入第i i个记录个记录R Ri i时，时，R R1 1，R R2 2，R Ri-1i-1已经通过各自的指针域已经通过各自的指针域linklink按排序码按排序码不减的次序连接成一个（静态链）表，将记录不减的次序连接成一个（静态链）表，将记录R Ri i的排的排序码序码keykeyi i与表中已经排好序的排序码从表头向右、或与表中已经排好序的排序码从表头向右、或称向后依次比较，找到称向后依次比较，找到R Ri i应插入的位置，将其插入在应插入的位

26、置，将其插入在表中，使表中各记录的排序码仍然有序。表中，使表中各记录的排序码仍然有序。第16页/共50页/*/*表插入排序定义的头文件，文件名为：表插入排序定义的头文件，文件名为：table2.h*/table2.h*/#define MAXSIZE 100 /*#define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/typedef int keytype;/*typedef int keytype;/*定义排序码类型为整数类型定义排序码类型为整数类型*/typedef structtypedef struct keytype key;keytype key

27、;int link;int link;/*/*此处还可以定义记录中除排序码外的其它域此处还可以定义记录中除排序码外的其它域*/recordtype;/*recordtype;/*记录类型的定义记录类型的定义*/typedef structtypedef struct recordtype rMAXSIZE+1;recordtype rMAXSIZE+1;int length;/*int length;/*待排序文件中记录的个数待排序文件中记录的个数*/table2;/*table2;/*待排序文件类型待排序文件类型*/第17页/共50页表插入排序算法的示意如图表插入排序算法的示意如图10.41

28、0.4所示（见书本）所示（见书本）对于将一个值为对于将一个值为x x的记录，插入到一个已排序（不的记录，插入到一个已排序（不减）的单链表减）的单链表headhead中，使新的单链表的结点值以不减中，使新的单链表的结点值以不减序排列，读者容易给出解决此问题的算法。序排列，读者容易给出解决此问题的算法。表插入排序算法：初始时，表插入排序算法：初始时，r0.Linkr0.Link用于存放表中用于存放表中第第1 1个记录的下标，个记录的下标，r0.Linkr0.Link的值为的值为1 1，排序结束时，排序结束时，r0.Linkr0.Link中存放的是所有排序码中值最小的对应记录的中存放的是所有排序码中

29、值最小的对应记录的下标，其它的排序码通过各自的指针域下标，其它的排序码通过各自的指针域linklink按不减的次按不减的次序连接成一个（静态链）表，最大的排序码对应的序连接成一个（静态链）表，最大的排序码对应的linklink为为0 0。第18页/共50页void tableinsertsort(table2*tab)void tableinsertsort(table2*tab)int i,p,q;int i,p,q;tab-r0.link=1;tab-r1.link=0;/*tab-r0.link=1;tab-r1.link=0;/*第第1 1个元素为有序静态表个元素为有序静态表*/for

30、(i=2;ilength;i+)/*for(i=2;ilength;i+)/*依次插入从第依次插入从第2 2个开始的所有元素个开始的所有元素*/q=0;p=tab-r0.link;/*p q=0;p=tab-r0.link;/*p指向表中第指向表中第1 1个元素，个元素，q q指向指向p p的前驱元素位置的前驱元素位置*/while(p!=0&tab-ri.key=tab-rp.key)/*while(p!=0&tab-ri.key=tab-rp.key)/*找插入位置找插入位置*/q=p;p=tab-rp.link;/*q=p;p=tab-rp.link;/*继续查找继续查找*/tab-ri

31、.link=p;tab-rq.link=i;/*tab-ri.link=p;tab-rq.link=i;/*将第将第i i个元素插入个元素插入q q和和p p所指向的元素之间所指向的元素之间*/算法算法10.3 10.3 表插入排序算法表插入排序算法 第19页/共50页10.2.4 Shell插入排序插入排序 Shell Shell插入排序：对有插入排序：对有n n个记录进行排序，首先取个记录进行排序，首先取1 1个整数个整数dndlength/2;d=tab-length/2;while(d=1)while(d=1)for(i=d+1;ilength;i+)for(i=d+1;ilength

32、;i+)/*/*从第从第d+1d+1个元素开始个元素开始,将所有元素有序插入相应分组中将所有元素有序插入相应分组中*/tab-r0.key=tab-ri.key;/*tab-r0.key=tab-ri.key;/*保存第保存第i i个元素个元素*/j=i-d;/*j=i-d;/*向前找插入位置向前找插入位置*/while(tab-r0.keyrj.key&j0)/*while(tab-r0.keyrj.key&j0)/*找插入位置并后移找插入位置并后移*/tab-rj+d.key=tab-rj.key;tab-rj+d.key=tab-rj.key;/*/*后移后移*/j=j-d;j=j-d;

33、/*/*继续向前查找继续向前查找*/tab-rj+d.key=tab-r0.key;/*tab-rj+d.key=tab-r0.key;/*插入第插入第i i个元素的副本个元素的副本*/d=d/2;d=d/2;算法算法10.4 Shell10.4 Shell插入排序算法插入排序算法 第21页/共50页10.3 选择排序选择排序 选择排序的基本思想是：每次从待排序的文件中选选择排序的基本思想是：每次从待排序的文件中选择出排序码最小的记录，将该记录放于已排序文件的最择出排序码最小的记录，将该记录放于已排序文件的最后一个位置，直到已排序文件记录个数等于初始待排序后一个位置，直到已排序文件记录个数等于

34、初始待排序文件的记录个数为止。文件的记录个数为止。10.3.1直接选择排序 苜先从所有苜先从所有n n个待排序记录中选择排序码最小的记个待排序记录中选择排序码最小的记录，将该记录与第录，将该记录与第1 1个记录交换，再从剩下的个记录交换，再从剩下的n-ln-l个记录个记录中选出排序码最小的记录和第中选出排序码最小的记录和第2 2个记录交换。重复这样个记录交换。重复这样的操作直到剩下的操作直到剩下2 2个记录时，再从中选出排序码最小的个记录时，再从中选出排序码最小的记录和第记录和第n-1n-1个记录交换。剩下的那个记录交换。剩下的那1 1个记录肯定是排序个记录肯定是排序码最大的记录，这样排序即告

35、完成。码最大的记录，这样排序即告完成。第22页/共50页void simpleselectsort(table*tab)void simpleselectsort(table*tab)int i,j,k;int i,j,k;for(i=1;ilength-1;i+)for(i=1;ilength-1;i+)k=i;/*k=i;/*记下当前最小元素的位置记下当前最小元素的位置*/for(j=i+1;jlength;j+)/*for(j=i+1;jlength;j+)/*向右查找更小的元素向右查找更小的元素*/if(tab-rj.keyrk.key)k=j;/*if(tab-rj.keyrk.ke

36、y)k=j;/*修改当前最小元素的位置修改当前最小元素的位置*/if(k!=i)if(k!=i)/*/*如如果果第第i i次次选选到到的的最最小小元元素素位位置置k k不不等等于于i i，则则将将第第k k、i i个个元元素素交交换换*/tab-r0.key=tab-rk.key;/*tab-r0.key=tab-rk.key;/*以第以第0 0个元素作为中间单元进行交换个元素作为中间单元进行交换*/tab-rk.key=tab-ri.key;tab-rk.key=tab-ri.key;tab-ri.key=tab-r0.key;tab-ri.key=tab-r0.key;算法算法10.5 1

37、0.5 直接选择排序算法直接选择排序算法 第23页/共50页直接选择排序算法执行过程如图直接选择排序算法执行过程如图10.610.6所示所示 （见书本）（见书本）10.3.2 10.3.2 树型选择排序树型选择排序 （略）（略）第24页/共50页10.3.3 堆排序堆排序 为了既要保存中间比较结果，减少后面的比较次为了既要保存中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间，使排序算法具有数，又不占用大量的附加存储空间，使排序算法具有较好的性能，较好的性能，WilliomsWillioms和和FloydFloyd在在19641964年提出的称为堆年提出的称为堆排序的算法实现了这一想

38、法。排序的算法实现了这一想法。堆是一个序列堆是一个序列kk1 1,k,k2 2,k,kn n，它满足下面的条件：，它满足下面的条件：k ki ikk2i2i并且并且k ki ikk2i+12i+1，当，当i=1,2,i=1,2,n/2n/2 采用顺序方式存储这个序列，就可以将这个序列采用顺序方式存储这个序列，就可以将这个序列的每一个元素的每一个元素k ki i看成是一颗有看成是一颗有n n个结点的完全二叉树的个结点的完全二叉树的第第i i个结点，其中个结点，其中k k1 1是该二叉树的根结点。是该二叉树的根结点。第25页/共50页 把堆对应的一维数组把堆对应的一维数组(即该序列的顺序存储结构即

39、该序列的顺序存储结构)看看作一棵完全二叉树的顺序存储，那么堆的特征可解释为，作一棵完全二叉树的顺序存储，那么堆的特征可解释为，完全二叉树中任一分支结点的值都小于或等于它的左、完全二叉树中任一分支结点的值都小于或等于它的左、右儿子结点的值。堆的元素序列中的第一个元素右儿子结点的值。堆的元素序列中的第一个元素k k1 1，即对应的完全二叉树根结点的值是所有元素中值最小的。即对应的完全二叉树根结点的值是所有元素中值最小的。堆排序方法就是利用这一点来选择最小元素。堆排序方法就是利用这一点来选择最小元素。一个序列和相一个序列和相应的完全二叉应的完全二叉树树 ：这个序列不是一个这个序列不是一个堆。堆排序的

40、关键堆。堆排序的关键问题是如何将待排问题是如何将待排序记录的排序码建序记录的排序码建成一个堆。成一个堆。第26页/共50页从图可以看到，在从图可以看到，在n=9n=9个个元素组成的序列和它相对元素组成的序列和它相对应的完全二叉树中，序号应的完全二叉树中，序号为为9 9，8 8，7 7，6 6，5 5的结点的结点没有儿子，以它们为根的没有儿子，以它们为根的子树显然满足堆的条件。子树显然满足堆的条件。因为在有因为在有n=9n=9个结点的完个结点的完全二叉树中，第全二叉树中，第4=n/24=n/2，3,2,13,2,1个结点都有儿子，一个结点都有儿子，一般情况下，以它们为根结般情况下，以它们为根结点

41、的子树不会满足堆的条点的子树不会满足堆的条件，所以，要使该序列变件，所以，要使该序列变换成一个堆，必须从这些换成一个堆，必须从这些结点处进行调整。结点处进行调整。调整是从序号为调整是从序号为1 1的的结点处开始直到结点处开始直到4(=n/2),4(=n/2),还是从序号为还是从序号为4 4的结点开的结点开始，然后对序号为始，然后对序号为3 3，2 2，1 1的结点依次进行呢？的结点依次进行呢？应该从第应该从第4 4个结点开个结点开始，依次使以第始，依次使以第4 4个结点个结点为根的子树变成堆，直到为根的子树变成堆，直到以第以第1 1个结点为根的整个个结点为根的整个完全二叉树具有堆的性质，完全二

42、叉树具有堆的性质，则建堆完成。则建堆完成。第27页/共50页建堆过程如下图所示建堆过程如下图所示 第28页/共50页/*/*筛选算法筛选算法 */void sift(table*tab,int k,int m)void sift(table*tab,int k,int m)int i,j,finished;int i,j,finished;i=k;j=2*i;tab-r0.key=tab-rk.key;finished=0;i=k;j=2*i;tab-r0.key=tab-rk.key;finished=0;while(j=m)&(!finished)while(j=m)&(!finished

43、)if(jrj+1.keyrj.key)j+;if(jrj+1.keyrj.key)j+;if(tab-r0.keyrj.key)finished=1;if(tab-r0.keyrj.key)finished=1;else tab-ri.key=tab-rj.key;i=j;j=2*j;else tab-ri.key=tab-rj.key;i=j;j=2*j;tab-ri.key=tab-r0.key;tab-ri.key=tab-r0.key;算法算法10.6 10.6 筛选算法筛选算法 第29页/共50页 通过筛选算法，可以将一个任意的排序码序列建通过筛选算法，可以将一个任意的排序码序列建

44、成一个堆，堆的第成一个堆，堆的第1 1个元素，即完全二叉树的根结点的个元素，即完全二叉树的根结点的值就是排序码中最小的。将选出的最小排序码从堆中删值就是排序码中最小的。将选出的最小排序码从堆中删除，对剩余的部分重新建堆，可以继续选出其中的最小除，对剩余的部分重新建堆，可以继续选出其中的最小者，直到剩余者，直到剩余1 1个元素排序即告结束。个元素排序即告结束。第30页/共50页/*/*堆排序算法堆排序算法 */void heapsort(table*tab)void heapsort(table*tab)int i;int i;for(i=tab-length/2;i=1;i-)sift(tab

45、,i,tab-length);/*for(i=tab-length/2;i=1;i-)sift(tab,i,tab-length);/*对所有元素建堆对所有元素建堆*/for(i=tab-length;i=2;i-)/*i for(i=tab-length;i=2;i-)/*i表示当前堆的大小，即等待排序的元素的个数表示当前堆的大小，即等待排序的元素的个数*/tab-r0.key=tab-ri.key;tab-r0.key=tab-ri.key;tab-ri.key=tab-r1.key;tab-ri.key=tab-r1.key;tab-r1.key=tab-r0.key;tab-r1.ke

46、y=tab-r0.key;/*/*上述上述3 3条语句为将堆中最小元素和最后一个元素交换条语句为将堆中最小元素和最后一个元素交换*/sift(tab,1,i-1);sift(tab,1,i-1);算法算法10.7 10.7 堆排序算法堆排序算法 第31页/共50页10.4交换排序交换排序 交换排序的基本思路：交换排序的基本思路：对待排序记录两两进行排序码比较，若不满足排对待排序记录两两进行排序码比较，若不满足排序顺序则交换这对记录，直到任何两个记录的排序码序顺序则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。都满足排序要求为止。10.4.1 冒泡排序 第32页/共50页 冒泡排序冒

47、泡排序 第第1 1趟，对所有记录从左到右每相邻两个记录的排趟，对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排序序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样一趟做完，将排序码最大者要求，则进行交换，这样一趟做完，将排序码最大者放在最后一个位置；放在最后一个位置；第第2 2趟对剩下的趟对剩下的n-ln-l个待排序记录重复上述过程，又个待排序记录重复上述过程，又将一个排序码放于最终位置，反复进行将一个排序码放于最终位置，反复进行n-ln-l次，可将次，可将n-ln-l个排序码对应的记录放至最终位置，剩下的即为排序个排序码对应的记录放至最终位置

48、，剩下的即为排序码最小的记录，它在第码最小的记录，它在第1 1的位置处。的位置处。如果在某一趟中，没有发生交换，则说明此时所如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。有记录已经按排序要求排列完毕，排序结束。第33页/共50页void bubblesort(table*tab)void bubblesort(table*tab)int i,j,done;i=1;done=1;int i,j,done;i=1;done=1;while(ilength&done)while(ilength&done)/*/*最多进行最多进行tab-lengthtab-leng

49、th次冒泡，如没有发生交换则结束次冒泡，如没有发生交换则结束*/done=0;done=0;for(j=1;jlength-i;j+)for(j=1;jlength-i;j+)if(tab-rj+1.keyrj.key)if(tab-rj+1.keyrj.key)tab-r0.key=tab-rj.key;tab-r0.key=tab-rj.key;tab-rj.key=tab-rj+1.key;tab-rj.key=tab-rj+1.key;tab-rj+1.key=tab-r0.key;done=1;tab-rj+1.key=tab-r0.key;done=1;i+;i+;/*/*算法算法

50、10.8 10.8 冒泡排序算法冒泡排序算法*/第34页/共50页 待排序的待排序的9 9个记录的排序码序列为个记录的排序码序列为312312，126126，272272，226226，8 8，165165，123123，1212，2828，使用冒泡排序算法进，使用冒泡排序算法进行的排序过程如下图所示：行的排序过程如下图所示：第35页/共50页10.4.2 快速排序快速排序 快速排序算法的基本思路是：快速排序算法的基本思路是：从从n n个待排序的记录中任取一个记录个待排序的记录中任取一个记录(不妨取第不妨取第1 1个个记录记录)，设法将该记录放置于排序后它最终应该放的位，设法将该记录放置于排序