数据结构 第10章_内排序

1、交换排序交换排序冒泡排序冒泡排序p 快速排序快速排序p 直接选择排序直接选择排序p 堆排序堆排序第十章第十章 内排序内排序插入排序插入排序p 直接插入排序直接插入排序p 二分插入排序二分插入排序p 希尔排序希尔排序 选择排序选择排序 归并排序归并排序 基数排序基数排序 排序是数据处理过程中经常使用的一种重要的运排序是数据处理过程中经常使用的一种重要的运算，排序的方法有很多种，本章主要讨论内排序的各算，排序的方法有很多种，本章主要讨论内排序的各种算法，并对每个排序算法的时间和空间复杂性以及种算法，并对每个排序算法的时间和空间复杂性以及算法的稳定性等进行了讨论。算法的稳定性等进行了讨论。 10.1

2、 排序的基本概念排序的基本概念 假设一个文件是由假设一个文件是由n个记录个记录R1，R2，Rn组成，组成，所谓排序就是以记录中某个所谓排序就是以记录中某个(或几个或几个)字段值不减字段值不减(或或不增不增)的次序将这的次序将这n个记录重新排列，称该字段为排个记录重新排列，称该字段为排序码。能唯一标识一个记录的字段称为关键码，关序码。能唯一标识一个记录的字段称为关键码，关键码可以作为排序码，但排序码不一定要是关键码。键码可以作为排序码，但排序码不一定要是关键码。 按排序过程中使用到的存储介质来分，可以将排按排序过程中使用到的存储介质来分，可以将排序分成两大类序分成两大类:内排序和外排序内排序和外

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

4、 首先考虑算法执行所需的时间，这主要是用执行首先考虑算法执行所需的时间，这主要是用执行过程中的比较次数和移动次数来度量；过程中的比较次数和移动次数来度量； 其次考虑算法执行所需要的附加空间。其次考虑算法执行所需要的附加空间。 当然，保证算法的正确性是不言而喻的，可读性当然，保证算法的正确性是不言而喻的，可读性等也是要考虑的因素。等也是要考虑的因素。 /*/*常见排序算法的头文件，文件名常见排序算法的头文件，文件名table.h */*/#define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/ typedef int keytype;/*定义排序码类型为整数类

5、型定义排序码类型为整数类型*/ typedef struct keytype key; int other;/*此处还可以定义记录中除排序码外此处还可以定义记录中除排序码外的其他域的其他域*/ recordtype;/*记录类型的定义记录类型的定义*/ typedef struct recordtype rMAXSIZE+1; int length;/*待排序文件中记录的个数待排序文件中记录的个数*/ table;/*待排序文件类型待排序文件类型*/void init(table *L) /*顺序表初始化函数顺序表初始化函数*/ int i; srand(time(NULL); L-lengt

6、h=10;for (i=1;iri.key= rand(i)%100;void print(table L) /*顺序表输出函数顺序表输出函数*/ int i,k=0; for (i=1;ilength); for (i=1;ilength;i+) fscanf(fp,%d,&L-ri.key); else L-length=0;1050 30 20 90 10 70 80 40 60 100一个输入文件的例子一个输入文件的例子10.2 插入排序插入排序 插入排序的基本方法是插入排序的基本方法是: 将待排序文件中的记录，将待排序文件中的记录， 逐个地按其排序码值的逐个地按其排序码值的大

7、小插入到目前已经排好序的若干个记录组成的文件中大小插入到目前已经排好序的若干个记录组成的文件中的适当位置，并保持新文件有序。的适当位置，并保持新文件有序。10.2.1 直接插入排序直接插入排序 直接插入排序算法的思路是直接插入排序算法的思路是:初始可认为文件中的初始可认为文件中的第第1个记录己排好序，然后将第个记录己排好序，然后将第2个到第个到第n个记录依次个记录依次插入已排序的记录组成的文件中。在对第插入已排序的记录组成的文件中。在对第i个记录个记录Ri进进行插入时，行插入时，R1，R2，Ri-1已排序，将记录已排序，将记录Ri的排序的排序码码keyi与已经排好序的排序码从右向左依次比较，找

8、与已经排好序的排序码从右向左依次比较，找到到Ri应插入的位置，将该位置以后直到应插入的位置，将该位置以后直到Ri-1各记录顺序各记录顺序后移，空出该位置让后移，空出该位置让Ri插入。插入。 直接插入排序演示直接插入排序演示0 1 2 3 4 5 6 212525*1608i =321254925*16080 1 2 3 4 5 6初态初态490 1 2 3 4 5 62525*1608i = 249250 1 2 3 4 5 6i = 6i = 521250 1 2 3 4 5 6214925*16080 1 2 3 4 5 64925*21254925*16i = 425*160825214

9、925*1608完成25习题：给出初始数列习题：给出初始数列47，28，32，15，94，33，14，16在直接插入排序下的状态变化过程。在直接插入排序下的状态变化过程。472832 15 9433 1416初态：初态：i=2i=3i=4i=5i=6i=7284732 15 9433 1416283247 15 9433 1416152832 47 9433 1416152832 47 9433 1416152832 33 4794 1416141528 32 3347 9716141516 28 3233 4797i=8void insertsort(table *L) /*直接插入排序直接

10、插入排序*/int i,j; for (i=2;ilength;i+) j=i-1; L-r0=L-ri; /*放置哨兵放置哨兵*/ while ( L-rj.keyL-r0.key ) L-rj+1=L-rj; j-; L-rj+1=L-r0; 算法算法10.1 直接插入排序算法直接插入排序算法 直接插入排序算法执行时间的分析：直接插入排序算法执行时间的分析：最好的情况最好的情况 ： 即初始排序码开始就是有序的情况下，直接插入即初始排序码开始就是有序的情况下，直接插入排序算法的比较次数为排序算法的比较次数为(n-1)次，移动次数为次，移动次数为2*(n-1)次。次。 最坏情况最坏情况 ： 即

11、初始排序码开始是逆序的情况下，因为当插即初始排序码开始是逆序的情况下，因为当插入第入第i个排序码时，该算法内循环个排序码时，该算法内循环while要执行要执行i次条件次条件判断，循环体要执行判断，循环体要执行i-l次，每次要移动次，每次要移动1个记录，外个记录，外循环共执行循环共执行n-1次，其循环体内不含内循环每次循环次，其循环体内不含内循环每次循环要进行要进行2次移动操作，所以在最坏情况下，比较次数次移动操作，所以在最坏情况下，比较次数为为(1+2+n)。 直接插入排序算法的时间复杂度为直接插入排序算法的时间复杂度为O(n2)。 10.2.2 二分法插入排序二分法插入排序 二分法插入排序的

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

13、id binarysort(table *L) /*折半插入排序折半插入排序*/ int left,right,mid,i,j; for(i=2;ilength;i+) L-r0=L-ri; /*保存待插入的元素保存待插入的元素*/ left=1; right=i-1; /*设置查找范围的左、右设置查找范围的左、右位置值位置值*/ while (leftri.keyrmid.key) right=mid-1; else left=mid+1; /*插入位置为插入位置为left*/ for(j=i-1;j=left;j-) /*后移留空后移留空*/ L-rj+1=L-rj; L-r left =

14、L-r0; /*插入第插入第i个元素的副本个元素的副本*/ 算法算法10.2 二分法插入排序算法二分法插入排序算法 二分法插入排序算法，在查找第二分法插入排序算法，在查找第i个记录的插入个记录的插入位置时，每执行一次位置时，每执行一次while循环体，查找范围缩小一循环体，查找范围缩小一半，和直接插入排序的比较次数对比，二分法插入的半，和直接插入排序的比较次数对比，二分法插入的比较次数少于直接插入排序的最多比较次数，而一般比较次数少于直接插入排序的最多比较次数，而一般要多于直接插入排序的最少比较次数。总体上讲，当要多于直接插入排序的最少比较次数。总体上讲，当n较大时，二分法插入排序的比较次数远

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

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

17、各记录的排序码仍然有序。表中，使表中各记录的排序码仍然有序。 /* 表插入排序定义的头文件，文件名为：表插入排序定义的头文件，文件名为：table2.h */#define MAXSIZE 100 /*文件中记录个数的最大值文件中记录个数的最大值*/typedef int keytype; /*定义排序码类型为整数类型定义排序码类型为整数类型*/typedef struct keytype key; int link;recordtype; /*记录类型的定义记录类型的定义*/typedef struct recordtype rMAXSIZE+1; int length; /*待排序文件中记

18、录的个数待排序文件中记录的个数*/table2; /*待排序文件类型待排序文件类型*/ 表插入排序算法的示意如图表插入排序算法的示意如图10.4所示所示keylink 31212627222628165123 下标下标 0 1 2 3 4 5 6 7（a）初始存储状态）初始存储状态下标下标 0 1 2 3 4 5 6 7（b）由第）由第1个记录构成的有序表个记录构成的有序表下标下标 0 1 2 3 4 5 6 7（c）插入第）插入第2个记录构成的有序表个记录构成的有序表keylink 31212627222628165123 1 0 keylink 31212627222628165123 2

19、 0 1 表插入排序算法：初始时，表插入排序算法：初始时，r0.Link用于存放表用于存放表中第中第1个记录的下标，个记录的下标，r0.Link的值为的值为1，排序结束时，排序结束时，r0.Link中存放的是所有排序码中值最小的对应记录中存放的是所有排序码中值最小的对应记录的下标，其它的排序码通过各自的指针域的下标，其它的排序码通过各自的指针域link按不减的按不减的次序连接成一个（静态链）表，最大的排序码对应的次序连接成一个（静态链）表，最大的排序码对应的link为为0。keylink 31212627222628165123 5 0 6 1 3 7 4 2 下标下标 0 1 2 3 4 5

20、 6 7（d）所有记录都插入后的结束状态（下标为）所有记录都插入后的结束状态（下标为5的记录的的记录的key值最小）值最小）图图10.4 表插入排序算法示意图表插入排序算法示意图void tableinsertsort(table2 *tab) int i,p,q; tab-r0.link=1; tab-r1.link=0; /*第第1个元素为有序静态表个元素为有序静态表*/ for(i=2;ilength;i+) /*依次插入从第依次插入从第2个开始的所有个开始的所有元素元素*/ q=0;p=tab-r0.link; /*p指向表中第指向表中第1个元素，个元素，q指向指向p的前驱元素位置的前

21、驱元素位置*/ while(p!=0&tab-ri.key=tab-rp.key) /*找插入找插入位置位置*/ q=p; p=tab-rp.link; /*继续查找继续查找*/ tab-ri.link=p;tab-rq.link=i; 算法算法10.3 表插入排序算法表插入排序算法 基本思想：对待排记录序列先作基本思想：对待排记录序列先作“宏观宏观”调整，调整，再作再作“微观微观”调整，它是由调整，它是由D.L.shell在在1959年提出年提出来的。来的。 所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插的插入排序。即：将记录序列分成若干子序列，每个子入排序。即

22、：将记录序列分成若干子序列，每个子序列分别进行插入排序。关键是，这种子序列不是序列分别进行插入排序。关键是，这种子序列不是由相邻的记录构成的。假设将由相邻的记录构成的。假设将n个记录分成个记录分成d个子序个子序列，则这列，则这d个子序列分别为：个子序列分别为：10.2.4 Shell插入排序插入排序 R1，R1+d，R1+2d，R1+kd R2，R2+d，R2+2d，R2+kd Rd，R2d，R3d，Rkd，R(k+1)d 10.2.4 Shell插入排序插入排序 21254925*16080 1 2 3 4 5 6i = 1d = 32125*2516084949d = 208162125*

23、25组内排序得：组内排序得：组内排序得：组内排序得：210825164925*jj+d21254925*1608 1 2 3 4 5621254925*16080 1 2 3 4 5d= 1210825164925*开始时开始时d的值较大，子序列中的对象较少，排序速度的值较大，子序列中的对象较少，排序速度较快；随着排序进展，较快；随着排序进展，d 值逐渐变小值逐渐变小(一般可以按一般可以按d=d/2的规律变化的规律变化)，子序列中对象个数逐渐变多，由，子序列中对象个数逐渐变多，由于前面工作的基础，大多数对象已基本有序，所以排于前面工作的基础，大多数对象已基本有序，所以排序速度仍然很快。序速度仍

24、然很快。 设待排序的设待排序的7记录的排序码为记录的排序码为312，126，272，226，28，165，123，初始让，初始让d=7/2=3，以后每次让以后每次让d缩小一半，其排序过程如图所示。缩小一半，其排序过程如图所示。 31228123126165226272 0 1 2 3 4 5 6 7(c) 完成完成31212328165226126272 0 1 2 3 4 5 6 7(b) d=112331212627222628165 0 1 2 3 4 5 6 7(a) 初始状态初始状态d=3习题：给出初始数列习题：给出初始数列47，28，32，15，94，33，14，16在在shell

25、排序下的状态变化过程。排序下的状态变化过程。d=44728321594331416472814159433321614153216472894331415162832334794d=2d=1结果结果void shellsort(table *L) /*希尔排序希尔排序*/ int i,j,d; d=L-length/2; while ( d=1 ) for (i=d+1; ilength; i+) /*从第从第d+1个元素开始个元素开始,将所有元素依次有序插入到相应的分组中将所有元素依次有序插入到相应的分组中*/ L-r0=L-ri; /*保存第保存第i个元素个元素*/ j=i-d; /*向前

26、找插入位置向前找插入位置*/ while(j0 & L-r0.keyrj.key) /*找插入位找插入位置并后移置并后移*/ L-rj+d=L-rj; /*后移后移*/ j=j-d; /*继续向前查找继续向前查找*/ L-rj+d=L-r0; /*插入第插入第i个元素的副本个元素的副本*/ d=d/2; 算法算法10.4 Shell插入排序算法插入排序算法10.3 选择排序选择排序 选择排序的基本思想是：每次从待排序的文件中选择排序的基本思想是：每次从待排序的文件中选择出排序码最小的记录，将该记录放于已排序文件的选择出排序码最小的记录，将该记录放于已排序文件的最后一个位置，直到已排序文

27、件记录个数等于初始待排最后一个位置，直到已排序文件记录个数等于初始待排序文件的记录个数为止。序文件的记录个数为止。 10.3.1直接选择排序直接选择排序 首先从所有首先从所有n个待排序记录中选择排序码最小的记个待排序记录中选择排序码最小的记录，将该记录与第录，将该记录与第1个记录交换，再从剩下的个记录交换，再从剩下的n-l个记个记录中选出排序码最小的记录和第录中选出排序码最小的记录和第2个记录交换。重复这个记录交换。重复这样的操作直到剩下样的操作直到剩下2个记录时，再从中选出排序码最小个记录时，再从中选出排序码最小的记录和第的记录和第n-1个记录交换。剩下的那个记录交换。剩下的那1个记录肯定是

28、个记录肯定是排序码最大的记录，这样排序即告完成。排序码最大的记录，这样排序即告完成。 直接选择排序演示直接选择排序演示2125*i = 12516490825160825*4921i = 221254925*1608 1 2 3 4 5 6初始初始最小者最小者 08交换交换21,08最小者最小者 16交换交换25,1625160825*4921结果结果4925*i = 408162521最小者最小者 25*无交换无交换最小者最小者 25无交换无交换25*i = 54925211608 1 2 3 4 5 649i = 3081625*2521最小者最小者 21交换交换49,21void sel

29、ectsort(table *L) /*简单选择排序算法简单选择排序算法*/ int i,j,k; for (i=1;ilength;i+) k=i; for (j=i+1;jlength; j+) /*找最小元素所在找最小元素所在位置位置*/ if (L-rj.keyrk.key) k=j; if (k!=i) L-r0=L-ri; /*将第将第i次找到的最小元素放次找到的最小元素放到第到第i个位置个位置*/ L-ri=L-rk; L-rk=L-r0; 直接选择排序算法执行过程如图直接选择排序算法执行过程如图10.6所示所示 （见书本）（见书本）10.3.3 堆排序堆排序 为了既要保存中间比

30、较结果，减少后面的比较次为了既要保存中间比较结果，减少后面的比较次数，又不占用大量的附加存储空间，使排序算法具有数，又不占用大量的附加存储空间，使排序算法具有较好的性能，较好的性能，Willioms和和Floyd在在1964年提出的称为年提出的称为堆排序的算法实现了这一想法。堆排序的算法实现了这一想法。 堆是一个序列堆是一个序列k1,k2,kn，它满足下面的条件：，它满足下面的条件： kik2i并且并且kik2i+1，当，当i=1,2, n/2 采用顺序方式存储这个序列，就可以将这个序列采用顺序方式存储这个序列，就可以将这个序列的每一个元素的每一个元素ki看成是一颗有看成是一颗有n个结点的完全

31、二叉树的个结点的完全二叉树的第第i个结点，其中个结点，其中k1是该二叉树的根结点。是该二叉树的根结点。 堆形：元素序列堆形：元素序列a1,a2,an的如下层次关系：的如下层次关系：a1a2a4a3a5a6123456堆关系堆关系：若：若j=2i或或j=2i+1则则称称有堆关系，这时称有堆关系，这时称ai为此堆关系的顶，为此堆关系的顶，aj为此堆为此堆关系的基。关系的基。堆堆：满足以下条件的堆形：满足以下条件的堆形：对堆形中的所有堆关系：对堆形中的所有堆关系均有均有ai=aj 。 把堆对应的一维数组把堆对应的一维数组(即该序列的顺序存储结构即该序列的顺序存储结构)看作一棵完全二叉树的顺序存储，那

32、么堆的特征可看作一棵完全二叉树的顺序存储，那么堆的特征可解释为，完全二叉树中任一分支结点的值都小于或解释为，完全二叉树中任一分支结点的值都小于或等于它的左、右儿子结点的值。堆的元素序列中的等于它的左、右儿子结点的值。堆的元素序列中的第一个元素第一个元素k1，即对应的完全二叉树根结点的值，即对应的完全二叉树根结点的值是所有元素中值最小的。堆排序方法就是利用这一是所有元素中值最小的。堆排序方法就是利用这一点来选择最小元素。点来选择最小元素。 在堆中结点序号在堆中结点序号n/2的结点没有基，实际上的结点没有基，实际上堆关系满足完全二叉树的结构特征。堆关系满足完全二叉树的结构特征。3475201212

33、3456152778（a）一个最小堆的例子）一个最小堆的例子91882342241612345651378（b）一个最大堆的例子）一个最大堆的例子一个序列和相应的完全二叉树一个序列和相应的完全二叉树 ：312272272 165 123 126 28 226226 8 12 12812316528226272126312下标下标 0 1 2 3 4 5 6 7 8 9123456789以下我们讨论最大堆：以下我们讨论最大堆：最大堆的重要性质：最大堆的重要性质：1）堆顶元为堆中最大元）堆顶元为堆中最大元2）堆具有部分有序性。即具有存储比较结果的）堆具有部分有序性。即具有存储比较结果的功能，遭受破

34、坏时易于调整成新的堆。功能，遭受破坏时易于调整成新的堆。堆的存储实现堆的存储实现 一维数组。一维数组。 91 88 42 23 24 16 5 13 1 2 3 4 5 6 7 8a0层1层2层3层堆排序的堆排序的基本思想基本思想：基本操作基本操作1）建堆（将待排序部分调整成堆）建堆（将待排序部分调整成堆）2）取最大元（堆顶元）取最大元（堆顶元）3）并入（将最大元并入已排序部分）并入（将最大元并入已排序部分）建堆算法（建堆算法（R.W.Floyd）1964年提出年提出-筛选法筛选法1）将待排序的数组随意地组成一个堆形）将待排序的数组随意地组成一个堆形2）沿堆形自下向上，自右向左依次进行筛选。设

35、）沿堆形自下向上，自右向左依次进行筛选。设当前要筛选当前要筛选ai，这时：，这时：若若ai=max(a2i,a2i+1)，即满足堆条件，则对，即满足堆条件，则对ai的筛选结束；的筛选结束；若若ai16不调整不调整42138891241612345652378(c) i=2, 13 下沉两级下沉两级42882391241612345651378(d) i=1, 42筛下一层筛下一层91882342241612345651378 91 88 42 23 24 16 5 13 1 2 3 4 5 6 7 8a（e）建成的堆）建成的堆最大元在堆顶最大元在堆顶建堆的关键一步：筛选建堆的关键一步：筛选Lk

36、若若rlow的右孩子存在且的右孩子存在且大于左兄弟，则令大于左兄弟，则令j指向它指向它，让它沿大基下沉，让它沿大基下沉void sift(table *L, int k, int m) int i,j,finished; /*初始化初始化*/ i=k;j=2*i; L-r0=L-rk; finished=0; /*确定下沉位置确定下沉位置*/ while(j=m)&(!finished) if (jrj+1.keyL-rj.key) j+; if(L-r0=L-rj) finished=1; else L-ri=L-rj; i=j; j=2*j; /* 被筛数下沉被筛数下沉*/ L-r

37、i=L-r0; 建堆总体控制：建堆总体控制： for(i= L-length/2 ;i=1;i-) sift (L, i, L-length); /*对所有元素建堆对所有元素建堆*/堆排序过程：堆排序过程：1）建初始堆（大根堆）建初始堆（大根堆）2）重复以下工作，一直到排序结束）重复以下工作，一直到排序结束交换截尾交换截尾重新建堆重新建堆 for(i=L-length;i=2;i-) void heapsort(table *L) int i; for(i=L-length/2;i=1;i-) sift(L,i,L-length); /*对所有元素建堆对所有元素建堆*/for(i=L-leng

38、th;i=2;i-) /* i表示当前堆的大小，表示当前堆的大小，即等待排序的元素的个数即等待排序的元素的个数*/ L-r0=L-ri; L-ri=L-r1; L-r1=L-r0; /*上述上述3条语句为将堆中最条语句为将堆中最小元素和最后一个元素交换小元素和最后一个元素交换*/ sift(L,1,i-1);n若设堆中有若设堆中有 n 个结点，且个结点，且 2k-1 n 2k，则对应，则对应的完全二叉树有的完全二叉树有 k 层。在第层。在第 i 层上的结点数层上的结点数 2i (i = 0, 1, , k-1)。在第一个形成初始堆的。在第一个形成初始堆的for循环中对每一个非叶结点调用了一次堆

39、调整算法循环中对每一个非叶结点调用了一次堆调整算法 sift( )，因此该循环所用的计算时间为：，因此该循环所用的计算时间为：2022kiiik1 1算法分析：算法分析：n其中，其中，i 是层序号，是层序号，2i 是第是第 i 层的最大结点数，层的最大结点数，(k-i-1)是第是第 i 层结点能够移动的最大距离。层结点能够移动的最大距离。在第二个在第二个for循环中，调用了循环中，调用了n-1次次sift()算法，该算法，该循环的计算时间为循环的计算时间为O(nlog2n)。因此，堆排序的时间。因此，堆排序的时间复杂性为复杂性为O(nlog2n)。该算法的附加存储主要是在第二个该算法的附加存储

40、主要是在第二个for循环中用来执循环中用来执行对象交换时所用的一个临时对象。因此，该算法行对象交换时所用的一个临时对象。因此，该算法的空间复杂性为的空间复杂性为O(1)。堆排序是一个不稳定的排序方法。堆排序是一个不稳定的排序方法。njnjjikkjkjjjkkjjkkii4 411111111202222222122)(练习：练习：1、给出初始数列、给出初始数列 47、28、32、15、94、33、14、16在堆排序下的建堆过程及示意图。在堆排序下的建堆过程及示意图。2、下列四个选项中，哪一个序列组成一个最小堆？、下列四个选项中，哪一个序列组成一个最小堆？a）20、76、35、23、80、54

41、b）20、54、23、80、35、76c）80、23、35、76、20、54d）20、35、23、80、54、76答案：答案：d算法设计题：算法设计题：1、写一个、写一个Heapinsert(r,key)算法，将关键字算法，将关键字插入到堆插入到堆r中，并保证插入后中，并保证插入后r后仍是堆。后仍是堆。2、写一个建堆算法：从空堆开始，依次读入元、写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。素调用上题中堆插入算法将其插入堆中。3、写一个堆删除算法、写一个堆删除算法heapdelete(r,i)，将，将ri从堆从堆r中删去。中删去。10.4交换排序交换排序 交换排序的

42、基本思路：交换排序的基本思路： 对待排序记录两两进行排序码比较，若不满足排对待排序记录两两进行排序码比较，若不满足排序顺序则交换这对记录，直到任何两个记录的排序码序顺序则交换这对记录，直到任何两个记录的排序码都满足排序要求为止。都满足排序要求为止。 快速排序快速排序冒泡排序冒泡排序 第第1趟，对所有记录从左到右每相邻两个记录的趟，对所有记录从左到右每相邻两个记录的排序码进行比较，如果这两个记录的排序码不符合排排序码进行比较，如果这两个记录的排序码不符合排序要求，则进行交换，这样一趟做完，将排序码最大序要求，则进行交换，这样一趟做完，将排序码最大者放在最后一个位置；者放在最后一个位置； 第第2趟

43、对剩下的趟对剩下的n-l个待排序记录重复上述过程，个待排序记录重复上述过程，又将一个排序码放于最终位置，反复进行又将一个排序码放于最终位置，反复进行n-l次，可将次，可将n-l个排序码对应的记录放至最终位置，剩下的即为排个排序码对应的记录放至最终位置，剩下的即为排序码最小的记录，它在第序码最小的记录，它在第1的位置处。的位置处。 如果在某一趟中，没有发生交换，则说明此时所如果在某一趟中，没有发生交换，则说明此时所有记录已经按排序要求排列完毕，排序结束。有记录已经按排序要求排列完毕，排序结束。 10.4.1 冒泡排序冒泡排序 一趟冒泡：对数列中指定的起点到终点间的数据一趟冒泡：对数列中指定的起点

44、到终点间的数据进行连续冒泡。进行连续冒泡。4728321594331416例：例：2847321594331416324728159433141615472832943314161547283294331416339415472832141614941547283233161694154728323314void bubblesort(table *L) /*冒泡排序冒泡排序*/ int i,j,flag; i=L-length; /*变量变量i记录参与冒泡排序的元素个数记录参与冒泡排序的元素个数/ while (i1) flag=0; for (j=0;jrj.keyL-rj+1.key)

45、/逆序则交换逆序则交换 L-r0=L-rj; L-rj=L-rj+1; L-rj+1=L-r0; flag=1; if (flag=0) break; i-;/元素个数减元素个数减/ /*算法算法10.8 冒泡排序算法冒泡排序算法*/ 二、快速排序二、快速排序基本思想：基本思想：1）找一个记录，以它的关键字作为）找一个记录，以它的关键字作为“枢轴枢轴”，（通常为第一个数（通常为第一个数t）2）划分）划分其关键字小于枢轴的记录均移动至该其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。动至该记录之后。3）对上步分成

46、的两个无序数组段重复）对上步分成的两个无序数组段重复1）、）、2）操作直到段长为操作直到段长为1。t=tpivot2125*i = 125164908pivot21254925*16080 1 2 3 4 5 6pivot例：例：211608i = 225*pivot4925i = 3081621254925*关键问题：关键问题：如何划分？如何划分？事实：划分过程也是当前选出数事实：划分过程也是当前选出数t的最后定位过程。的最后定位过程。方法：从外向内来回比较法。方法：从外向内来回比较法。1）将当前选择的数保存到）将当前选择的数保存到t中，以空出左端。中，以空出左端。2）从右向左依次比较，放过

47、那些大于）从右向左依次比较，放过那些大于t的数，一的数，一直找到第一个小于等于直找到第一个小于等于t的数；将此数放入空左端的数；将此数放入空左端，并令其空出的位置为新右端，原左端的右邻为，并令其空出的位置为新右端，原左端的右邻为新左端。新左端。3）从左向右依次地放过那些）从左向右依次地放过那些=t的数；将此数放入空右端，并令其空的数；将此数放入空右端，并令其空出的位置为新左端，原右端的左邻为新右端。出的位置为新左端，原右端的左邻为新右端。4）重复）重复2）3）步，直至）步，直至t进入最终位置。进入最终位置。例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：21254925*

48、1608从右向左找第从右向左找第一个小于一个小于t的数的数21rightleft例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft21例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft从左向右找第一从左向右找第一个大于个大于 t 的数的数例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft例：例： 1 2 3

49、4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft21从右向从右向左扫描左扫描例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608leftright21例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608leftright例：例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608leftright从左向从左向右扫描右扫描21例例： 1 2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft例：例： 1

50、2 3 4 5 6t =a1初始序列如下：初始序列如下：254925*1608rightleft一次划分结束条件：一次划分结束条件：left=right21 快速排序就是不断地对原始数据段及划分中快速排序就是不断地对原始数据段及划分中分出的新数据段作划分。分出的新数据段作划分。关键一步：对关键一步：对 L-rleft.right作一次来回比较。作一次来回比较。1）从右向左找第一个不大于）从右向左找第一个不大于t的数。的数。 while (leftright & t.keyrright.key) right-; 2）将）将rright填入空左端，并设置新左端。填入空左端，并设置新左端。

51、if (leftright) 3）从左向右找第一个大于）从左向右找第一个大于t的数。的数。 while ( ) left+; 4）将）将rleft填入空右端，并设置新右端。填入空右端，并设置新右端。if (leftrright=L-rleft;right-; L-rleft=L-rright;left+;leftL-rleft.keyright快速排序的总体控制：快速排序的总体控制：quicksort(&L, low, high )1）初始化：）初始化： left=low; right=high; t=rleft;2）对当前数据段作划分：）对当前数据段作划分： do 一次来回比较；一次

52、来回比较； while (left!=right);3）将）将t填入最终位置填入最终位置:L-r =t; 4）递归地对）递归地对Llow.left-1，Lleft+1.high 作快作快速排序。速排序。 quicksort( ); leftquicksort( );L,low,left-1L,left+1,highvoid quicksort(table *L,int low, int high) int left,right; recordtype t; if (lowrleft; do while (leftright & t.keyrright.key) right-; /*从右

53、往左找第一个小于等于从右往左找第一个小于等于t的元素的元素*/ if (leftrleft=L-rright; left+; /*将将rright的值填入左端，并设新左端的值填入左端，并设新左端*/ while (leftL-rleft.key) left+; /*从左往右找第一个大于从左往右找第一个大于t的元素的元素*/快速排序递归快速排序递归出口条件出口条件一次划分一次划分初始化工作初始化工作来回比较进行来回比较进行一次划分一次划分 if (leftrright=L-rleft; right-; /*将将rleft的值填入右端，并设新右端的值填入右端，并设新右端*/ while (left

54、!=right); L-rleft=t; /*t存入相应位置存入相应位置*/ /*递归对左段和右段进行快速排序递归对左段和右段进行快速排序*/ quicksort( L,low,left-1); quicksort( L,left+1,high); 算法分析：算法分析： 快速排序被认为是在所有同数量级快速排序被认为是在所有同数量级O(nlogn)的的排序方法中，其平均性能是最好的。排序方法中，其平均性能是最好的。例例 但是，若待排记录的初始状态为按关键字有序但是，若待排记录的初始状态为按关键字有序时，快速排序将蜕化为冒泡排序，其时间复杂度为时，快速排序将蜕化为冒泡排序，其时间复杂度为O(n2)

55、。初始序列：初始序列：20 30 40 50 60 70 80 90 100什么样的初始什么样的初始序列具有最佳的序列具有最佳的快速排序时间效率？快速排序时间效率？ 练习：练习：1、给定初始序列、给定初始序列31，68，45，90，23，39，54，12、87、76，请写出以，请写出以31为枢轴的划分为枢轴的划分结果结果。2、试设计一个算法，使得在、试设计一个算法，使得在O(n)的时间内重排数组，的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字将所有取负值的关键字放在所有取非负值的关键字之前。之前。思考题：思考题：采用链式存储的线性表采用链式存储的线性表如何进行快速排序。如何进行

56、快速排序。 （一）双链表一）双链表head4010608020（二）单链表（带头结点）（二）单链表（带头结点） head 4010806030tail=NULLpqpresp指示当前用于划分的枢轴指示当前用于划分的枢轴q指示当前与指示当前与p结点进行比较的结点；结点进行比较的结点；pre 指示指示q的前驱结点；的前驱结点；s用于指示被移动的结点。用于指示被移动的结点。（二）单链表（带头结点）（二）单链表（带头结点） head 4010806030tail=NULLpqpres将将s指示的结点取下插入到当前的链首由以下步骤完成：指示的结点取下插入到当前的链首由以下步骤完成：pre-next=q;

57、（二）单链表（带头结点）（二）单链表（带头结点） head 4010806030tail=NULLpqpres将将s指示的结点取下插入到当前的链首由以下步骤完成：指示的结点取下插入到当前的链首由以下步骤完成：pre-next=q;s-next=head-next;（二）单链表（带头结点）（二）单链表（带头结点） head 4010806030tail=NULLpqpres将将s指示的结点取下插入到当前的链首由以下步骤完成：指示的结点取下插入到当前的链首由以下步骤完成：pre-next=q;s-next=head-next;head-next=s;（二）单链表（带头结点）（二）单链表（带头结点）

58、 head 4010806030tail=NULLpqpres将将s指示的结点取下插入到当前的链首由以下步骤完成：指示的结点取下插入到当前的链首由以下步骤完成：pre-next=q;s-next=head-next;head-next=s;（二）单链表（带头结点）（二）单链表（带头结点）将将s指示的结点取下插入到当前的链首由以下步骤完成：指示的结点取下插入到当前的链首由以下步骤完成：pre-next=q;s-next=head-next;head-next=s; head 1040806030tail=NULLpqpres（二）单链表（带头结点）（二）单链表（带头结点）若若q指示的结点值比指示

59、的结点值比p指示的结点值大，则该结点的位指示的结点值大，则该结点的位置保留不动，处理下一个结点。即：置保留不动，处理下一个结点。即： head 1040806030tail=NULLpqprespre=q;q=q-next;（二）单链表（带头结点）（二）单链表（带头结点）若若q指示的结点值比指示的结点值比p指示的结点值大，则该结点的位指示的结点值大，则该结点的位置保留不动，处理下一个结点。即：置保留不动，处理下一个结点。即： head 1040806030tail=NULLpqprespre=q;q=q-next;（二）单链表（带头结点）（二）单链表（带头结点）若若q指示的结点值比指示的结点值

60、比p指示的结点值大，则该结点的位指示的结点值大，则该结点的位置保留不动，处理下一个结点。即：置保留不动，处理下一个结点。即： head 1040806030tail=NULLpqprespre=q;q=q-next;（二）单链表（带头结点）（二）单链表（带头结点） head 1040806030tail=NULLpqpres（二）单链表（带头结点）（二）单链表（带头结点） head 3010804060tail=NULLpqpres（二）单链表（带头结点）（二）单链表（带头结点） head 3010804060tail=NULLpq=NULLpres划分结束条件：划分结束条件：q=tail;递归地对前半部分和后半部分进行快速链式排序：递归地对前半部分和后半部分进行快速链式