数据结构课件：14 第七章 排序新]

1数据结构国家精品课程2022/9/6第七章第七章 排排 序序2数据结构国家精品课程2022/9/6l从从数数学学和和计计算算机机角角度度而而言言，简简单单地地说说排排序序算算法法就就是是把把元元素素按按照照一一定定的的序序关关系系列列表表，最最常常见见的的序序关关系系是是数数字字序和字典序序和字典序。l高高效效的的排排序序算算法法有有助助于于提提高高其其他他算算法法的的效效率率，如如查查找找算算法法。此此外外，在在很很多多情情况况下下，排排序序有有助助于于规规范范化化数数据据和便于人类阅读、理解和便于人类阅读、理解。l尽尽管管排排序序问问题题本本身身相相对对于于其其他他计计算算理理论论问问题题而而言言并并不不复复杂杂，但但要要设设计计高高效效的的、有有针针对对性性的的排排序序算算法法也也并并非非易事，因此针对它的研究一直在持续开展。易事，因此针对它的研究一直在持续开展。冒冒泡泡排排序序的的研研究究最最早早出出现现于于1956年年，尽尽管管很很多多人人认认为为排排序序问问题题已已经经解解决决，但但新新的的排排序序算算法法持持续续不不断断地地被被提提出出，如如发发表表于于2004年年的的库库排排序序(Librarysort，又又称称缺缺口口插插入入排排序序，它是插入排序的新变形，时间复杂度它是插入排序的新变形，时间复杂度O(nlog2n).3数据结构国家精品课程2022/9/6第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序4数据结构国家精品课程2022/9/6l排排序序，也也叫叫分分类类，是是将将一一组组杂杂乱乱无无章章的的数数据据按按一一定定的的规规律律排列起来的过程。排列起来的过程。l文文件件，是是待待排排序序数数据据对对象象的的集集合合；一一个个数数据据对对象象也也叫叫作作一一个个记录，记录，记为记为R1，R2，Rnl关关键键词词域域(key):通通常常数数据据对对象象由由多多个个属属性性域域(多多个个数数据据成成员员)组组成成，其其中中可可将将一一个个属属性性域域作作为为排排序序依依据据，该该域域即即为为关关键键词词域域。每每个个文文件件用用哪哪个个属属性性域域作作为为关关键键词词，要要视视具具体体的的应应用用需需要要而而定定。即即使使是是同同一一个个文文件件表表，在在解解决决不不同同问问题题的的场场合也可能取不同的域做关键合也可能取不同的域做关键词词。l关键词记为关键词记为：K1，K2，Kn；l排序排序：将记录按关键词域递增或递减的顺序排列将记录按关键词域递增或递减的顺序排列7.1基本概念基本概念5数据结构国家精品课程2022/9/6l每每个个文文件件用用哪哪个个属属性性域域作作为为关关键键词词，要要视视具具体体的的应应用用需需要要而而定定；即即使使是是同同一一个个文文件件表表，在在解解决决不不同同问问题题的的场场合合也也可可能取不同的关键词域。能取不同的关键词域。l主主关关键键词词:如如果果在在数数据据表表中中各各个个对对象象的的关关键键词词互互不不相相同同，这这种种关关键键词词即即主主关关键键词词。按按照照主主关关键键词词排排序序，排排序序的的结结果果是唯一的。是唯一的。l次次关关键键词词:数数据据表表中中有有些些对对象象的的关关键键词词可可能能相相同同，这这种种关关键键词词称称为为次次关关键键词词。按按照照次次关关键键词词排排序序，排排序序的的结结果果可可能能不唯一。不唯一。6数据结构国家精品课程2022/9/6l排序的目标就是寻找一个置换排序的目标就是寻找一个置换使得诸关键词按照非递减的次序排列，即有使得诸关键词按照非递减的次序排列，即有l如如果果进进一一步步要要求求具具有有相相同同关关键键词词的的记记录录保保持持它它们们原原来来的的相相对对次次序序，即即要要求求：当当K(i)=K(j)并并且且ij时时，总总有有(i)0)AND(KiK)DO(Ri+1Ri.ii-1.)Ri+1R.)16数据结构国家精品课程2022/9/6算法算法InsertSortA(R,s,e)/引入虚拟记录引入虚拟记录,Ks-1minKi|sieISA1逐一排序逐一排序FORjs+1TOeDO(ij-1KKj.RRj.WHILEKKiDO(Ri+1Riii-1)Ri+1R)17数据结构国家精品课程2022/9/6FORjs+1TOeDO(ij-1KKj.RRj.WHILEKKiDO(Ri+1Riii-l)Ri+1R)k1k2k3k4k0k58 87 72 24 46 6j 224 46 67 788887 72 24 46 62 2 227 7 884 46 64 4 77 882 24 46 63 3 224 47 7 886 65 518数据结构国家精品课程2022/9/63.算法分析算法分析设设dj是是Rj左边关键词大于左边关键词大于Kj的记录个数，的记录个数，则则算法算法InsertSortA中关中关键词键词的比的比较较次数次数为为：记录的移动次数为记录的移动次数为19数据结构国家精品课程2022/9/6l最最好好情情况况下下，排排序序前前记记录录已已经经按按关关键键词词从从小小到到大大有有序序排排列列，即即dj=0。每每趟趟只只需需与与前前面面的的有有序序部部分分的的最最后后一一个个记记录录的的关关键键词词比比较较1次次，记记录录移移动动2次次，总总的的关关键键词词比比较较次次数数为为n-1，记记录录移移动动次次数数为为2(n-1)。20数据结构国家精品课程2022/9/6l最最坏坏情情况况下下：第第j趟趟时时，第第j个个记记录录前前面面所所有有记记录录的的关键词都比第关键词都比第j个记录的关键词大，即个记录的关键词大，即dj=j-1总的关键词比较次数：总的关键词比较次数：记录移动次数：记录移动次数：21数据结构国家精品课程2022/9/6平均情况平均情况下，下，考察分析考察分析的期望值。的期望值。l对对于于序序列列K1，K2，Kn，如如果果1ijn，且且KiKj，则则称称(Ki,Kj)为为上上述述序序列列的的一一个个反反序序对对。实实际际上上，正正好好是是序序列列K1，K2，Kn的的反反序序对对个数。个数。22数据结构国家精品课程2022/9/6对对于于关关键键词词K1，K2，Kn，设设K(1)，K(2)，K(n)是是排排序序结结果果。假假设设K(j)插插入入到到K(1)，K(2)，K(j1)每每个个位位置置的的概概率率相相等等，则则对对于于原原始始序序列列K1，K2，Kn：K(2)出现在出现在K(1)左边或右边的概率是左边或右边的概率是1/2；K(3)出出现现在在K(1)和和K(2)左左边边、中中间间和和右右边边的的概概率率是是1/3；K(n)出出现现在在K(1)，K(n1)中中间间的的任任何何位位置置的的概概率率均为均为1/n.23数据结构国家精品课程2022/9/6则有则有反序对的平均个数反序对的平均个数=0+(0+1)/2+(0+1+2)/3+(0+1+2+n1)/n=0+1/2+2/2+(n1)/n=n(n1)/4即即的期望值为的期望值为n(n1)/4.24数据结构国家精品课程2022/9/6平均情况平均情况下，若待排序文件中记录所有可能排列的下，若待排序文件中记录所有可能排列的概率相同，则可取上述最好情况和最坏情况的平均概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动情况。在平均情况下的关键词比较次数和记录移动次数分别为次数分别为因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为O(n2)。25数据结构国家精品课程2022/9/626数据结构国家精品课程2022/9/64.直接插入排序算法总结直接插入排序算法总结l优点优点:是算法的执行过程相当清晰，并且书写容易是算法的执行过程相当清晰，并且书写容易.l缺点缺点:期望复杂性为期望复杂性为O(n2).l稳定性：直接插入排序是稳定的排序方法。稳定性：直接插入排序是稳定的排序方法。l最好情况是：当被排序文件初态为正序时，算法的最好情况是：当被排序文件初态为正序时，算法的时间复杂度为时间复杂度为O(n).l辅助空间：辅助空间：O(1)27数据结构国家精品课程2022/9/65.直接插入排序算法是否可以进一步改进呢？直接插入排序算法是否可以进一步改进呢？l直接插入排序算法中包含了一个查找过程，对前部直接插入排序算法中包含了一个查找过程，对前部已经排序完的记录执行顺序查找。这显然是其效率已经排序完的记录执行顺序查找。这显然是其效率低下的原因之一，是否可以通过改进顺序查找来提低下的原因之一，是否可以通过改进顺序查找来提高排序效率呢高排序效率呢?28数据结构国家精品课程2022/9/6l通通过过将将顺顺序序查查找找改改为为二二分分查查找找，可可以以构构造造二二分分插插入入排排序序算算法法。即即在在插插入入第第j个个元元素素时时，不不是是像像直直接接插插入入排排序序那那样样顺顺序序寻寻找找插插入入的的位位置置，而而是是采采用用对对半半（或或二分）的方法插入。二分）的方法插入。l如如果果文文件件（R1，R2，Rn）采采用用顺顺序序存存储储，则则对对半半插插入入排排序序算算法法可可以以减减少少关关键键词词的的比比较较次次数数，但但是是记录的移动次数仍不能减少。记录的移动次数仍不能减少。l如如果果文文件件（R1，R2，Rn）采采用用链链接接存存储储，不不能能使用对半的方法寻找插入位置。使用对半的方法寻找插入位置。29数据结构国家精品课程2022/9/6l对对半半插插入入排排序序基基本本思思想想：设设在在顺顺序序表表中中有有一一个个记记录录序序列列R1,R2,Rn。其其中中，R1,R2,Ri-1是是已已经经排排好好序序的的记记录录集集合合。在在插插入入Ri时时，利利用用对对半半搜搜索索法法寻寻找找Ri的的插入位置。插入位置。30数据结构国家精品课程2022/9/6l对对半半插插入入排排序序就就平平均均性性能能来来说说比比直直接接插插入入排排序序要要快。快。l它它所所需需要要的的关关键键词词比比较较次次数数与与待待排排序序记记录录序序列列的的初初始始排排列列无无关关，仅仅依依赖赖于于记记录录个个数数。在在插插入入第第i 个个记记录录时时，需需要要经经过过 log2i+1次次关关键键词词比比较较，才能确定它应插入的位置。才能确定它应插入的位置。31数据结构国家精品课程2022/9/6l当当n 较较大大时时，总总关关键键词词比比较较次次数数比比直直接接插插入入排排序序的的最坏情况要好得多，但比其最好情况要差。最坏情况要好得多，但比其最好情况要差。l在在记记录录的的初初始始排排列列已已经经按按关关键键词词排排好好序序或或接接近近有有序序时时，直直接接插插入入排排序序比比对对半半插插入入排排序序执执行行的的关关键键词词比比较较次次数数要要少少。对对半半插插入入排排序序的的记记录录移移动动次次数数与与直直接接插入排序相同，依赖于对象的初始排列。插入排序相同，依赖于对象的初始排列。l对半插入排序是一个稳定的排序方法。对半插入排序是一个稳定的排序方法。32数据结构国家精品课程2022/9/6第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序直接插入排序直接插入排序希尔排序希尔排序7.3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序33数据结构国家精品课程2022/9/67.2.2希尔希尔(shell)排序排序1 1、希尔排序（渐减增量排序法）思想：、希尔排序（渐减增量排序法）思想：1959年年DonaldL.Shell提提出出Shell排排序序法法，源源自自对对直直接插入算法的改进接插入算法的改进.把把记记录录按按下下标标