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

1、 排序的方法有很多，但简单地判别那一种算排序的方法有很多，但简单地判别那一种算 法最好，以便可以普遍选用那么是困难的。法最好，以便可以普遍选用那么是困难的。 评价排序算法好坏的规范主要有两条：算法评价排序算法好坏的规范主要有两条：算法 执行所需求的时间和所需求的附加空间。执行所需求的时间和所需求的附加空间。 另外，算法本身的复杂程度也是需求思索另外，算法本身的复杂程度也是需求思索 的一个要素。的一个要素。 排序算法所需求的附加空间普通都不大，矛排序算法所需求的附加空间普通都不大，矛 盾并不突出。而排序是一种经常执行的一盾并不突出。而排序是一种经常执行的一 种运算，往往属于系统的中心部分，因此种

2、运算，往往属于系统的中心部分，因此 排序的时间开销是算法好坏的最重要的标排序的时间开销是算法好坏的最重要的标 志。志。 为简单起见，数据的存储构造采用记为简单起见，数据的存储构造采用记录数组方式。记录数组的类型阐明如下：录数组方式。记录数组的类型阐明如下：其中其中n为记录总数加为记录总数加1算法中引入附加记录算法中引入附加记录temp的作用：是进入的作用：是进入查找循环之前，它保管了查找循环之前，它保管了Ri的副本，使得的副本，使得不至于因记录的后移而丧失不至于因记录的后移而丧失Ri中的内容。中的内容。算法分析算法分析nininOnninOnni2222)(2/ )4)(1()21()(2/

3、) 1)(2(移动次数的最大值比较次数的最大值希尔排序的根本过程希尔排序的根本过程希尔排序算法希尔排序算法rectype Rn+d1;rectype Rn+d1;int dt;int dt; SHELLSORT(rectype SHELLSORT(rectype R,int d)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 for (i=h+dl;in+dl;i+)(i=h+dl;in+dl;i+) temp tempRi;Ri; j

4、ji-h;i-h; while while (temp.keyRj.key)(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排序的时间性能优于直接插入排排序的时间性能优于直接插入排序呢？由于直接插入排序在初态为正序时所需时间序呢？由于直接插入排序在初态为正序时所需时间最少，实践上，初态为根本有序时直接插入排序所最少，实践上，初态为根本有序时直接插入排序所需的比较和挪动次数均较少。另一方面，当需的比较和挪动次数均较少

5、。另一方面，当n n值较值较小时，小时，n n和和n2n2的差别也较小，即直接插入排序的最的差别也较小，即直接插入排序的最好时间复杂度好时间复杂度O(n)O(n)和最坏时间复杂度和最坏时间复杂度O(n2)O(n2)差别不差别不大。在大。在shellshell排序开场时增量较大，分组较多，每排序开场时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增组的记录数目少，故各组内直接插入较快，后来增量逐渐减少，分组数逐渐减少，而各组的记录数目量逐渐减少，分组数逐渐减少，而各组的记录数目逐渐增多，但组内元素曾经过多次排序，数组曾经逐渐增多，但组内元素曾经过多次排序，数组曾经比较接近有序形

6、状，所以新的一趟排序过程也较块。比较接近有序形状，所以新的一趟排序过程也较块。 首先依序比较首先依序比较n个待排序记录的一端开场，个待排序记录的一端开场，依次两两比较排序码，只需是逆序，那么交依次两两比较排序码，只需是逆序，那么交换，这样完成一趟交换排序，结果就是将最换，这样完成一趟交换排序，结果就是将最大或最小的记录交换到最后面或最前大或最小的记录交换到最后面或最前面；面； 然后其他的记录同法进展两两比较，每一趟然后其他的记录同法进展两两比较，每一趟都将较大小元素交换到最后前面，都将较大小元素交换到最后前面，不断进展下去，直到最后一个记录排完或没不断进展下去，直到最后一个记录排完或没有要交换

7、的元素的时候为止。有要交换的元素的时候为止。 首先从首先从R0到到Rn-1对对n个元素比较其排序码，个元素比较其排序码，对逆序元素进展交换，完成一趟排序时，将对逆序元素进展交换，完成一趟排序时，将排序码值最到的元素几交换到最后一个位置，排序码值最到的元素几交换到最后一个位置，即即Rn-1，该过程相当于一趟冒泡；，该过程相当于一趟冒泡； 然后，又从然后，又从R0到到Rn-2中又进展一趟交换中又进展一趟交换冒泡，这样不断进展下去，直到最后一个元冒泡，这样不断进展下去，直到最后一个元素素R0或某一趟没有交换元素为止。或某一趟没有交换元素为止。 冒泡排序算法冒泡排序算法void bubblesort(

8、R)void bubblesort(R) for(i=0;in-2;i+) for(i=0;i=i;j+) for(j=n-1;j=i;j+) if (Rj+1.keyRj.key) if (Rj+1.key= temp.key)&(i= temp.key)&(ij) j-; if (ij) Ri+=Rj; if (ij) Ri+=Rj; while (Ri.key=temp.key)&(ij) i+; while (Ri.key=temp.key)&(ij) i+; if (ij) Rj-=Ri; if (ij) Rj-=Ri; while (i!=j); while (i!=j); Ri=

9、temp; Ri=temp; return i; return i; QUICKSORT(rectype R,int s1,int t1)QUICKSORT(rectype R,int s1,int t1) int i; int i; if (s1t1) if (s1t1) i=PARTITION(R,s1,t1); i=PARTITION(R,s1,t1); QUICKSORT(R,s1,i-1); QUICKSORT(R,s1,i-1); QUICKSORT(R,i+1,t1); QUICKSORT(R,i+1,t1); 112)(2/ ) 1()(ninOnnin比较次数的最大值n)O(

10、nlognC(1)nnlog)C(n/22kn.)8C(n/23n)2C(n/24n/42n)4C(n/22n)2C(n/22n/2n2C(n/2)nC(n)22kk3322两种常见的选择排序两种常见的选择排序 直接选择排序直接选择排序 堆排序堆排序根本原理根本原理: 将待排序的结点分为已排序将待排序的结点分为已排序(初初始为空始为空)和为未排序两组，依次将未排序的和为未排序两组，依次将未排序的结点中值最小的结点插入已排序的组中。结点中值最小的结点插入已排序的组中。49386597761327491338659776492749132765977649384913273897764965491

11、327384976976549132738494997657613273849496597761327384949657697直接选择排序算法直接选择排序算法SELECTSORT(rectype R)SELECTSORT(rectype R) int i,j,k; int i,j,k; rectype temp; rectype temp; for (i=0;in-1;i+) for (i=0;in-1;i+) k=i; k=i; for (j=i+1;jn;j+) for (j=i+1;jn;j+) if (Rj.keyRk.key) k=j; if (Rj.key= low(n/2)i =

12、 low(n/2)的结的结点都是叶子，因此以这些结点为根的子点都是叶子，因此以这些结点为根的子树都已是堆。这样，我们只需依次将序树都已是堆。这样，我们只需依次将序号为号为low(n/2)low(n/2)，low(n/2)-1low(n/2)-1，.，1 1的的结点作为根的子树都调整为堆即可。结点作为根的子树都调整为堆即可。 我们以大根堆为例进展阐明我们以大根堆为例进展阐明 假设知结点假设知结点RiRi的左右子树已是堆，如何将以的左右子树已是堆，如何将以RiRi为根的完全为根的完全二叉树也调整为堆？二叉树也调整为堆？ 处理这一问题可采用处理这一问题可采用“挑选法，其根本思想是：由于挑选法，其根本

13、思想是：由于RiRi的的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的左右子树已是堆，这两棵子树的根分别是各自子树中关键字最大的结点，所以我们必需在结点，所以我们必需在RiRi和它的左右孩子中选取关键字最大的结和它的左右孩子中选取关键字最大的结点放到点放到RiRi的位置上。假设的位置上。假设RiRi的关键字已是三者中的最大者，那的关键字已是三者中的最大者，那么无须做任何调整，以么无须做任何调整，以RiRi为根的子树已构成堆，否那么必需将为根的子树已构成堆，否那么必需将RiRi和具有最大关键字的左孩子和具有最大关键字的左孩子R2iR2i或右孩子或右孩子R2i+1R2i+1进展交换。进

14、展交换。假定假定R2iR2i的关键字最大，将的关键字最大，将RiRi和和R2iR2i交换位置，交换之后有能交换位置，交换之后有能够导致够导致R2iR2i为根的子树不再是堆，但由于为根的子树不再是堆，但由于R2iR2i的左右子树依然是的左右子树依然是堆，于是可以反复上述过程，将以堆，于是可以反复上述过程，将以R2iR2i为根的子树调整为堆，为根的子树调整为堆，.，如此逐层递推下去，最多能够调整到树叶。如此逐层递推下去，最多能够调整到树叶。例子：关键字序列为例子：关键字序列为 42，13，91，23， 24， 16，05，88，n=8，故从第四个结点开场调，故从第四个结点开场调整整42421313

15、9191232324241616050588884213912324160588424213139191888824241616050523234213918824160523不调整不调整424213139191888824241616050523234213918824160523424288889191232324241616050513134288912324160513919188884242232324241616050513139188422324160513建成的堆建成的堆挑选算法挑选算法SIFT(rectype R,int i;int m)SIFT(rectype R,int

16、i;int m) int j; int j; rectype temp; rectype temp; temp=Ri; temp=Ri; j=2 j=2* *i;i; while (j=m) while (j=m) if (jm)&(Rj.keyRj+1.key) j+; if (jm)&(Rj.keyRj+1.key) j+; if (temp.keyRj.key) if (temp.key=1; i-) SIFT(R, i, n) 由于建堆的结果把关键字最大的记录选到了堆由于建堆的结果把关键字最大的记录选到了堆顶的位置，而排序的结果应是升序，所以，应该顶的位置，而排序的结果应是升序，所以，

17、应该将将R1和和Rn交换，这就得到了第一趟排序的结果。交换，这就得到了第一趟排序的结果。 第二趟排序的操作首先是将无序区第二趟排序的操作首先是将无序区R1到到Rn-1调整为堆。这时对于当前堆来说，它的左右子树调整为堆。这时对于当前堆来说，它的左右子树依然是堆，所以，可以调用依然是堆，所以，可以调用SIFT函数将函数将R1到到Rn-1调整为大根堆，选出最大关键字放入堆顶，调整为大根堆，选出最大关键字放入堆顶，然后将堆顶与当前无序区的最后一个记录然后将堆顶与当前无序区的最后一个记录Rn-1交交换，如此反复进展下去。换，如此反复进展下去。9191888842422323242416160505131

18、39188422324160513a a初始堆初始堆R1R1到到R8R8131388884242232324241616050591911388422324160591b b第一趟排序之后第一趟排序之后c c重建的堆重建的堆R1R1到到R7R7888824244242232313131616050591918824422313160591050524244242232313131616888891910524422313168891d d第二趟排序之后第二趟排序之后e e重建的堆重建的堆R1R1到到R6R642422424161623231313050588889191422416231305

19、8891f f第三趟排序之后第三趟排序之后050524241616232313134242888891910524162313428891g g重建的堆重建的堆R1R1到到R5R5242423231616050513134242888891912423160513428891h h第四趟排序之后第四趟排序之后131323231616050524244242888891911323160524428891i i重建的堆重建的堆R1R1到到R4R4232313131616050524244242888891912313160524428891j j第五趟排序之后第五趟排序之后05051313161

20、6232324244242888891910513162324428891k k重建的堆重建的堆R1R1到到R3R3161613130505232324244242888891911613052324428891l l第六趟排序之后第六趟排序之后050513131616232324244242888891910513162324428891m m重建的堆重建的堆R1R1到到R2R2131305051616232324244242888891911305162324428891n n第七趟排序之后第七趟排序之后0505131316162323242442428888919105131623244

21、28891堆排序算法堆排序算法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;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); 归并排序是利用归并排序是利用“归并技术来进展排序，所

22、归并技术来进展排序，所谓归并是指将假设干个曾经排序的子序列合并谓归并是指将假设干个曾经排序的子序列合并为一个有序序列。其算法比较简单，可以直接为一个有序序列。其算法比较简单，可以直接给出。给出。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 归并算法归并算法void merge(R,R1,low,mid,hign)void merge(R,R1,low,mid,hign)/Rlow/Rlow到到RmidRmid与与Rmid+1Rmid+1到到RhighRhigh是两个有序是两

23、个有序序列，结果是合并为一个有序序列序列，结果是合并为一个有序序列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) if(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+;

24、 while(j=high) R1k+=Rj+; 归并排序就是利用上述归并操作实归并排序就是利用上述归并操作实现排序的。其根本思想是：将待排序列现排序的。其根本思想是：将待排序列R0R0到到Rn-1Rn-1看成看成n n个长度为个长度为1 1的有序子的有序子序列，把这些子序列两两归并，便得到序列，把这些子序列两两归并，便得到high(n/2)high(n/2)个有序的子序列。然后再把个有序的子序列。然后再把这这high(n/2)high(n/2)个有序的子序列两两归并，个有序的子序列两两归并，如此反复，直到最后得到一个长度为如此反复，直到最后得到一个长度为n n的有序序列。上述每次的归并操作，

25、都的有序序列。上述每次的归并操作，都是将两个子序列归并为一个子序列，这是将两个子序列归并为一个子序列，这就是就是“二路归并，类似地还可以有二路归并，类似地还可以有“三三路归并或路归并或“多路归并。多路归并。归并过程例如归并过程例如(25) (57) (48) (37) (12) (92) (86)(25 57) (37 48) (12 92) (86)(25 37 48 57) (12 86 92)(12 25 37 48 57 86 92)一趟归并算法一趟归并算法归并排序就是利用上述归并操作实现排序的。归并排序就是利用上述归并操作实现排序的。 其根本思想是：其根本思想是： 将待排序的记录序列

26、将待排序的记录序列R0R0到到Rn-1Rn-1看成为看成为n n个长度为个长度为1 1的有序序列，将其进展两两归并，那么得的有序序列，将其进展两两归并，那么得到到n/2n/2个个n n为基数时候那么为为基数时候那么为 n+1n+1/2/2个个长度为长度为2 2的有序序列，然后继续进展，直到最后得到的有序序列，然后继续进展，直到最后得到一个长度为一个长度为n n的有序序列为止。这就是的有序序列为止。这就是2-2-路归并排序。路归并排序。 其中，最关键的是将两个长度为其中，最关键的是将两个长度为l l的有序序的有序序列归并为长度为列归并为长度为2l2l的有序序列。的有序序列。一趟归并算法一趟归并算

27、法MERGEPASS(rectype R,rectype R1,int MERGEPASS(rectype R,rectype R1,int length)length) int i,j; int i,j; i=0; i=0; while (i+2 while (i+2* *length-1n)length-1n) MERGE(R,R1,i,i+length-1,i+2 MERGE(R,R1,i,i+length-1,i+2* *length-1);length-1); i=i+2 i=i+2* *length;length; if (i+length-1n-1) if (i+length-1

28、n-1) MERGE(R,R1,i,i+length-1,n-1); MERGE(R,R1,i,i+length-1,n-1); else else for (j=i;jn;j+) R1j=Rj; for (j=i;jn;j+) R1j=Rj; 在上述一趟归并过程中，假设正好配在上述一趟归并过程中，假设正好配成对时候，即可正常完成，否那么最后一成对时候，即可正常完成，否那么最后一次归并时，能够有两种情况：次归并时，能够有两种情况： 1(2k+1)*lenn2(k+1)*len 表示有两个有序序列，但后一个长度缺表示有两个有序序列，但后一个长度缺乏乏len，此时归并方法与前一样，仅仅是参，此时归

29、并方法与前一样，仅仅是参数不同而已。数不同而已。 22k*lenn2(k+1)*len 表示只需一个有序序列，此时曾经是有表示只需一个有序序列，此时曾经是有序的，故只需求复制到序的，故只需求复制到R1中即可。中即可。归并排序算法归并排序算法MERGESORT(rectype R)MERGESORT(rectype R) int length=1; int length=1; while (lengthn) while (lengthn) MERGEPASS(R,R1,length); MERGEPASS(R,R1,length); length=2 length=2* *length;leng

30、th; MERGEPASS(R1,R,length); MERGEPASS(R1,R,length); length=2 length=2* *length;length; 1792083069385998455927133B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.

31、e B8.e B9.e 27193339845530620817985992719333984553062081798599B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 33984306208955859271179933062089335585

32、927117998493B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.f B1.f B2.f B3.f B4.f B5.f B6.f B7.f B8.f B9.f B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e B0.e B1.e B2.e B3.e B4.e B5.e B6.e B7.e B8.e B9.e 17930698485993355932082719335593179208271306859984分配排序算法分配排序算法typedef structtypedef struct int keyd; int keyd; int next; int next