数据结构李云清杨庆红揭安全学习教案.pptx

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

1、数据结构数据结构(sh j ji u)李云清李云清 杨庆红杨庆红 揭安全揭安全第一页，共50页。第10章 内排序(pi x)排序是数据处理过程排序是数据处理过程(guchng)(guchng)中经常使用的一种重中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的要的运算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及算各种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。法的稳定性等进行了讨论。10.1 排序排序(pi x)的基本概念的基本概念 假设一个文件是由假设一个文件是由n n个记录个记录R R1 1，R R2

2、 2，R Rn n组成，所组成，所谓排序就是以记录中某个谓排序就是以记录中某个(或几个或几个)字段值不减字段值不减(或不增或不增)的的次序将这次序将这n n个记录重新排列，称该字段为排序码。能唯一标个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。排序码不一定要是关键码。第1页/共50页第二页，共50页。按排序过程中使用到的存储介质来分，可以按排序过程中使用到的存储介质来分，可以(ky)(ky)将排序将排序分成两大类分成两大类:内排序和外排序。内排序和外排序。内排序是指在排序

3、过程中所有数据内排序是指在排序过程中所有数据(shj)(shj)均放在内存中均放在内存中处理，不需要使用外存的排序方法。而对于数据处理，不需要使用外存的排序方法。而对于数据(shj)(shj)量很量很大的文件，在内存不足的情况下，则还需要使用外存，这种大的文件，在内存不足的情况下，则还需要使用外存，这种排序方法称为外排序。排序方法称为外排序。排序码相同排序码相同(xin tn)(xin tn)的记录，若经过排序后，这些的记录，若经过排序后，这些记录仍保持原来的相对次序不变，称这个排序算法是稳定的。记录仍保持原来的相对次序不变，称这个排序算法是稳定的。否则，称为不稳定的排序算法。否则，称为不稳定

4、的排序算法。第2页/共50页第三页，共50页。评价评价(pngji)(pngji)排序算法优劣的标准排序算法优劣的标准 ：首先考虑算法执行所需的时间，这主要是用执行过程中的首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动比较次数和移动(ydng)(ydng)次数来度量；次数来度量；其次考虑算法执行所需要的附加空间。其次考虑算法执行所需要的附加空间。当然，保证算法的正确性是不言而喻的，可读性等也是要当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。考虑的因素。第3页/共50页第四页，共50页。排序排序(pi x)(pi x)算法如未作特别的说明，使用的有关定义算法如未

5、作特别的说明，使用的有关定义如下如下 ：/*/*常见排序算法常见排序算法(sun f)(sun f)的头文件，文件名的头文件，文件名table.h*/table.h*/#define MAXSIZE 100 /*#define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/*/typedef int keytype;/*typedef int keytype;/*定义排序码类型为整数类型定义排序码类型为整数类型*/*/typedef struct typedef struct keytype key;keytype key;/*/*此处还可以定义记录中除排序码外的

6、其它域此处还可以定义记录中除排序码外的其它域*/*/recordtype;/*recordtype;/*记录类型的定义记录类型的定义*/*/typedef struct typedef struct recordtype rMAXSIZE+1;recordtype rMAXSIZE+1;int length;/*int length;/*待排序文件中记录的个数待排序文件中记录的个数*/*/table;/*table;/*待排序文件类型待排序文件类型*/*/为了方便为了方便(fngbin)，r0一般不用于存放排序码，在一一般不用于存放排序码，在一些排序算法中它可以用来作为些排序算法中它可以用来作

7、为中间单元存放临时数据。中间单元存放临时数据。length域是待排序的记录个数，域是待排序的记录个数，它必须不大于它必须不大于MAXSIZE，这样，这样，第第1length个记录的排序码分个记录的排序码分别存于别存于r1.keyrlength.key中中 第4页/共50页第五页，共50页。10.2 插入排序 插入排序的基本插入排序的基本(jbn)(jbn)方法是方法是:将待排序文件中的记录将待排序文件中的记录(jl)(jl)，逐个地按其排序码值的大小逐个地按其排序码值的大小插入到目前已经排好序的若干个记录插入到目前已经排好序的若干个记录(jl)(jl)组成的文件中的适当组成的文件中的适当位置，

8、并保持新文件有序。位置，并保持新文件有序。10.2.1 10.2.1 直接直接直接直接(zhji)(zhji)插入排序插入排序插入排序插入排序 直接插入排序算法的思路是直接插入排序算法的思路是:初始可认为文件中的第初始可认为文件中的第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与已经与已经排好序的排

9、序码从右向左依次比较，找到排好序的排序码从右向左依次比较，找到R Ri i应插入的位应插入的位置，将该位置以后直到置，将该位置以后直到R Ri-1i-1各记录顺序后移，空出该位置各记录顺序后移，空出该位置让让R Ri i插入。插入。第5页/共50页第六页，共50页。一组记录的排序一组记录的排序(pi x)(pi x)码分别为码分别为:312312，126126，272272，226226，2828，165165，123 123 初初始始时时将将第第1 1个个排排序序码码作作为为已已经经排排好好序序的的，把把排排好好序序的的数数据据记记录录放放入入中中括括号号 中中，表表示示有有序序的的文文件件

10、(wnjin)(wnjin)，剩剩下的在中括号外，如下所示：下的在中括号外，如下所示：312312，126126，272272，226226，2828，165165，123 123 设设前前3 3个个记记录录的的排排序序码码已已重重新新排排列列有有序序，构构成成一一个个含含有有(hn yu)3(hn yu)3个记录的有序文件个记录的有序文件:126126，272272，312312，226226，2828，165165，123 123 现在要将第现在要将第4 4个排序码个排序码226226插入插入 ！第6页/共50页第七页，共50页。126126，272272，312312，226226，28

11、28，165165，123123现在现在(xinzi)(xinzi)要将第要将第4 4个排序码个排序码226226插入插入 ！将待插入的排序将待插入的排序(pi x)(pi x)码码226226和已经有序的最后一个和已经有序的最后一个排序排序(pi x)(pi x)码码312312比较，因为待插入的排序比较，因为待插入的排序(pi x)(pi x)码码226226小于小于312312，所以，所以226226肯定要置于肯定要置于312312的前面，至于是否就是的前面，至于是否就是置于置于312312的前一个位置，此时还不能确定，需要继续向左的前一个位置，此时还不能确定，需要继续向左比较；比较；将

12、所有大于待插入排序将所有大于待插入排序(pi x)(pi x)码码226226的那两个的那两个排序排序(pi x)(pi x)码码312312和和272272依次后移一个位置，在空出依次后移一个位置，在空出的位置插入待排序的位置插入待排序(pi x)(pi x)的排序的排序(pi x)(pi x)码码226226，得，得一含有一含有4 4个记录的有序文件：个记录的有序文件：126126，226226，272272，312312，2828，165165，123 123 第7页/共50页第八页，共50页。需要注意的是，当待插入排序需要注意的是，当待插入排序(pi x)(pi x)码小于所有已排序码

13、小于所有已排序(pi x)(pi x)的排序的排序(pi x)(pi x)码时，如在插入第码时，如在插入第5 5个值个值2828时：时：126126，226226，272272，312312，2828，165165，123123算法设计的时候如处理？算法设计的时候如处理？方法之一：设置方法之一：设置(shzh)“(shzh)“哨兵哨兵”第8页/共50页第九页，共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+)/*依次插入

14、从第依次插入从第2 2个开始个开始(kish)(kish)的所有元素的所有元素*/*/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;/*继续向前（左）查找继续向前（左）查找*/*/t

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

16、6126，272272，226226，2828，165165，123123初始初始 （）（）312 312，126126，272272，226226，2828，165165，123123i=2i=2：（126126）126 126，312312，272272，226226，2828，165165，123123i=3i=3：（272272）126 126，272272，312312，226226，2828，165165，123123i=4i=4：（226226）126 126，226226，272272，312312，2828，165165，123123i=5i=5：（2828）28 28，12

17、6126，226226，272272，312312，165165，123123i=6i=6：（165165）28 28，126126，165165，226226，272272，312312，123123i=7i=7：（123123）28 28，123123，126126，165165，226226，272272，312312图图10.2 10.2 直接插入排序算法直接插入排序算法(sun f)(sun f)执行过程示意图执行过程示意图 第10页/共50页第十一页，共50页。直接插入排序算法执行时间直接插入排序算法执行时间(shjin)(shjin)的分析：的分析：最好最好(zu ho)(zu

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

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

20、*(n-1)(1+2+n)*(n-1)，移动次数为，移动次数为(1+2+2+2+n+2)*(n-1)(1+2+2+2+n+2)*(n-1)。假设待排序文件中的记录。假设待排序文件中的记录以各种以各种(zhn)(zhn)排列出现的概率相同，因为当插入排列出现的概率相同，因为当插入第第i i个排序码时，该算法内循环个排序码时，该算法内循环whilewhile平均约要执行平均约要执行i/2i/2次条件判断，循环体要执行（次条件判断，循环体要执行（i-li-l）/2/2次，外循环共执次，外循环共执行行n-1n-1次，所以平均比较次数约为次，所以平均比较次数约为(2+3+n)/2*(n-1)(2+3+n

21、)/2*(n-1)，平均移动次数为，平均移动次数为(n-1)*(2+1+3+1+n+1)/2(n-1)*(2+1+3+1+n+1)/2，也即，也即直接插入排序算法的时间复杂度为直接插入排序算法的时间复杂度为O(n2)O(n2)。第12页/共50页第十三页，共50页。10.2.2 10.2.2 二分法插入排序二分法插入排序 二分法插入排序的思想：二分法插入排序的思想：根据插入排序的基本思想，在找第根据插入排序的基本思想，在找第i i个记录的插入位个记录的插入位置时，前置时，前i-li-l个记录已排序，将第个记录已排序，将第i i个记录的排序码个记录的排序码keyikeyi和和已排序的前已排序的前

22、i-1i-1个的中间位置记录的排序码进行比较个的中间位置记录的排序码进行比较(bjio)(bjio)，如果，如果keyikeyi小于中间位置记录排序码，则可以小于中间位置记录排序码，则可以在前半部继续使用二分法查找，否则在后半部继续使用在前半部继续使用二分法查找，否则在后半部继续使用二分法查找，直到查找范围为空，即可确定二分法查找，直到查找范围为空，即可确定keyikeyi的插入的插入位置。位置。第13页/共50页第十四页，共50页。void binarysort(table*tab)void binarysort(table*tab)int i,j,left,right,mid;int i,

23、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;/*保存保存(bocn)(bocn)待插入的元素待插入的元素*/*/left=1;right=i-1;/*left=1;right=i-1;/*设置查找范围的左、右位置值设置查找范围的左、右位置值*/*/while(left=right)/*while(leftri.keyrmid.key)right=mid-1;if

24、(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=tab-r0.key;/*tab-rleft.key=tab-r0.key;/*插入第插入第i i个元素的副本个元素的副本*/*/*/*算法算法10.2 10.2 二

25、分法插入排序算法二分法插入排序算法*/*/第14页/共50页第十五页，共50页。设待排序的设待排序的7 7记录的排序码为记录的排序码为312312，126126，272272，226226，2828，165165，123123，在前，在前6 6个记录已经排序的情况下，使用二个记录已经排序的情况下，使用二分法插入排序算法分法插入排序算法(sun f)(sun f)插入第插入第7 7个记录的排序码个记录的排序码123123的的执行过程示意如图执行过程示意如图10.310.3所示（见书本）。所示（见书本）。二分法插入排序算法二分法插入排序算法(sun f)(sun f)，在查找第，在查找第i i个记

26、录的插入个记录的插入位置时，每执行一次位置时，每执行一次whilewhile循环体，查找范围缩小一半，和直循环体，查找范围缩小一半，和直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。总体上讲，当最少比较次数。总体上讲，当n n较大时，二分法插入排序的比较大时，二分法插入排序的比较次数远少于直接插入排序的平均比较次数，但二者所要进较次数远少于直接插入排序的平均比较次数，但二者所要进行的移动次数相等，故二分法插入排序的时间复

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

28、设一个所谓的指针域linklink，它的类型为整型，它的类型为整型，表插入排序的思路：在插入第表插入排序的思路：在插入第i i个记录个记录RiRi时，时，R1R1，R2R2，Ri-1Ri-1已经通过各自的指针域已经通过各自的指针域linklink按排序码不减的次序连接成一按排序码不减的次序连接成一个（静态链）表，将记录个（静态链）表，将记录RiRi的排序码的排序码keyikeyi与表中已经排好序的与表中已经排好序的排序码从表头向右、或称向后依次排序码从表头向右、或称向后依次(yc)(yc)比较，找到比较，找到RiRi应插入应插入的位置，将其插入在表中，使表中各记录的排序码仍然有序。的位置，将其

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

30、type key;keytype key;int link;int link;/*/*此处还可以定义记录中除排序码外的其它域此处还可以定义记录中除排序码外的其它域*/*/recordtype;/*recordtype;/*记录类型记录类型(lixng)(lixng)的定义的定义*/*/typedef structtypedef struct recordtype rMAXSIZE+1;recordtype rMAXSIZE+1;int length;/*int length;/*待排序文件中记录的个数待排序文件中记录的个数*/*/table2;/*table2;/*待排序文件类型待排序文件类型

31、(lixng)*/(lixng)*/第17页/共50页第十八页，共50页。表插入排序算法的示意表插入排序算法的示意(shy)(shy)如图如图10.410.4所示（见书本）所示（见书本）对于将一个值为对于将一个值为x x的记录，插入到一个已排序的记录，插入到一个已排序(pi(pi x)x)（不减）的单链表（不减）的单链表headhead中，使新的单链表的结点中，使新的单链表的结点值以不减序排列，读者容易给出解决此问题的算法。值以不减序排列，读者容易给出解决此问题的算法。表插入排序表插入排序(pi x)(pi x)算法：初始时，算法：初始时，r0.Linkr0.Link用于存放表中用于存放表中第

32、第1 1个记录的下标，个记录的下标，r0.Link r0.Link的值为的值为1 1，排序，排序(pi x)(pi x)结束时，结束时，r0.Linkr0.Link中存放的是所有排序中存放的是所有排序(pi x)(pi x)码中值最小的对应记录的码中值最小的对应记录的下标，其它的排序下标，其它的排序(pi x)(pi x)码通过各自的指针域码通过各自的指针域linklink按不减的次按不减的次序连接成一个（静态链）表，最大的排序序连接成一个（静态链）表，最大的排序(pi x)(pi x)码对应的码对应的linklink为为0 0。第18页/共50页第十九页，共50页。void tableins

33、ertsort(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(i=2;ilength;i+)/*for(i=2;ilength;i+)/*依次插入从第依次插入从第2 2个开始的所有元素个开始的所有元素*/*/q=0;p=tab-r0.link;q=0;p=tab-r0.link;/*p/*p指指向向表表中中第第1 1个个元元素素，q q

34、指指向向p p的的前前驱驱(qinq)(qinq)元元素位置素位置*/*/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.link=p;tab-rq.link=i;tab-ri.link=p;tab-rq.link=i;/*/*将将第第i i个个元元素素插插入入q q和和p p所所指指向向的的元元素素之之间间*/*/算法算法10.3 10.3 表插入排序算法表

35、插入排序算法 第19页/共50页第二十页，共50页。10.2.4 Shell10.2.4 Shell插入排序插入排序 Shell Shell插入排序：对有插入排序：对有n n个记录个记录(jl)(jl)进行排序，首先取进行排序，首先取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;i+)/*从第从第d+1d+1个元素开始个元素开始,将所有元素有序插入相应分组中将所有元素有序插入相应分组中*/*/tab-r0.key=tab-ri.key;/*tab-

36、r0.key=tab-ri.key;/*保存第保存第i i个元素个元素*/*/j=i-d;/*j=i-d;/*向前找插入位置向前找插入位置(wi zhi)*/(wi zhi)*/while(tab-r0.keyrj.key&j0)/*while(tab-r0.keyrj.key&j0)/*找插入位置找插入位置(wi zhi)(wi zhi)并后移并后移*/*/tab-rj+d.key=tab-rj.key;/*tab-rj+d.key=tab-rj.key;/*后移后移*/j=j-d;/*/j=j-d;/*继续向前查找继续向前查找*/*/tab-rj+d.key=tab-r0.key;/*ta

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

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

39、记录，这样个记录肯定是排序码最大的记录，这样排序即告完成。排序即告完成。第22页/共50页第二十三页，共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.ke

40、yrk.key)k=j;/*if(tab-rj.keyrk.key)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个个元元素素作作为为(zuwi)(zuwi)中中间间单单元元进进行交换行交换*/*/tab-rk.key=tab-ri.key;tab-rk.key=tab-ri.key;tab-

41、ri.key=tab-r0.key;tab-ri.key=tab-r0.key;算法算法10.5 10.5 直接选择排序算法直接选择排序算法 第23页/共50页第二十四页，共50页。直接选择排序算法直接选择排序算法(sun f)(sun f)执行过程如图执行过程如图10.610.6所示所示 （见书本）（见书本）10.3.2 10.3.2 树型选择树型选择树型选择树型选择(xunz)(xunz)排序排序排序排序 （略）（略）（略）（略）第24页/共50页第二十五页，共50页。10.3.3 10.3.3 堆排序堆排序 为了为了(wi le)(wi le)既要保存中间比较结果，减少后面的比较既要保存

42、中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间，使排序算法具有较次数，又不占用大量的附加存储空间，使排序算法具有较好的性能，好的性能，WilliomsWillioms和和FloydFloyd在在19641964年提出的称为堆排序的年提出的称为堆排序的算法实现了这一想法。算法实现了这一想法。堆堆是是一一个个序序列列(xli)k1,k2,kn(xli)k1,k2,kn，它它满满足足下下面面的的条件：条件：kik2i kik2i并且并且kik2i+1kik2i+1，当，当i=1,2,i=1,2,n/2n/2 采用顺序方式存储这个序列采用顺序方式存储这个序列(xli)(xli)，就可以将

43、这个序列，就可以将这个序列(xli)(xli)的每一个元素的每一个元素ki ki看成是一颗有看成是一颗有n n个结点的完全二叉树的第个结点的完全二叉树的第i i个结点，其中个结点，其中k1k1是该二叉树的根结点。是该二叉树的根结点。第25页/共50页第二十六页，共50页。把堆对应的一维数组把堆对应的一维数组(即该序列的顺序存储结构即该序列的顺序存储结构)看作一看作一棵完全二叉树的顺序存储，那么堆的特征可解释为，完全二棵完全二叉树的顺序存储，那么堆的特征可解释为，完全二叉树中任一分支结点的值都小于或等于它的左、右儿子结点叉树中任一分支结点的值都小于或等于它的左、右儿子结点的值。堆的元素序列中的第

44、一个元素的值。堆的元素序列中的第一个元素k1k1，即对应的完全二，即对应的完全二叉树根结点的值是所有元素中值最小的。堆排序方法叉树根结点的值是所有元素中值最小的。堆排序方法(fngf)(fngf)就是利用这一点来选择最小元素。就是利用这一点来选择最小元素。一个序列一个序列(xli)(xli)和相应和相应的完全二叉树的完全二叉树 ：这个这个(zh ge)(zh ge)序列不序列不是一个堆。堆排序的是一个堆。堆排序的关键问题是如何将待关键问题是如何将待排序记录的排序码建排序记录的排序码建成一个堆。成一个堆。第26页/共50页第二十七页，共50页。从图可以看到，在从图可以看到，在n=9n=9个元素个

45、元素组成的序列和它相对应的完组成的序列和它相对应的完全二叉树中，序号为全二叉树中，序号为9 9，8 8，7 7，6 6，5 5的结点没有儿子，以的结点没有儿子，以它们为根的子树显然满足堆它们为根的子树显然满足堆的条件。因为在有的条件。因为在有n=9n=9个结点个结点的完全二叉树中，第的完全二叉树中，第4=n/24=n/2，3,2,13,2,1个结点都有儿子，一般个结点都有儿子，一般情况下，以它们为根结点的情况下，以它们为根结点的子树不会满足堆的条件，所子树不会满足堆的条件，所以，要使该序列变换以，要使该序列变换(binhun)(binhun)成一个堆，必须成一个堆，必须从这些结点处进行调整。从

46、这些结点处进行调整。调整是从序号为调整是从序号为1 1的结点的结点处开始直到处开始直到4(=n/2),4(=n/2),还是从序还是从序号为号为4 4的结点开始，然后对序的结点开始，然后对序号为号为3 3，2 2，1 1的结点依次进的结点依次进行呢？行呢？应该从第应该从第4 4个结点开始，个结点开始，依次使以第依次使以第4 4个结点为根的子个结点为根的子树变成堆，直到以第树变成堆，直到以第1 1个结点个结点为根的整个完全二叉树具有为根的整个完全二叉树具有(jyu)(jyu)堆的性质，则建堆完堆的性质，则建堆完成。成。第27页/共50页第二十八页，共50页。建堆过程建堆过程(guchng)(guc

47、hng)如下图所示如下图所示 第28页/共50页第二十九页，共50页。/*/*筛选筛选(shixun)(shixun)算法算法 */*/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)if(j

48、rj+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 筛选筛选(shixun)(shixun)算法算法 第29页/共50页第三十页，共50页。通过通过(tnggu)(tnggu)筛选算法

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

50、)int i;int i;for(i=tab-length/2;i=1;i-)sift(tab,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表示当前堆的大小，即等待表示当前堆的大小，即等待(dngdi)(dngdi)排序的元素的个数排序的元素的个数*/*/tab-r0.key=tab-ri.key;tab-r0.key=tab-ri.key;tab-ri.key