排序1(数据结构PPT课件)(ppt文档).ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章,排序,排序,：,将一组杂乱无章的数据按一定的规律顺次排列起来。,文件,:,它是待排序数据对象的有限集合。,关键词域,(,key,),:,通常数据对象有多个,属性域,，即多个数据成员组成，其中有一个属性域可用来区分对象，作为排序依据。该域即为关键词域。每个文件用哪个属性域作为关键词，要视具体的应用需要而定。即使是同一个文件表，在解决不同问题的场合也可能取不同的域做关键码。,概 述,概 述,记录,：,R,1,，,R,2,，,，,R,n,关键,词,：,K,1,，,K,2,，,，,K,n,；,排序：,记录按关键词域递增或递减的顺序排列,主关键词,:,如果在数据表中各个对象的关键码互不相同，这种关键码即主关键码。按照主关键码进行排序，排序的结果是唯一的。,次关键词,:,数据表中有些对象的关键码可能相同，这种关键码称为次关键码。按照次关键码进行排序，排序的结果可能不唯一。,排序算法的稳定性,:,如果在对象序列中有两个对象,r,i,和,r,j,，它们的关键码,k,i,=,k,j,，且在排序之前，对象,r,i,排在,r,j,前面。如果在排序之后，对象,r,i,仍在对象,r,j,的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。,分类：,内排序,和,外排序,升序,和,降序,存储：,数组,和,链表,排序的时间开销,:,排序的时间开销是衡量算法好坏的最重要的标志。,排序的时间开销可用算法执行中,关键词的比较次数与数据的移动次数,来衡量,。,各节给出算法运行时间代价的大略估算,:,一般都,按平均情况,进行估算。对于那些,受对象关键词序列初始排列,及,对象个数影响较大的，需要,按最好情况和最坏情况,进行估算。,算法执行时所需的附加存储空间,:,评价算法好坏的另一标准。,9.1,插入排序,9.1.1,直接插入排序,直接插入排序思想：,将一个记录插入到已排好序的有序表中，从而,得到一个新的、记录数增一的有序表。,9 15 23 28 37,20,排序方法,:,第一步：,R1,；,第二步：,R1,R2,第三步：,R1,R2,R3,第,j,步：,R1,，,R2,，,，,Rj,1,Rj,；,第,n,步，,R1,，,R2,，,，,Rn,1,Rn,插入排序的算法,算法,InsertSort,(R,，,n),/*,本算法排列,n,个记录，使得它们相应的关键词排,列成一个非递减的序列,*,/,IS1,逐一排序,FOR j,2 TO n DO,(i,j1,/,每次循环,R,j,插入,到,R,1,，,，,R,j,1,中,K,K,j,.,R,R,j,.,WHILE i,0 AND K,K,i,DO,(R,i+1,R,i,iil),R,i+1,R),各趟排序结果,21,25,49,25*,16,08,1 2 3 4 5 6,1 2 3 4 5 6,temp,21,25,49,25*,16,08,25,j,=2,1 2 3 4 5 6,temp,21,25,49,25*,16,08,49,j,=3,21,25,49,25*,16,08,1 2 3 4 5 6,21,25,49,25*,16,08,j,=5,21,25,49,25*,16,08,j,=6,j,=4,25*,16,08,1 2 3 4 5 6,temp,1 2 3 4 5 6,temp,16,49,16,16,21,25,49,25*,16,08,21,25,49,25*,08,i,=4,时的排序过程,21,25,49,25*,完成,16,08,16,j,=5,i,=4,j,=5,i,=3,1 2 3 4 5 6,1 2 3 4 5 6,temp,1 2 3 4 5 6,temp,25,25*,16,16,21,25,49,25*,08,0 1 2 3 4 5,21,49,25*,08,21,25,49,25*,16,08,16,16,25,21,j,=5,i,=2,j,=5,i,=1,j,=5,i,=,0,16,1 2 3 4 5 6,temp,1 2 3 4 5 6,temp,改进后的插入排序算法,算法,InsertSortA,(R,，,s,e),ISA1,逐一排序,FOR j,s+1 TO e DO,(ij1,KK,j,.,RR,j,.,WHILE K,K,i,DO,(R,i+1,R,i,iil),R,i+1,R),插入排序演示,FOR j,s+1 TO e DO,(,ij1,KK,j,.,RR,j,.,WHILE K,K,i,DO,(R,i+1,R,i,iil),R,i+1,R,),k1,k2,k3,k4,k0,k5,8,7,2,4,6,j,2,4,6,7,8,8,7,2,4,6,2,2,7,8,4,6,4,7,8,2,4,6,3,2,4,7,8,6,5,插入算法分析：设,d,j,是,R,j,左边关键词大于,K,j,的记录个数，,则算法,InsertSortA,中关键词的比较次数为：,记录的移动次数为,最好情况,下，排序前记录已经按关键词从小到大有序排列，每趟只需与前面的有序部分的最后一个记录的关键词比较,1,次，记录移动,2,次，总的关键词比较次数为,n,-1,，记录移动次数为,2(,n,-1),。,最坏情况,下，第,i,趟时第,i,个记录前面的所有记录的关键词都比第,i,个记录的关键词大，即,d,j,取最大值，因此必须与前面,i-1,个记录都做关键词比较，并且每做,1,次比较就要做,1,次记录移动。则总的关键词比较次数为,记录移动次数为,平均情况,下，若待排序文件中记录所有可能的排列的概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动次数分别为,因此，直接插入排序的时间复杂度为,o(,n,2,),。,直接插入排序算法,优点,:,是算法的执行过程相当清晰，并,且书写容易,.,缺点,:,期望复杂性为,O(n,2,).,稳定性：,直接插入排序是,稳定的,排序方法。,最好情况是：,当被排序文件初态为正序时，算法的时间复杂度为,O(n).,辅助空间：,O(1),第七次上机练习题,1,、习题,7-5,2,、假定图,G=(V,E),用邻接矩阵的方式存储，请给出判断图是否存在回路的算法。,9.1.2,希尔排序,希尔排序（,渐减增量排序法）,思想：,把记录按下标的一定增量分组，对每组使用直接插入排序法，随着增量逐渐减少，所分成的组包含的关键词越来越多，到增量值减至,1,时，整个文件恰好被分成一个组，算法便告终止,.,希尔排序,增量的取法：,d,1,=5,n/2,10/2,d,2,=2,d,1,/2,5/2,d,3,=1,d,2,/2,2/2,例,将十个数进行希尔,排序的示例。,0 1 2 3 4 5 6 7 8 9,36 25 48 12 65,25,43 58 76 32,下标,d,1,=5,25,43,48,58,12,76,25,36,32,65,25,25,48 12 32 36 43 58 76 65,一趟,排序结果,例,将十个数进行希尔,排序的示例。,0 1 2 3 4 5 6 7 8 9,下标,d,2,=2,25,25,48 12 32 36 43 58 76 65,25,48,32,43,76,25,12,36,58,65,32,43,48,12,25,25,12 32 25 43 36 48 58 76 65,二趟,排序结果,12,25,25,32 36 43 48 58 65 76,三趟,排序结果,d,3,=1,渐减增量排序算法,算法分析,只对特定的待排序记录序列，可以准确地估算关键词的比较次数和对象移动次数。,想要弄清关键词比较次数和记录移动次数与增量选择之间的依赖关系，并给出完整的数学分析，至今仍然是数学难题。,Knuth,利用大量的实验统计资料得出，当,n,很大时，关键词平均比较次数和记录平均移动次数大约在,n,1.25,到,1.6,n,1.25,的范围内。这是在利用直接插入排序作为子序列排序方法的情况下得到的。,不稳定的排序算法,