数据结构第六章排序资料.ppt

《数据结构第六章排序资料.ppt》由会员分享，可在线阅读，更多相关《数据结构第六章排序资料.ppt（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构第六章排序徐晓晖制p基本概念基本概念p插入排序插入排序p交换排序交换排序p选择排序选择排序p归并排序归并排序p基数排序基数排序p外部排序外部排序数据结构第六章排序徐晓晖制10-1 排序的基本概念排序的基本概念是记录中的一个(或多个)字段，如果是关键码，则按关键码排序；排序码也可以不是关键码，则可能有多个记录具有相同的排序码，排序的结果不惟一。将一个数据元素集合或序列重新排列成一个按数据元素某个数据项值有序的序列。l排序排序l排序码排序码l稳定排序稳定排序l不稳定排序不稳定排序l内排序内排序l外排序外排序假设R0,R1,Rn-1是由n个记录组成的文件，K0,K1,Kn-1是排序码集合，假

2、设Ki=Kj(0=i,j=n-1,ij)，且在排序前的序列中Ri领先于Rj(即ij)，若在排序后的序列中Ri仍领先于Rj，则称所用的排序方法是稳定的稳定的，否则是不稳定的不稳定的。待排序的记录在排序过程中全部存放在内存的称为内排序内排序，如果排序过程中需要使用外存的称为外排序外排序。数据结构第六章排序徐晓晖制排序方法可以分为五种：插入排序、选择排序、插入排序、选择排序、交换排序、基数排序和归并排序交换排序、基数排序和归并排序。排序中的基本操作：比较比较关键码大小和移动移动记录。评价排序算法好坏的标准主要有两条执行算法所需的时间；执行算法所需要的附加空间。排序的时间开销可以用算法执行中的比较比较

3、和移动移动次数来表示。数据结构第六章排序徐晓晖制10-2插入排序插入排序插入排序插入排序插入排序的基本思想：每步将一个待排序的记录按其的基本思想：每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。全部插入完为止。u直接插入排序直接插入排序假设待排序的假设待排序的n n个记录个记录R0,R1,Rn-1R0,R1,Rn-1存放在数组中，存放在数组中，直接插入法直接插入法直接插入法直接插入法是在插入记录在插入记录Ri(iRi(i=1,2n-1)=1,2n-1)时，记录集合时，记录集合被划分为两个区间被划分为两个区间R

4、0R0，Ri-1Ri-1和和 RiRi，Rn-1Rn-1，其中，其中，前一个子区间已经排好序，后一个子区间是当前未前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码排序的部分，将排序码KiKi与与Ki-1Ki-1，Ki-2,K0Ki-2,K0依次比依次比较，找出应该插入的位置，将记录较，找出应该插入的位置，将记录RiRi插入，原位置插入，原位置的记录向后顺移。的记录向后顺移。数据结构第六章排序徐晓晖制例：设待排序记录的排序码为：49，38，65，97，76，13，27，49，请用直接插入排法排序。i=2:4938659776132749i=3:3849659776132749i=

5、4:3849659776132749i=5:3849659776132749i=6:3849657697132749i=7:1338496576972749i=8:1327384965769749i=9:1327384949657697数据结构第六章排序徐晓晖制typedeftypedef structstruct KeyTypeKeyTypekeykey；DataTypeDataType;voidInsertSort(DataTypeR,intn)intI;for(i=2;i=n;i+)if(Ri.keyRi-1.key)R0=Ri;for(j=i-1;R0.deyRj.key;j-)Rj+

6、1=Rj;Rj+1=R0;数据结构第六章排序徐晓晖制算法分析如下:空间效率：只需要一个记录的辅助空间。时间效率：最小比较记录的次数为n-1=O(n)；最大比较记录的次数为(n+2)(n-1)/2=O(n2)；最小移动记录的次数为0次；最大移动记录的次数为(n+4)(n-1)/2=O(n2)。平均情况下，插入记录大约同前面i/2个记录进行关键码比较和移动，因此插入排序的时间复杂度为O(n2)直接插入排序是稳定的排序算法数据结构第六章排序徐晓晖制u二分法插入排序二分法插入排序由于插入排序的基本操作是在有序表中进行查找,而查找的过程是可以用折半查找来实现的。由此实现的排序称为二分法插入排序二分法插入

7、排序。二分法插入排序必须采用顺序存储方式。数据结构第六章排序徐晓晖制voidB_InsertSort(DataTypeR,intn)intI;intcow,high,mid;for(i=2;i=n;i+)R0=Ri;low=1;high=i-1;while(lowRmid.key)low=mid+1;elsehigh=mid-1;for(j=i-1;j=high+1;j-)Rj+1=Rj;Rhigh+1=R0;数据结构第六章排序徐晓晖制i=2:4938659776132749i=3:3849659776132749i=4:3849659776132749i=5:3849659776132749

8、i=6:3849657697132749i=7:1338496576972749i=8:1327384965769749i=9:1327384949657697low=1,high=1low=1,high=2low=1,high=3low=1,high=4low=1,high=5数据结构第六章排序徐晓晖制算法分析如下:定位一个关键码的位置需比较次数至多为,比较次数时间复杂度为而移动记录的次数和直接插入排序相同，因此时间复杂度仍为O(n2)二分插入排序是一个稳定的排序方法。数据结构第六章排序徐晓晖制u表插入排序基本思想：在直接插入的基础上减少移动次数，主要是在记录中设置一个指针字段，记录链接成链

9、表，初始时，链表为空，头结点指针域置为0，并在头结点数据域放比所有记录关键码都大的整数，然后，向链表中插入结点typedefstructDataTypedata;intnext;NodeType;NodeTypeRn+1;数据结构第六章排序徐晓晖制MAX49386597761327490-0112030445262738这个有序的链表，查找则只能顺序查找，而不能随机查找若需要，要发对记录进行重排，使其在物理上有序。012345678数据结构第六章排序徐晓晖制voidB_InsertSort(NodeTypeR,intn)inti,j,p;DataTypeS;j=R0.next;i=1;whil

10、e(in)if(i=j)j=Rj.next;i+;elseif(ij)p=Rj.next;S=Ri;Ri=Rj;Rj=S;Ri.next=j;j=p;elsewhile(ji)j=Rj.next;数据结构第六章排序徐晓晖制012345678MAX4938659776132749681504723jip134986jip27381jij7p387655jij496970pjip497648jijp659770jijp769708ij数据结构第六章排序徐晓晖制u希尔排序Shell排序排序又称缩小增量排序，排序的基本思想是先取d1n,将整个待排记录分成d1个组，所有距离为d1倍数的记录放在同一组中，

11、先在各组进行直接插入排序；然后，取d2d1重复上述分组和排序工作；直到di=1为止，就可以完成整个的排序工作。Shell排序的一个特点是：子序列的构成不是简单“逐段分割”，而是将相隔某个增量的记录组成一个子序列。di有各种取法,Shell取D.Knuth取数据结构第六章排序徐晓晖制49386597761327495504初始：d1=10/2=54913 2738496555970476一趟排序后：1327495504493865977604273855二趟排序后：13044938274955659776041338494938279776希尔排序是个不稳定的排序方法数据结构第六章排序徐晓晖制v

12、oidShellInsert(DataTypeR,intdk)inti;for(i=dk+1;i=n;i+)if(Ri.key0&R0.keyRj.key;j=j-dk)Rj+dk=Rj;Rj+dk=R0;void ShellSort(DataType R,int n,int d,int t)int k;for(k=0;kt;k+)ShellInsert(R,dk);数据结构第六章排序徐晓晖制10-3交换排序交换排序交换排序的基本方法是两两比较待排序记录的排序码，交换不满足顺序要求的偶对，直到全部满足为止。冒泡排序冒泡排序的方法是先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，

13、则两个记录交换位置，否则不交换;然后,对新的第二个记录R1与第三个记录R2做同样的处理；依次类推，直到处理完第n-1个记录和第n个记录，从(R0,R1)到(Rn-2,Rn-1)的n-1次比较和交换过程称为一次起泡。重复这样起泡过程最多n-1次就能完成排序.u冒泡排序冒泡排序数据结构第六章排序徐晓晖制voidBubble_Sort(DataTypeR,intn)inti,j,swap;for(i=1;in;i+)swap=0;for(j=1;jRj+1.key)R0=Rj;Rj=Rj+1;Rj+1=R0;swap=1;if(swap=0)break;数据结构第六章排序徐晓晖制1304493827

14、49556597760413384927497697041338274949556576972738最好情况下：移动次数为0，比较次数为n-1最差情况下：比较次数稳定的排序方法数据结构第六章排序徐晓晖制u快速排序快速排序快速排序快速排序基本思想是：通过一趟排序将待排记录分割基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。进行排序，以达到整个序列有序。一趟快速排序的具体做法是：附设两个指针i和j

15、,它们的初值分别是一个序列的第一个和最后一个记录的位置，设枢轴记录的关键字为temp.key，在首先从j所指位置起向前搜索直到第一个关键字小于temp.key的记录和i记录交换，然后从i所指位置起向后搜索，找到第一个关键字大于temp.key的记录和j记录互相交换，重复交替这两步直到i=j为止。数据结构第六章排序徐晓晖制491438749665849552749ij27iii74jjj8i96jj492714388496596495574ij278ii38j278142738496596495574ij65j55i96j49i658142738495549659674数据结构第六章排序徐晓晖制

16、intPartition(DataTypeR,inti,intj)R0=Ri;while(ij)while(i=R0.key)j-;if(ij)Ri=Rj;i+;while(ij&Ri.keyR0.key)i+;if(ij)Rj=Ri;j-;Ri=R0;returni;数据结构第六章排序徐晓晖制voidQuick_Sort(DataTypeR,ints,intt)if(st)i=Partition(R,s,t);Quick_Sort(R,s,i-1);Quick_Sort(R,i+1,t);voidQuick(DataTypeR,intn)Quick_Sort(R,1,n);数据结构第六章排序

17、徐晓晖制快速排序的记录移动次数不大于比较次数，所以，快速排序的最坏时间复杂度应为O(n2),最好时间复杂度为O(nlog2n)。4927651483855499674上例中对应的递归调用过程的二叉树快速排序是通常被认为同数量级的排序方法中平均性能最好的。快速排序是一个不稳定排序方法数据结构第六章排序徐晓晖制10-4 选择排序选择排序每一趟在n-i+1个记录中选取关键码最小的记录作为有序序列中第i个记录，直到全部排完。u简单选择排序简单选择排序基本方法是首先在所有记录中选出排序码最小的记录，首先在所有记录中选出排序码最小的记录，与第一个记录交换，然后在其余的记录中再选出排序与第一个记录交换，然后

18、在其余的记录中再选出排序码最小的记录与第二个记录交换，以此类推，直到所码最小的记录与第二个记录交换，以此类推，直到所有记录排好序。有记录排好序。数据结构第六章排序徐晓晖制voidSelect_Sort(DataTypeR,intn)inti,j,k;for(i=1;in;i+)for(k=i,j=i+1;j=n;j+)if(Rj.keyn/2的结点都是叶结点，以这些结点为根的子树均已是堆，只需依次将以序号n/2,n/2-1,1结点为根的子树调整为堆即可。用筛选法为以Ri为根的完全二叉树建堆，若Ri的左右子树都是堆，可以把Ri与其左右子树根结点R2i+1,R2i+2中最大者交换位置。若交换位置后

19、破坏了子树的堆特性，则再对这棵子树重复交换过程，直到以Ri为根结点的子树成为堆。数据结构第六章排序徐晓晖制VoidheapAdjust(DataTypeR,ints,intt)inti,j;DataTyperc;rc=Rs;i=s;for(j=2*i;j=t;j=2*j)if(jt&Rj.keyRj.key)break;Ri=Rj;i=j;Ri=rc;数据结构第六章排序徐晓晖制05615948191126150105rcij61ij48ij1505数据结构第六章排序徐晓晖制voidHeapSort(DataTypeR,intn)intI;for(i=n/2;i0;i-)HeapAdjust(R

20、,i,n);for(i=n;i1;i-)R0=R1;R1=Ri;Ri=R0;HeapAdjust(R,1,i-1);数据结构第六章排序徐晓晖制初始序列为26,5,77,1,61,11,59,15,48,19，请用堆排序法排序。（1）初始完全二叉树 (2)调整序号为5的结点 数据结构第六章排序徐晓晖制(3)调整序号为4的结点 (4)调整序号为3的结点 数据结构第六章排序徐晓晖制(5)调整序号为2的结点 (6)调整序号为1的结点 数据结构第六章排序徐晓晖制(7)结点77与结点5互换 (8)重建堆数据结构第六章排序徐晓晖制(9)结点61与结点1互换 (10)重建堆数据结构第六章排序徐晓晖制(11)结

21、点59与结点05互换 (12)重建堆数据结构第六章排序徐晓晖制(13)结点48与结点1互换 (14)重建堆数据结构第六章排序徐晓晖制(15)结点26与结点1互换 (16)重建堆数据结构第六章排序徐晓晖制(17)结点19与结点5互换 (18)重建堆数据结构第六章排序徐晓晖制(19)结点15与结点1互换 (20)重建堆数据结构第六章排序徐晓晖制堆排序的时间耗费主要在构造初始堆，以及排序中去掉最大元素后重建堆两部分。初始建堆共调用HeapAdjust函数n/2次，每次将一个Ri(in/2)为根的子树树调整为堆。个结点的完全二叉树，其深度的结点层数依次为：0,1,1,2,2,2,h-1。个，以它为根的

22、子树深度为h-m。第m层上结点数最多为HeapAdjust算法的每层上与两个子女和排序码值进行比较，所以在m层上结点执行初始建堆最多比较2(h-m)次，第m层所有子树建堆最多比较次数为第一部分数据结构第六章排序徐晓晖制初始建堆总的比较次数为数据结构第六章排序徐晓晖制排序中每去掉最大元素后需要重建堆。重建堆需要与排序码的比较次数为第二部分排序中重建堆比较花费总次数为整个堆排序总的比较次数为结点移动的次数小于比较次数，故总的时间复杂度时间复杂度。堆排序是不稳定的!数据结构第六章排序徐晓晖制归并排序归并排序的基本思想是把待排序的文件分成若干个子文件，先将每个子文件内的记录排序，再将已排序的子文件合并

23、，得到完全排序的文件。10-5 归并排序归并排序假设初始的序列含有n个记录，可以看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到个长度为2或1的有序子序列；再两两归并，如此重复直到得到一个长度为n的有序序列为止。这种排序方法称为二路归并排序二路归并排序。数据结构第六章排序徐晓晖制voidMerge(DataTypeR,DataTypeR1,ints,intm,intt)inti,j,k;i=s;j=m+1;k=s;while(i=m&j=t)if(Ri.keyRj.key)R1k=Ri;k+;i+;elseR1k=Rj;k+;j+;while(i=m)R1k=Ri;k+;i+;w

24、hile(j=t)R1k=Rj;k+;j+;数据结构第六章排序徐晓晖制voidMergePass(DataTypeR,DataTypeR1,intlen,intn)inti;for(i=1;i+2*len-1n;i=i+2*len)Merge(R,R1,i,i+len-1,i+2*len-1)if(i+len-1n)Merge(R,R1,i,i+len-1,n);elseif(i=n)while(i=n)R1i+=Ri+1;归并排序的迭代算法归并排序的迭代算法数据结构第六章排序徐晓晖制VoidMergeSort(DataTypeR,intn)DataTypeR1MAXNUM;intlen;le

25、n=1;while(lenn)MergePass(R,R1,len,n)len=2*len;MergePass(R1,R,len,n);数据结构第六章排序徐晓晖制归并排序的递归算法归并排序的递归算法voidMSort(DataTypeR,DataTypeR1,ints,intt)intm;if(s=t)R1s=Rs;elsem=(s+t)/2;MSort(R,R1,s,m);MSort(R,R1,m+1,t);Merge(R1,R,s,m,t);voidMergeSort(DataTypeR,intn)DataTypeR1MAXNUM;MSort(R,R1,1,n);数据结构第六章排序徐晓晖制

26、255748371282752916255737481282297516253748571229758216122529374857758216121625293748577582数据结构第六章排序徐晓晖制算法分析：时间复杂度：空间复杂度:和待排记录等量的空间。二路归并算法是稳定的。一般情况下很少用于内部排序。数据结构第六章排序徐晓晖制10-6 基数排序基数排序基数排序属于分配排序，分配排序基数排序属于分配排序，分配排序的思想是把排序码分解成若干部分，然后通过对各个部分排序码的分别排序，最终达到整个排序码的排序。基数排序是采用“分配”与“收集”的办法，用对多关键码进行排序的思想实现对单关键码进

27、行排序的方法。数据结构第六章排序徐晓晖制u多关键码排序1.以扑克牌排序为例。每张扑克牌有两个“关键码”：花色和面值。其有序关系为：花色：梅花方块红心黑桃面值：2345678910JQKA可以先按花色排序，之后再按面值排序；也可以先按面值排序，再按花色排序。数据结构第六章排序徐晓晖制文件中任一记录Ri的关键字均由d个分量 构成。若这d个分量中每个分量都是一个独立的关键字，则文件是多关键字的(如扑克牌有两个关键字：点数和花色)；设单关键字的每个分量的取值范围均是：C0kjCrd-1(0jd)可能的取值个数rd称为基数。基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，0)进行箱排序

28、。在d趟箱排序中，所需的箱子数就是基数rd，这就是“基数排序名称的由来。数据结构第六章排序徐晓晖制2781090639305891845052690080830123456789q.e0123456789q.fq0.e278109063930589184 505083008269数据结构第六章排序徐晓晖制9300630831845052780081095892690123456789q.e0123456789q.f930063083184505278008109589269数据结构第六章排序徐晓晖制5050081099300632692780831845890123456789q.e01234

29、56789q.f505008 109930063269278083184589数据结构第六章排序徐晓晖制008063083109184269278505589930数据结构第六章排序徐晓晖制#defineKEY_NUM#defineRADIX#defineMAX_SPACETypedefstructKeyTypekeysKEY_NUM;InfoTypeotheritems;intnext;NodeType;Typedefstructintf;inte;Q_Node;TypedefQ_NodeQueueRADIX;数据结构第六章排序徐晓晖制voidDistribute(NodeTypeR,int

30、i,Queueq)intj;for(j=0;jRADIX;j+)qj.f=qj.e=0;for(p=R0.next;p;p=Rp.next)j=ord(Rp.keysi);if(!gj.f)gj.f=p;elseRqj.e.next=p;qj.e=p;数据结构第六章排序徐晓晖制voidCollect(NodeTypeR;intI,Queueq)intj;for(j=0;!qj.f;j=succ(j)R0.next=qj.f;t=qj.e;while(jRADIX)for(j=succ(j);jRAIX-1&!qj.f;j=succ(j);if(qj.f)Rt.next=qj.f;t=qj.e;

31、数据结构第六章排序徐晓晖制voidRadxSort(NodeTypeR,intn)Queueq;for(i=0;in;i+)Ri.next=i+1;Rn.next=0;for(i=0;iKEY_NUM;i+)Distribute(R,i,q)Collect(R,i,q)数据结构第六章排序徐晓晖制基数排序的时间是线性的(即O(n)。基数排序所需的辅助存储空间为O(n+rd)。基数排序是稳定的。数据结构第六章排序徐晓晖制数据结构第六章排序徐晓晖制(1).平均时间性能：以快速排序法最佳，但最坏情况下不如堆排序和归并排序；在n较大时，归并排序比堆排序快，但所需辅助空间最多。(2).简单排序以直接插入排

32、序最简单，当下列中记录“基本有序基本有序”或n值较小时，是最佳的排序方法。因此常和其他排序方法结合使用。(3).基数排序最适用于n值很大而关键字较小的序列。若关键字也很大，而序列中大多数记录的“最最高位关键字高位关键字”均不同，则也可以先按“最高位关键最高位关键字字”不同将序列分成若干个子序列，而后用直接插入排序。(4).从稳定性来看，基数排序是稳定的排序方法，大部分时间复杂度为的简单排序法都是稳定的。然而，快速排序、堆排序和希尔排序等时间性能较好的排序都是不稳定的。一般来说，排序过程中的比较是数据结构第六章排序徐晓晖制在相邻的两个记录关键字之间进行的排序方法是稳定的。大多数情况下排序是按记录的主关键字进行的，则所有的排序方法是否稳定无关紧要。当排序是按记录的次关键字进行时，则应根据问题所需慎重选择。本章讨论的大多数算法是在顺序存储结构上进行的，因此在排序过程中要进行大量的记录的移动。当记录很大(即每个记录所占的空间很大)时，记录移动所耗费的时间也很多，此时可采用静态链表作存储结构，如表插入排序，链式基数排序，以修改指针代替移动记录。但有些方法如快速排序法是无法实现表排序的，在这种情况下，可以进行“地址排序”，即另设一个向量指示需要记录，同时在排序过程中不移动记录而移动地址向量中相应分量的内容。