《数据结构：第7章 排序》由会员分享，可在线阅读，更多相关《数据结构：第7章 排序（127页珍藏版）》请在金锄头文库上搜索。
1、1数据结构国家精品课程2024/7/27第七章第七章 排排 序序2数据结构国家精品课程2024/7/27l从从数数学学和和计计算算机机角角度度而而言言，简简单单地地说说排排序序算算法法就就是是把把元元素素按按照一定的序关系列表，最常见的序关系是照一定的序关系列表，最常见的序关系是数字序数字序和和字典序字典序。l高高效效的的排排序序算算法法有有助助于于提提高高其其他他算算法法的的效效率率，如如查查找找算算法法。此此外外，在在很很多多情情况况下下，排排序序有有助助于于规规范范化化数数据据和和便便于于人人类类阅阅读、理解读、理解。l尽尽管管排排序序问问题题本本身身相相对对于于其其他他计计算算理理论论
2、问问题题而而言言并并不不复复杂杂，但但要要设设计计高高效效的的、有有针针对对性性的的排排序序算算法法也也并并非非易易事事，因因此此针针对它的研究一直在持续开展。对它的研究一直在持续开展。3数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序4数据结构国家精品课程2024/7/27l排排序序，也也叫叫分分类类，是是将将一一组组杂杂乱乱无无章章的的数数据据按按一一定定的的规规律律排
3、列起来的过程。排列起来的过程。l文文件件，是是待待排排序序数数据据对对象象的的集集合合；一一个个数数据据对对象象也也叫叫作作一一个个记录，记录，记为记为R1，R2，Rnl关关键键词词域域(key):通通常常数数据据对对象象由由多多个个属属性性域域(多多个个数数据据成成员员)组组成成，其其中中可可将将一一个个属属性性域域作作为为排排序序依依据据，该该域域即即为为关关键键词域。词域。l关键词记为关键词记为：K1，K2，Kn；l排序排序：将记录按关键词域递增或递减的顺序排列将记录按关键词域递增或递减的顺序排列7.1基本概念基本概念5数据结构国家精品课程2024/7/27l每每个个文文件件用用哪哪个个
4、属属性性域域作作为为关关键键词词，要要视视具具体体的的应应用用需需要要而而定定；即即使使是是同同一一个个文文件件表表，在在解解决决不不同同问问题题的的场场合合也也可可能取不同的关键词域。能取不同的关键词域。l主主关关键键词词: : 如如果果在在数数据据表表中中各各个个对对象象的的关关键键词词互互不不相相同同，这这种种关关键键词词即即主主关关键键词词。按按照照主主关关键键词词排排序序，排排序序的的结结果果是唯一的。是唯一的。l次次关关键键词词: : 数数据据表表中中有有些些对对象象的的关关键键词词可可能能相相同同，这这种种关关键键词词称称为为次次关关键键词词。按按照照次次关关键键词词排排序序，排
5、排序序的的结结果果可可能能不唯一。不唯一。6数据结构国家精品课程2024/7/27排序算法的度量指标排序算法的度量指标:n排序的时间开销排序的时间开销( (排序算法的时间复杂性排序算法的时间复杂性) ): :是衡量算法好坏的是衡量算法好坏的最重要标志。可用算法执行中最重要标志。可用算法执行中关键词的比较次数关键词的比较次数与与数据的移动数据的移动次数次数来衡量。来衡量。n各算法的时间复杂性一般都各算法的时间复杂性一般都按平均情况按平均情况进行估算。对那些受对进行估算。对那些受对象初始排列及对象个数影响较大的，需要按象初始排列及对象个数影响较大的，需要按最好最好和和最坏最坏情况进情况进行估算。行
6、估算。n算法的空间复杂性算法的空间复杂性: :主要考察排序过程所需辅助存储空间的大主要考察排序过程所需辅助存储空间的大小。小。n排序算法的稳定性排序算法的稳定性: : 如果在对象序列中有两个对象如果在对象序列中有两个对象ri和和rj，它们的关键词它们的关键词ki=kj，且在排序之前对象，且在排序之前对象ri排在排在rj前面，如前面，如果在排序之后，对象果在排序之后，对象ri仍在对象仍在对象rj的前面，则称这个排序方的前面，则称这个排序方法是稳定的，否则称这个排序方法是不稳定的。法是稳定的，否则称这个排序方法是不稳定的。7数据结构国家精品课程2024/7/27l排排序序算算法法很很多多，在在解解
7、决决特特定定问问题题时时应应如如何何选选择择排排序序算法呢？算法呢？l首首先先应应该该从从算算法法的的时时间间代代价价和和空空间间代代价价出出发发考考虑虑（即即应应用用环环境境中中的的CPU处处理理能能力力、存存储储容容量量等等硬硬件件约约束束和和系系统统响响应应时时间间等等处处理理效效率率要要求求），有有些些情情况况下下也也需需要要考考虑虑算算法法实实现现的的复复杂杂程程度度（从从软软件件工工程程角角度度考考虑虑软软件件开开发发成成本本）。一一般般情情况况下下以以考考虑虑时时间间代代价为主。价为主。8数据结构国家精品课程2024/7/27l排序算法有多种分类方法排序算法有多种分类方法:从从元
8、元素素的的存存储储设设备备角角度度可可分分为为内内排排序序（在在内内存存中中进行）和进行）和外排序外排序（在外存储器上进行）。（在外存储器上进行）。按按对对关关键键词词的的操操作作可可分分为为基基于于关关键键词词比比较较的的排排序序算法和算法和分布排序算法分布排序算法。按按时时间间代代价价分分类类：平平方方阶阶排排序序算算法法，它它们们一一般般都都比比较较简简单单，特特点点是是容容易易实实现现，但但时时间间复复杂杂度度相相对对较较高高，最最坏坏情情况况下下时时间间复复杂杂度度一一般般为为O(n2)；线线性性对对数数阶阶算算法法，以以分分治治策策略略算算法法为为主主，最最坏坏情情况况下下时间复杂
9、度一般为时间复杂度一般为O(nlog(n).9数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序直接插入排序直接插入排序希尔排序希尔排序7.3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序10数据结构国家精品课程2024/7/277.2插入排序插入排序例：例：原有序表：原有序表：(915232837)20找插入位置找插入位置:(915232837)20新有序表新有序表:(91520232837)插入排序思想插入排序思想基于基于
10、插入插入操作所完成的排序。操作所完成的排序。插插入入:将将一一个个记记录录插插入入到到已已排排好好序序的的有有序序表表中中，从而得到一个新的记录数增一的有序表。从而得到一个新的记录数增一的有序表。11数据结构国家精品课程2024/7/277.2.1直接插入排序算法直接插入排序算法1.基本思想基本思想待排序记录待排序记录R1，R2，Rn1,Rn第一步：第一步：R1第二步：第二步：(R1),R2第三步：第三步：(R1,R2),R3第第j步：步：(R1，R2，Rj1),Rj第第n步步:(R1，R2，Rn1),Rn12数据结构国家精品课程2024/7/27例：例：j=5j=59 91515282823
11、2308081234561616161628281616232316161616一次插入过程一次插入过程16161616原有序表中关键词比原有序表中关键词比Rj大的记录数：大的记录数：dj比较次数：比较次数：dj+1 移动次数：移动次数： dj+228281616232313数据结构国家精品课程2024/7/272.算法描述算法描述算法算法InsertSort(R,n)FORj2TOnDO(/每次将每次将Rj插入到有序表插入到有序表R1，Rj1中中KKj.RRj.ij-1.WHILE(i0)AND(KiK)DO(Ri+1Ri.ii-1.)Ri+1R.) 14数据结构国家精品课程2024/7/2
12、7算法算法InsertSortA(R,s,e)/引入虚拟记录引入虚拟记录,Ks-1minKi|sieISA1逐一排序逐一排序FORjs+1TOeDO(ij-1KKj.RRj.WHILEKKiDO(Ri+1Riii-1)Ri+1R) 15数据结构国家精品课程2024/7/27FORjs+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
13、65 516数据结构国家精品课程2024/7/273.算法分析算法分析设设dj是是Rj左边关键词大于左边关键词大于Kj的记录个数，的记录个数，则则算法算法InsertSortA中关中关键词键词的比的比较较次数次数为为：记录的移动次数为记录的移动次数为17数据结构国家精品课程2024/7/27l最最好好情情况况下下，排排序序前前记记录录已已经经按按关关键键词词从从小小到到大大有有序序排排列列，即即dj=0。每每趟趟只只需需与与前前面面的的有有序序部部分分的的最最后后一一个个记记录录的的关关键键词词比比较较1次次，记记录录移移动动2次次，总总的的关关键键词词比比较较次次数数为为n-1，记记录录移移
14、动动次次数数为为2(n-1)。18数据结构国家精品课程2024/7/27l最最坏坏情情况况下下：第第i趟趟时时，第第i个个记记录录前前面面所所有有记记录录的的关键词都比第关键词都比第i个记录的关键词大，即个记录的关键词大，即dj=j-1总的关键词比较次数：总的关键词比较次数：记录移动次数：记录移动次数：19数据结构国家精品课程2024/7/27平均情况平均情况下，若待排序文件中记录所有可能排列的下，若待排序文件中记录所有可能排列的概率相同，则可取上述最好情况和最坏情况的平均概率相同，则可取上述最好情况和最坏情况的平均情况。在平均情况下的关键词比较次数和记录移动情况。在平均情况下的关键词比较次数
15、和记录移动次数分别为次数分别为因此，直接插入排序的时间复杂度为因此，直接插入排序的时间复杂度为O(n2)。20数据结构国家精品课程2024/7/27平均情况平均情况下，下，考察分析考察分析的期望值。的期望值。l对对于于序序列列K1，K2，Kn ，如如果果1ijn，且且KiKj，则则称称(Ki,Kj)为为上上述述序序列列的的一一个个反反序序对对。实实际际上上，正正好好是是序序列列K1，K2，Kn的的反反序序对对个数。个数。21数据结构国家精品课程2024/7/27则有则有反序对的平均个数反序对的平均个数=0+(0+1)/2+(0+1+2)/3+(0+1+2+n1)/n=0+1/2+2/2+(n1
16、)/2=n(n1)/4即即的期望值为的期望值为n(n1)/4.22数据结构国家精品课程2024/7/2723数据结构国家精品课程2024/7/274.直接插入排序算法总结直接插入排序算法总结l优点优点:是算法的执行过程相当清晰，并且书写容易是算法的执行过程相当清晰，并且书写容易.l缺点缺点:期望复杂性为期望复杂性为O(n2).l稳定性：直接插入排序是稳定的排序方法。稳定性：直接插入排序是稳定的排序方法。l最好情况是：当被排序文件初态为正序时，算法的最好情况是：当被排序文件初态为正序时，算法的时间复杂度为时间复杂度为O(n).l辅助空间：辅助空间：O(1)24数据结构国家精品课程2024/7/2
17、75.直接插入排序算法是否可以进一步改进呢？直接插入排序算法是否可以进一步改进呢？l直接插入排序算法中包含了一个查找过程，对前部直接插入排序算法中包含了一个查找过程，对前部已经排序完的记录执行顺序查找。这显然是其效率已经排序完的记录执行顺序查找。这显然是其效率低下的原因之一，是否可以通过改进顺序查找来提低下的原因之一，是否可以通过改进顺序查找来提高排序效率呢高排序效率呢?25数据结构国家精品课程2024/7/27l通通过过将将顺顺序序查查找找改改为为二二分分查查找找，可可以以构构造造二二分分插插入入排排序序算算法法。即即在在插插入入第第j个个元元素素时时，不不是是像像直直接接插插入入排排序序那
18、那样样顺顺序序寻寻找找插插入入的的位位置置，而而是是采采用用对对半半（或或二分）的方法插入。二分）的方法插入。l如如果果文文件件（R1，R2，Rn）采采用用顺顺序序存存储储，则则对对半半插插入入排排序序算算法法可可以以减减少少关关键键词词的的比比较较次次数数，但但是是记录的移动次数仍不能减少。记录的移动次数仍不能减少。l如如果果文文件件（R1，R2，Rn）采采用用链链接接存存储储，不不能能使用对半的方法寻找插入位置。使用对半的方法寻找插入位置。26数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序直接插入排序直接插入排序希尔排序希尔排序7.
19、3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序27数据结构国家精品课程2024/7/277.2.2希尔希尔(shell)排序排序1 1、希尔排序（渐减增量排序法）思想：、希尔排序（渐减增量排序法）思想：1959年年DonaldL.Shell提提出出Shell排排序序法法，源源自自对对直直接插入算法的改进接插入算法的改进.把把记记录录按按下下标标的的一一定定增增量量分分组组，对对每每组组使使用用直直接接插插入入排排序序算算法法排排序序；随随着着增增量量逐逐渐渐减减少少，每每组组包
20、包含含的的关关键键词词越越来来越越多多，当当增增量量减减至至1 1时时，整整个个文文件件恰恰被被分分成一组，算法便终止成一组，算法便终止。28数据结构国家精品课程2024/7/27例例将十个数进行希尔排序的示例。将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 936254812652525 43587632下标下标d1=525434858127625253632652525254812323643587665一趟一趟排序结果排序结果29数据结构国家精品课程2024/7/27例将十个数进行希尔排序的示例。 0 1 2 3 4 5 6 7 8
21、 90 1 2 3 4 5 6 7 8 9下标下标d d2 2=2=2 2525254812323643587665252548483232434376252512123636585865653243481225 2525123225433648587665二趟二趟排序结果排序结果 1225252532364348586576三趟三趟排序结果排序结果d d3 3=1=130数据结构国家精品课程2024/7/27 希尔排序希尔排序增量的取法：增量的取法：d d1 1= = =5= = =5n/2n/210/210/2d d2 2= = =2= = =2d d1 1/2/25/25/2d d3 3
22、= = =1= = =1d d2 2/2/22/22/231数据结构国家精品课程2024/7/272、算法分析、算法分析lShell算算法法的的性性能能与与所所选选取取的的分分组组长长度度序序列列有有很大关系。很大关系。l只只对对特特定定的的待待排排序序记记录录序序列列，可可以以准准确确地地估估算关键词的比较次数和对象移动次数。算关键词的比较次数和对象移动次数。l想想要要弄弄清清关关键键词词比比较较次次数数和和记记录录移移动动次次数数与与增增量量选选择择之之间间的的关关系系，并并给给出出完完整整的的数数学学分分析，至今仍然是数学难题。析，至今仍然是数学难题。32数据结构国家精品课程2024/7
23、/27lShell算算法法的的性性能能与与所所选选取取的的分分组组长长度度序序列列有有很很大大关关系。系。l前前面面介介绍绍的的实实例例是是最最简简单单的的分分组组长长度度序序列列，即即n/2i，最最坏坏情情况况下下时时间间复复杂杂度度为为O(n2).一一般般实实际际应应用用中中选选择择2.2作作为为递递减减因因子子效效果果更更好好，而而不不是是2.如如果果选选择择2k-1为分组长度序列，最坏情况下能达到为分组长度序列，最坏情况下能达到.33数据结构国家精品课程2024/7/27lV. Pratt于于1969年年证证明明如如下下结结论论：如如果果渐渐减减增增量量序序列列取取值值为为形形如如且且
24、小小于于n的的所所有有自自然然数数的的集集合合（即即），则则Shell算算法法的的时时间间复复杂杂度为度为.34数据结构国家精品课程2024/7/27lKnuth利利用用大大量量的的实实验验统统计计资资料料得得出出，当当n 很很大大时时，关关键键词词平平均均比比较较次次数数和和记记录录平平均均移移动动次次数数大大约约在在n1.25到到1.6n1.25的的范范围围内内。这这是是在在利利用用直直接接插插入入排排序序作作为为子子序序列列排排序序方方法法的的情况下得到的。情况下得到的。l不稳定的排序算法不稳定的排序算法35数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概
25、念7.2插入排序插入排序7.3交换排序交换排序冒泡排序冒泡排序快速排序快速排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序36数据结构国家精品课程2024/7/277.3交换排序交换排序l反反序序对对：对对于于序序列列K1,K2,Kn,若若1 iKj,则称则称(Ki,Kj)为上述序列的一个反序对。为上述序列的一个反序对。l交交换换排排序序的的思思想想：交交换换文文件件中中存存在在的的反反序序对对，直直到不存在反序对为止。到不存在反序对为止。l交交换换排排序序包包括括：冒冒泡泡排排序序、分分划划
26、交交换换排排序序（快快速速排序）。排序）。37数据结构国家精品课程2024/7/277.3.1冒泡排序冒泡排序 1、冒泡排序思想：、冒泡排序思想：通通过过比比较较相相邻邻记记录录的的关关键键词词，交交换换存存在在逆逆序序的的记记录录；使使关关键键词词较较大大的的记记录录如如气气泡泡一一般般逐逐渐渐往往上上“飘移飘移”直至浮出直至浮出“水面水面”。 38数据结构国家精品课程2024/7/27i =9=9090902021616080805051212123456789131314140707123456789090902021616080805051212131314140707i =8=812
27、345678909090202161608080505121213131414070739数据结构国家精品课程2024/7/272、冒泡排序算法、冒泡排序算法算法算法BSort(R，n)BS1冒泡过程冒泡过程FORi=nTO2STEP1DOFORj=1TOi1DOIFKjKj+1THEN(RjRj+1).n 关键词的比较次数关键词的比较次数: :(n-1)+(n-2)+1= =(n-1)n/240数据结构国家精品课程2024/7/27l经经过过一一趟趟冒冒泡泡，可可以以把把具具有有最最大大关关键键词词的的记记录录移移至至最后（第最后（第n个位置）。个位置）。l第第i趟趟冒冒泡泡，把把第第i大大
28、记记录录放放在在倒倒数数第第i(正正数数第第n-i+1)个位置上。个位置上。l做做n-1趟冒泡，就可以对所有记录排序。趟冒泡，就可以对所有记录排序。l发生一次记录交换，反序对的个数减少一个。发生一次记录交换，反序对的个数减少一个。l排排序序中中可可能能出出现现如如下下情情况况：每每趟趟比比较较中中，在在某某位位置置后，没有记录交换；最后几趟没有交换。后，没有记录交换；最后几趟没有交换。41数据结构国家精品课程2024/7/27i =9=90909020216160808050512121234567891313141407071234567890909020216160808050512121
29、31314140707i =8=812345678909090202161608080505121213131414070742数据结构国家精品课程2024/7/273、冒泡排序冒泡排序算法的改进算法的改进算法算法Bubble(R，n)Bubble1终止位置初始化终止位置初始化BOUNDn/每趟冒泡关键词比较的终止位置每趟冒泡关键词比较的终止位置Bubble2冒泡过程冒泡过程WHILEBOUND0DO(t0/每趟冒泡记录交换的最后位置每趟冒泡记录交换的最后位置FORj1TOBOUND 1DOIFKjKj+1THEN(RjRj+1.tj.)BOUNDt).43数据结构国家精品课程2024/7/2
30、74、算法分析、算法分析l最最好好情情形形：记记录录的的初初始始排排列列按按关关键键词词从从小小到到大大排排好好序序时时，此此算算法法只只执执行行一一趟趟起起泡泡，做做n-1次次关关键键词词比比较，不发生记录交换；较，不发生记录交换；l最最坏坏情情形形：算算法法执执行行了了n-1趟趟起起泡泡，第第i趟趟(1 i n)做做了了n-i 次次关关键键词词比比较较，执执行行了了n-i 次次记记录录交交换换,此此时时，总总的的关关键键词词比比较较次次数数和和记记录录交交换换次次数数为为(n-1)n/244数据结构国家精品课程2024/7/27l一般情形一般情形假假定定记记录录序序列列R1，R2，Rn所所
31、对对应应的的关关键键词词序序列列为为A=K1，K2，Kn令令bj（1 j n）表表示示A中中关关键键词词第第j小小的的记记录录左左边边大大于于它它的的关关键键词词的的个个数数，则则文文件件b1，b2，bn称称为为A的的反序表反序表.A=07,09,02,16,08,05,12,14,13B=2,4,0,2,0,1,2,1,045数据结构国家精品课程2024/7/27经过经过一趟冒泡后，一趟冒泡后，记录记录的位置的位置发发生生变变化，反序表也化，反序表也发发生生变变化。化。定定理理7.1设设K1，K2，Kn是是序序列列1，2，n的的一一个个排排列列，b1，b2，bn是是对对应应的的反反序序表表.
32、如如果果算算法法Bubble的的一一趟趟冒冒泡泡把把K1, K2, Kn改改变变为为K1,K2,Kn,那那么么从从b1,b2,bn中中把把每每个个非非零零元元素素减减1,就得到了相应的反序表就得到了相应的反序表b1,b2,bn.A=07,09,02,16,08,05,12,14,13A=07,09,02,16,08,05,12,14,13B=2,4,0,2,0,1,2,1,0B=2,4,0,2,0,1,2,1,0A=07,02,09,08,05,12,14,13,A=07,02,09,08,05,12,14,13,1616B=1,3,0,1,0,0,1,0,0B=1,3,0,1,0,0,1,0
33、,046数据结构国家精品课程2024/7/27证证明明：如如果果Kj（1 j n）的的左左边边有有大大于于Kj的的元元素素，设设Km=maxKt|1 tKj，则则由由算算法法Bubble知知，Rm一一定定会会与与Rj交交换换，且且Rj左左边边的的其其它它元元素不能与素不能与Rj交换。所以交换。所以如如果果Kj（1 j n）的的左左边边没没有有大大于于Kj的的元元素素，则则说说明明Rj左左边边的的所所有有元元素素都都小小于于Kj，从从而而一一趟趟冒冒泡泡之之后后，Rj左左边边的的任任何何元元素素都都不不与与Rj交交换换（因因为为它它们们都都小小于于Kj），所以仍然有），所以仍然有.证毕。证毕。4
34、7数据结构国家精品课程2024/7/27l推推论论7.1算算法法Bubble的的冒冒泡泡趟趟数数A=1+maxb1，b2，bn；记记录录交交换换次次数数B=nbi；关关键键词词的的比比较较次次数数C=ACi，其中其中Ci等于第等于第i趟冒泡时的趟冒泡时的BOUND减减1.lA、B、C分分布布较较为为复复杂杂，平平均均情情形形复复杂杂度度的的计计算算较较为为复复杂杂(略略)；48数据结构国家精品课程2024/7/27l改进的冒泡排序算法的复杂性：改进的冒泡排序算法的复杂性：49数据结构国家精品课程2024/7/275、冒泡排序算法总结冒泡排序算法总结l时间复杂度时间复杂度：O(n2)（包括最坏和
35、平均）包括最坏和平均）.l最好情况最好情况：当被排序文件初态为正序时，算法的时：当被排序文件初态为正序时，算法的时间复杂度为间复杂度为O(n).l稳定性稳定性：冒泡排序是：冒泡排序是稳定稳定的排序方法。的排序方法。l辅助存储空间辅助存储空间：O(1).l为了进一步提高效率，可采用为了进一步提高效率，可采用气泡上浮气泡上浮和和下沉下沉交替交替的方法。的方法。50数据结构国家精品课程2024/7/27第一趟第二趟第三趟第四趟79909090905679798888 9056887979488565656324323535273227323216271627278816351616353544451
36、数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序冒泡排序冒泡排序快速排序快速排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序52数据结构国家精品课程2024/7/277.3.2分划交换排序分划交换排序l1962年年，Hoare提提出出了了分分划划交交换换排排序序，也也叫叫快快速速排排序序(QuickSort)。l算法的出发点：算法的出发点：1、通过交换反序对排序，一次记录交换使得文件中、通过交换反序对排序，一次记录交
37、换使得文件中反序对的数目减少得最多反序对的数目减少得最多;2、一趟分划把一个记录、一趟分划把一个记录直接放在其最终的位置上直接放在其最终的位置上。53数据结构国家精品课程2024/7/271、快速排序的基本思想、快速排序的基本思想:l任任取取待待排排序序文文件件中中的的某某个个记记录录(例例如如取取第第一一个个记记录录)作作为为基基准准，按按照照该该记记录录的的关关键键词词大大小小，将将整整个个文文件件分分划划为为左左右右两两个子文件：个子文件：左左侧侧子子文文件件中中所所有有记记录录的的关关键键词词都都小小于于或或等等于于基基准准记记录录的关键词的关键词右右侧侧子子文文件件中中所所有有记记录
38、录的的关关键键词词都都大大于于基基准准记记录录的的关关键键词词基准记录排在两个子文件中间。基准记录排在两个子文件中间。l分分别别对对两两个个子子文文件件重重复复上上述述方方法法，直直到到所所有有记记录录都都排排在在相相应位置上为止。应位置上为止。54数据结构国家精品课程2024/7/272、快速排序算法描述、快速排序算法描述QuickSort(R)if(R的长度大于的长度大于1)将文件将文件R分划为两个子文件分划为两个子文件LeftR和和RightR;QuickSort(LeftR);QuickSort(RightR);将两个子文件将两个子文件LeftR和和RightR合并为合并为一个文件一个
39、文件R;55数据结构国家精品课程2024/7/27(1)(2)(3)(4)(5)(6)(7)(8)(9)7073692393181168100i(第一个大于第一个大于)(第一个小于第一个小于)j706869239318117310070686923111893731007068692311189373100186869231170937310056数据结构国家精品课程2024/7/27算法算法QSort(R,m,n)/Hoare快速排序的递归算法快速排序的递归算法QSort1递归出口递归出口/Rm为为基准基准记录记录，Rn+1关关键词键词最大最大IF(mn)THEN(im.jn+1.KKm.W
40、HILEijDO(ii+1WHILEKiKDOjj1.IFijTHENRiRj)RmRj.QSort(R,m,j1).QSort(R,j+1,n).)57数据结构国家精品课程2024/7/27(1) (2) (3) (4) (5) (6) (7) (8) (9)(1) (2) (3) (4) (5) (6) (7) (8) (9) 70707070 73 69 23 93 18 11 68 73 69 23 93 18 11 68 100100i=1i=1j=9j=9i=2i=2 70707070 68 68 69 23 93 18 11 69 23 93 18 11 73 10073 100
41、j=8j=8 70707070 68 68 6969 23 93 18 11 23 93 18 11 73 10073 100i=3i=3j=8j=8 70707070 68 68 69 69 2323 93 18 11 93 18 11 7373 100100i=4i=4j=8j=8 70707070 68 68 69 23 69 23 9393 18 11 18 11 73 10073 100i=5i=5j=8j=8 70707070 68 68 69 23 69 23 9393 18 18 1111 73 73 100100i=5i=5j=7j=7 70707070 68 68 69 2
42、3 69 23 1111 18 18 9393 73 73 100100i=5i=5j=7j=7 70707070 68 68 69 23 11 69 23 11 1818 93 73 93 73 100100i=7i=7j=6j=61818 68 68 69 23 11 69 23 11 70 70 70 70 93 73 100 93 73 100WHILEijDO(ii+1WHILEKiKDOjj1.IFijTHENRiRj)RmRj.快速排序一次快速排序一次分划过程示例分划过程示例: :58数据结构国家精品课程2024/7/27 18 68 18 68 69 23 1169 23 11
43、 70707070 93 7393 73 j=6j=6一一趟趟结果结果 11 1811 1811 1811 18 68 2368 23 69696969 70707070 73 93 73 93j=5j=5三趟三趟结果结果 11 18 23 68 69 70 73 9311 18 23 68 69 70 73 9311 18 23 68 69 70 73 9311 18 23 68 69 70 73 93 最终最终结果结果多趟快速排序过程示例多趟快速排序过程示例 11 18 11 18 11 18 11 18 2323 68 69 68 69 68 69 68 69 70707070 73 7
44、3 93939393四趟四趟结果结果j=4j=4 1111 18181818 69 23 6869 23 68 70707070 7373 93 93j=2j=2二趟二趟结果结果j=8j=859数据结构国家精品课程2024/7/27 18 68 18 68 69 23 1169 23 11 70707070 93 7393 73 j=6j=6 1111 18181818 69 23 6869 23 68 70707070 93 7393 73 j=2j=2 11 1811 1811 1811 18 68 23 68 23 6969 70707070 93 73 93 73j=5j=5 11 1
45、8 23 68 69 70 73 9311 18 23 68 69 70 73 9311 18 23 68 69 70 73 9311 18 23 68 69 70 73 93 最终最终结果结果 11 18 11 18 11 18 11 18 2323 6868 69696969 70707070 73 73 93939393j=8j=8j=4j=4算法算法QSort(R，m，n)IFmKnTHENRm+1Rn.IFKmKnTHENRmRn.IFKm+1KmTHENRm+1Rm.Part2分划开始分划开始imjn+1KKm.Part3用用Km分划文件分划文件(Rm，Rm+1，Rn)WHILEi
46、jDO(ii1WHILEKiKDOii1jj1WHILEKjKDOjj1.IFijTHENRiRj)RmRj67数据结构国家精品课程2024/7/274、快速排序算法总结、快速排序算法总结l时间复杂度时间复杂度:O(n2)/最坏最坏.l时间复杂度时间复杂度:O(nlog2n)/最好和平均最好和平均l辅助空间辅助空间：O(log2n).l稳定性稳定性：快速排序是：快速排序是不稳定不稳定的排序方法。的排序方法。l快快速速排排序序方方法法对对于于n 较较大大的的平平均均情情况况而而言言，是是目目前前内内部部排排序序中中最最好好、最最快快的的排排序序方方法法。但但当当n 很很小小时时，这这种种排排序序
47、方方法往往比其它简单排序方法还慢。法往往比其它简单排序方法还慢。68数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择排序直接选择排序直接选择排序堆排序堆排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序69数据结构国家精品课程2024/7/277.4选择排序选择排序l思思想想：对对待待排排序序的的文文件件进进行行n次次选选择择操操作作，其其中中第第i次次选选择择第第i小小(或或大大)的的记记录录放放在在第第i(或或n-i+
48、1，倒数第倒数第i)的位置上。的位置上。l 直接选择排序、堆排序直接选择排序、堆排序70数据结构国家精品课程2024/7/277.4.1直接选择排序直接选择排序 1 1、直接选择排序思想：、直接选择排序思想： 选择第选择第i（i =1,2,n- -1）大的记录的具体办法：大的记录的具体办法：在剩余的在剩余的n-i+1个记录中进行一趟比较，确定出第个记录中进行一趟比较，确定出第i大大记录记录，放在第，放在第n-i+1位置上。位置上。17786543438 173865434781738634547871数据结构国家精品课程2024/7/272 2、直接选择排序算法、直接选择排序算法算法算法SSo
49、rt(R,n)/待排序文件待排序文件(R1,R2,Rn)SS1排序排序FORj=nTO2STEP1DO(/从从1到到j找最找最大大元素的下标元素的下标tt1.FORi2TOjDOIFKtKiTHENtiRjRt)/将将Rt放到第放到第j个位置上个位置上72数据结构国家精品课程2024/7/27 (1) (2) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6)it 2121 25 25 49 25* 16 08 49 25* 16 08 2 1 2 1 初始初始序列序列2算法算法SSort（R，n）FORj=nTO2STEP-1DO(t1.FORi2TOnDOIFKt
50、KiTHENtiRiRt) 21 21 2525 4949 25* 16 08 25* 16 08 3 23 2 21 25 21 25 4949 25*25* 16 08 16 08 4 34 3 21 25 21 25 49 49 25* 25* 16 16 08 08 5 3 5 3 21 25 21 25 49 49 25* 16 25* 16 08 08 6 36 3 21 25 08 25* 1621 25 08 25* 16 4949 21212121 25 25 08 08 25* 16 25* 16 49494949 21 25 21 25 49 49 25* 16 25*
51、16 0808 一趟直接选择排序过程示例一趟直接选择排序过程示例73数据结构国家精品课程2024/7/27多趟直接选择排序过程示例多趟直接选择排序过程示例 (1) (2) (3) (4) (5) (6)(1) (2) (3) (4) (5) (6)i it t 1 1 21 21 25 25 08 08 25*25* 16 16 49 49 2 2 2 2 21 16 21 16 0808 25*25* 25 25 49 49 4 4 3 3 21 16 08 21 16 08 25*25* 25 49 25 49 1 1 5 5 08 08 16 16 2121 25* 2525* 25 4
52、949 21 21 25 25 49 49 25*25* 16 08 16 08 3 3 初始初始序列序列 4 4 08 16 08 16 2121 25* 25* 25 4925 49 2 2 74数据结构国家精品课程2024/7/273、算法分析、算法分析l直接选择排序的关键词比较次数与记录的初直接选择排序的关键词比较次数与记录的初始排列无关。假定整个待排序文件有始排列无关。假定整个待排序文件有n 个记个记录，则第录，则第i 趟选择所需的比较次数是趟选择所需的比较次数是n-i次。次。总的关键词比较次数总的关键词比较次数为为(n-1)+(n-2)+1=(n-1)n/2l记录记录交换次数交换次
53、数是选择的趟数是选择的趟数:n-1.75数据结构国家精品课程2024/7/274、直接选择排序算法总结、直接选择排序算法总结l时间复杂度时间复杂度:O(n2)（包括最好、最坏和平均）（包括最好、最坏和平均）.l稳定性：稳定性：不稳定不稳定的排序方法。的排序方法。l辅助空间：辅助空间：O(1). l优点：优点：简单、书写容易简单、书写容易76数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择排序直接选择排序直接选择排序堆排序堆排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排
54、序算法分析7.7分布排序分布排序7.8外排序外排序77数据结构国家精品课程2024/7/277.4.2堆排序堆排序1、堆排序的原理、堆排序的原理v选择排序的关键：找最大记录选择排序的关键：找最大记录v堆排序：利用堆排序：利用淘汰赛淘汰赛的方式寻找当前序列的方式寻找当前序列中的最大记录中的最大记录v淘淘汰汰赛赛的的思思想想：对对n个个选选手手，两两两两比比赛赛，得得到到 n/2 个个优优胜胜者者，作作为为第第一一轮轮的的结结果果；然然后后对对这这 n/2 个个选选手手，再再两两两两比比赛赛，如如此此重重复，直到选出一个冠军。复，直到选出一个冠军。78数据结构国家精品课程2024/7/272、堆的
55、定义、堆的定义 完完全全二二叉叉树树中中的的任任意意结结点点的的关关键键词词大大于于等等于于它它的的两两个个儿儿子子结结点点的的关关键键词词。我我们们把把这这样的数据结构称为样的数据结构称为堆堆( (极大堆极大堆) )。极大极大(大根大根)堆堆极小极小(小根小根)堆堆79数据结构国家精品课程2024/7/27949375918544511848581034例例12345678910111294937591854451184858103480数据结构国家精品课程2024/7/27堆的定义堆的定义完全二叉树的数组表示完全二叉树的数组表示Ki K2i&Ki K2i+1完全二叉树的数组表示完全二叉树的
56、数组表示Ki K2i&Ki K2i+181数据结构国家精品课程2024/7/273、堆排序算法、堆排序算法l设设数数组组R存存放放堆堆，则则R1是是关关键键词词最最大大的的记记录录，将将R1和和Rn互互换，使得换，使得最大记录放在最大记录放在Rn的位置。的位置。l调调整整R1，Rn-1，使使之之成成为为新新堆堆，则则R1是是其其中中最最大大者，再交换者，再交换R1与与Rn-1，使，使Rn-1中放入次最大记录中放入次最大记录。l再再对对R1，R2，Rn-2调调整整，使使之之成成为为新新堆堆，再再进进行行类类似似的的交交换换，上上述述操操作作反反复复进进行行，直直到到调调整整范范围围只只剩剩下下一
57、一个个记记录录R1为为止止。此此时时，R1是是n个个记记录录中中最最小小的的，且且数数组组Rn中中的的记录已经按从小到大排列了。记录已经按从小到大排列了。82数据结构国家精品课程2024/7/27n堆排序算法的粗略描述：堆排序算法的粗略描述：（l）建立包含）建立包含Kl，K2，Kn的堆；的堆；（2）FORinTO2STEP1DO（R1Ri重建包含重建包含K1，K2，Ki1的堆的堆）n需解决的两个问题：需解决的两个问题：如何建堆如何建堆如何调整新堆如何调整新堆83数据结构国家精品课程2024/7/27l问题问题重建堆：重建堆：R1与与Ri交换后，只有交换后，只有R1与其左与其左右儿子不满足堆的性
58、质。右儿子不满足堆的性质。1388422324160591428891232416051388422324160542889123241605881342232416054288912324160588134223241605428891232416058824422313160542889123241605882442231316059184数据结构国家精品课程2024/7/27l重建堆算法重建堆算法算法算法Restore(R，f，e)R1初始化初始化jfR2建堆建堆WHILEj e/2 DO/判断判断j是否为内结点是否为内结点(IF(2je)AND(K2jKjTHEN（RmRj.jm.）E
59、LSEje.）重建堆算法的时间复杂度为重建堆算法的时间复杂度为 O(log2n)85数据结构国家精品课程2024/7/27l问题问题初始建堆初始建堆:将以序号将以序号 n/2 ， n/2 1,1的结点为根的子树都调整为堆即可。的结点为根的子树都调整为堆即可。例例关键词序列（关键词序列（42,13,91,23,24,16,05,88)。421391232416058886数据结构国家精品课程2024/7/27l堆排序算法堆排序算法算法算法HeapSort(R，n)HS1初始建堆初始建堆FORi n2 TO1STEP1DORestore（R，i，n）HS2 排序排序 FORinTO2STEP1DO
60、(R1Ri.Restore(R，1，i1)87数据结构国家精品课程2024/7/27n堆排序堆排序过程过程关键字序列关键字序列关键字序列关键字序列(42,13,91,23,24,16,05,88)(42,13,91,23,24,16,05,88)42889123241605139188422324160513428891232416051388244223131605911、建立初始堆、建立初始堆2、交换，并重建、交换，并重建堆堆88数据结构国家精品课程2024/7/2742889123241605134224162313058891428891232416051324231605134288
61、91428891232416051323131605244288914288912324160513161305232442889189数据结构国家精品课程2024/7/27428891232416051313051623244288914288912324160513051316232442889190数据结构国家精品课程2024/7/274、堆排序算法总结、堆排序算法总结l时间复杂度时间复杂度:最好、最坏和平均情况相同最好、最坏和平均情况相同重建堆算法为重建堆算法为O(log2n)堆排序算法为堆排序算法为O(nlog2n).l稳定性：稳定性：堆排序是堆排序是不稳定不稳定的排序方法。的排序方
62、法。l辅助存储空间：辅助存储空间：O(1).91数据结构国家精品课程2024/7/274949252525*25*2121161608080123450808252525*25*16162121494902543149252125*160849252125*160808252125*1608252125*164949交换交换交换交换 0 0号与号与号与号与 5 5号对象号对象号对象号对象, ,5 5号对象就位号对象就位号对象就位号对象就位初始最大堆初始最大堆初始最大堆初始最大堆92数据结构国家精品课程2024/7/27252525*25*0808212116164949012345161625
63、*25*080825252121494902543125252525*210816*21081649491625*21081625*21082525 4949252525*25*0808212116164949012345161625*25*080825252121494902543125252525*210816*21081649491625*21081625*21082525 4949交换交换交换交换 0 0号与号与号与号与 4 4号对象号对象号对象号对象, ,4 4号对象就位号对象就位号对象就位号对象就位从从从从 0 0号到号到号到号到 4 4号号号号 重新重新重新重新调整为最大堆调整为
64、最大堆调整为最大堆调整为最大堆93数据结构国家精品课程2024/7/2725*25*161608082121252549490123450808161625*25*25252121494902543125*16210825*1621082525 494908162108162125*25* 2525 4949交换交换交换交换 0 0号与号与号与号与 3 3号对象号对象号对象号对象, ,3 3号对象就位号对象就位号对象就位号对象就位从从从从 0 0号到号到号到号到 3 3号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆94数据结构国家精品课程2024/7/2721211
65、61625*25*0808252549490123450808161625*25*25252121494902543121160821160825*25* 2525 4949081608162121 25*25* 2525 4949交换交换交换交换 0 0号与号与号与号与 2 2号对象号对象号对象号对象, ,2 2号对象就位号对象就位号对象就位号对象就位从从从从 0 0号到号到号到号到 2 2号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆95数据结构国家精品课程2024/7/27堆存在于顺序线性表（数组）中堆存在于顺序线性表（数组）中1616080825*25*21
66、21252549490123450808161625*25*252521214949025431160816082121 25*25* 2525 494908081616 2121 25*25* 2525 4949交换交换交换交换 0 0号与号与号与号与 1 1号对象号对象号对象号对象, ,1 1号对象就位号对象就位号对象就位号对象就位从从从从 0 0号到号到号到号到 1 1号号号号 重新重新重新重新调整为最大堆调整为最大堆调整为最大堆调整为最大堆96数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择
67、排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序97数据结构国家精品课程2024/7/277.5合并排序合并排序1、合并、合并l合合并并(归归并并)：把把两两个个或或多多个个有有序序文文件件合合并并成成一一个个单单一的有序文件。一的有序文件。l合合并并的的基基本本思思想想：设设两两个个有有序序表表A和和B的的记记录录个个数数(表表长长)分分别别为为al和和bl，变变量量i和和j分分别别是是表表A和和表表B的的当当前前检检测测指指针针。设设表表C是是归归并并后后的的新新有有序序表表，变量变量k是它的当前存放指针。是它
68、的当前存放指针。98数据结构国家精品课程2024/7/27l m m+l m m+1 1 n ni ji jl nl nk kC C当当i和和j都都在在两两个个表表的的表表长长内内变变化化时时，根根据据Ai与与Bj的的关关键键词词大小，依次把关键词小的对象排放到新表大小，依次把关键词小的对象排放到新表Ck中；中；当当i与与j 中中有有一一个个已已经经超超出出表表长长时时，将将另另一一个个表表中中的的剩剩余余部部分分照抄到新表照抄到新表Ck中。中。99数据结构国家精品课程2024/7/27合并算法描述：合并算法描述：算法算法Merge(R，t，m，n.X)M1初始化指针初始化指针itjm1k1M
69、2比较比较i和和j所指记录所指记录WHILE（im）AND（jn）DO（IFKiKjTHEN（XkRiii1.）ELSE（XkRjjj1.）kk+1.）M3复制余留记录复制余留记录WHILE(im)DO(XkRi.ii1.kk+1.)WHILE(jn)DO(XkRj.jj1.kk+1.)100数据结构国家精品课程2024/7/27lMerge算法分析：算法分析：关键词比较次数关键词比较次数n-t+1记录移动次数为记录移动次数为n-t+1101数据结构国家精品课程2024/7/272、合并排序、合并排序：l两路合并两路合并：一次合并两个文件：一次合并两个文件l合并排序合并排序：利用两路合并过程进
70、行排序。利用两路合并过程进行排序。基基本本思思想想：设设初初始始文文件件有有n个个记记录录，首首先先把把它它看看成成是是n个个长长度度为为1的的有有序序子子序序列列(合合并并项项)，先先做做两两两两合合并并，得得到到 n/2 个个长长度度为为2的的合合并并项项(如如果果n为为奇奇数数，则则最最后后一一个个有有序序子子序序列列的的长长度度为为1)；再再做做两两两两合合并并，如如此此重重复复，最最后后得得到到一一个个长长度度为为n的的有有序序列。序序列。102数据结构国家精品课程2024/7/27开始开始255748371292863325,5737,4812,9233,86第一次第一次合并合并2
71、5,37,48,5712,33,86,92第二次第二次合并合并12,25,33,37,48,57,86,92第三次第三次合并合并合并排序过程示例合并排序过程示例103数据结构国家精品课程2024/7/27l算算法法Merge(R,t,m,n.X)：合合并并算算法法，假假定定文文件件(Rt,Rt1,Rm)和和(Rm1,Rn)已已经经有有序序，合合并并这这两两个个文文件件，得得到到排序好的新文件排序好的新文件(Xt,Xt1,Xn)；l算算法法MPass(R,n,1engthX)：一一趟趟合合并并算算法法，将将文文件件R中中长长度度为为length的的所所有有子子文文件件两两两两合合并并到到文文件件
72、X中中，n是是R记记录录数，该函数中调用了数，该函数中调用了Merge()；l算算法法MSort(R，n)：合合并并排排序序算算法法，该该函函数数通通过过调调用用函函数数Mpass()，实现两路合并排序。实现两路合并排序。104数据结构国家精品课程2024/7/27一趟合并一趟合并MPass(R,n,1ength.X)的基本思想的基本思想l设设文文件件R中中的的n个个记记录录已已经经分分为为一一些些长长度度为为len的的子子文文件件，将将这这些些子子文文件件两两两两合合并并，合合并并成成一一些些长长度度为为2len的的子子文文件件，结结果果放放到到X中。中。l如如果果n不不是是2len的的整整
73、数数倍倍，则则一一趟趟合合并并到到最最后后，可可能能遇遇到到两两种种情形：情形：剩剩下下一一个个长长度度为为len的的子子文文件件和和另另一一个个长长度度不不足足len的的子子文文件件，可可用用一一次次merge算算法法，将将它它们们合合并并成成一一个个长长度度小小于于2len的的子子文件。文件。只只剩剩下下一一个个子子文文件件，其其长长度度小小于于或或等等于于len，可可将将它它直直接接抄抄到到X中。中。105数据结构国家精品课程2024/7/27一趟归并算法一趟归并算法算法算法MPass(R,n,1engthX)MP1初始化初始化i1MP2合并相邻的两个长度为合并相邻的两个长度为lengt
74、h的子文件的子文件WHILEin2*length+1DO(Merge(R,i,ilength-1,i2*length-1.X).ii2*length)MP3处理余留的长度小于处理余留的长度小于2*length的子文件的子文件IFi+length1nTHENMerge(R,i,i+length-1,n.X)ELSEFORj=iTOnDOXjRj106数据结构国家精品课程2024/7/27归并排序算法归并排序算法lenlen=1=1lenlen=2=2lenlen=4=4lenlen=8=8lenlen=16=16107数据结构国家精品课程2024/7/27两路合并排序算法两路合并排序算法算法算法
75、MSort(R,n)/X是辅助文件，其记录结构与是辅助文件，其记录结构与R相同相同MS1初始化初始化length1MS2交替合并交替合并WHILElengthnDO（MPass(R,n,length.X).length2*lengthMPass(X,n,length.R).length2*length）108数据结构国家精品课程2024/7/273、算法分析算法分析l一一趟趟两两路路合合并并MPass，要要调调用用Merge函函数数 n/(2*len) O(n/len)次次，而而Merge的的复复杂杂度度为为O(len).所所以以,MPass的复杂度为的复杂度为O(n).l合合并并排排序序算算
76、法法MSort，调调用用MPass正正好好 log2n 次次，所所以算法以算法总的时间复杂度为总的时间复杂度为O(nlog2n)。l辅助存储空间：辅助存储空间：O(n)l归并排序是归并排序是稳定稳定的排序方法。的排序方法。109数据结构国家精品课程2024/7/27通通过过实实例例仔仔细细分分析析合合并并排排序序算算法法，不不难难发发现现它它的的两个缺点：两个缺点：(1)当当数数据据集集非非常常小小时时，比比如如只只有有2个个元元素素，仍仍然然采采用分治策略，影响效率。用分治策略，影响效率。(2)Merge算算法法基基于于元元素素移移动动，当当元元素素比比较较大大时时会会比比较费时。较费时。针
77、对这两个问题的解决办法：针对这两个问题的解决办法：(1)对对于于非非常常小小的的数数据据集集，以以及及前前几几次次归归并并动动作作，调调用直接插入排序算法。用直接插入排序算法。(2)将将数数组组存存储储改改为为链链表表存存储储，这这样样记记录录移移动动就就变变为为指针移动了。指针移动了。110数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序111数据结构国家精品课程2024
78、/7/27 7.6.1各种内排序方法的比较各种内排序方法的比较 排序方法排序方法 最好时间最好时间 平均时间平均时间 最坏时间最坏时间稳定性稳定性辅助空间辅助空间直接选择直接选择O(n2)O(n2)O(n2)不稳定不稳定O(1)希尔希尔 O(n1.25) 不稳定不稳定O(1)直接插入直接插入O(n)O(n2)O(n2)稳定稳定O(1) 冒泡冒泡O(n)O(n2)O(n2)稳定稳定O(1)快速快速O(nlog2n)O(nlog2n)O(n2)不稳定不稳定O(log2n)堆堆O(nlog2n)O(nlog2n)O(nlog2n)不稳定不稳定O(1)归并归并O(nlog2n)O(nlog2n)O(n
79、log2n)稳定稳定O(n)112数据结构国家精品课程2024/7/27 7.6.2排序下界排序下界l下下界界：如如果果一一个个领领域域问问题题的的输输入入规规模模为为n，则则“该该领领域域问问题题的的算算法法的的时时间间复复杂杂性性下下界界为为L(n)”含含义义是是：不不存存在在解解该该领领域域问问题题的的算算法法，它它的的时时间间复复杂杂性性小小于于L(n).l排序下界排序下界: : O(nlog2n)l任任何何基基于于关关键键词词比比较较的的排排序序算算法法，其其关关键键词词比比较较次次数数至少至少为为nlog2n。113数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1
80、基本概念基本概念7.2插入排序插入排序7.3交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序114数据结构国家精品课程2024/7/277.7分布排序分布排序当当预预先先知知道道待待排排序序关关键键词词的的一一些些知知识识时时，比比如如其其分分布布范范围围，就就能能构构造造出出非非基基于于关关键键词词比比较较的的排排序序算算法，而且有些算法能在法，而且有些算法能在最坏情况下达到线性时间最坏情况下达到线性时间。如如扑扑克克牌牌的的排排序序、英英文文单单词词的的排排序序等等，可可采采用
81、用基基于关键词的数字性质的于关键词的数字性质的分分“桶桶”排序方法。排序方法。“桶桶”个个数数的的选选择择是是根根据据关关键键词词的的数数字字性性质质，而而且且“桶桶”的个数将直接影响排序算法的效率。的个数将直接影响排序算法的效率。两种分布排序：两种分布排序：基数分布基数分布和和值分布值分布。115数据结构国家精品课程2024/7/277.7.1基数分布基数分布n假假定定记记录录R1，R2，Rn相相应应的的关关键键词词K1，K2，Kn都都有有如如下下的的表表示示形形式式: Ki=(Ki,p，Ki,p1，Ki,1)，且且对于每个对于每个t(1tp)都有都有0Ki,tr，r为为基数基数.n基基数数
82、分分布布排排序序是是基基于于关关键键词词的的表表示示，按按其其字字典典序序由由小小到到大排列。其中，字典序规定如下：大排列。其中，字典序规定如下： Ki=(Ki,p，Ki,1)Kj=(Kj,p，Kj,1)当且仅当存在当且仅当存在tp，使得当，使得当st时时Ki,s=Kj,s 而而Ki,tKj,t116数据结构国家精品课程2024/7/27基数分布排序基数分布排序最高次序位法最高次序位法：先按高位分桶，然后桶内进行排序：先按高位分桶，然后桶内进行排序如：英文单词，扑克牌如：英文单词，扑克牌最最低低次次序序位位法法：首首先先按按最最低低位位排排序序，然然后后按按下下一一个个次低位排序，次低位排序，
83、最后按最高位排序，最后按最高位排序。117数据结构国家精品课程2024/7/271221630281016*20618按最低位分配按最低位分配r0r1r2r3r4r5r6r7r8r9f0f1f2f3f4f5f6f7f8f91221630281016*206183010201221616*62818r0r1r2r3r4r5r6r7r8r9f0f1f2f3f4f5f6f7f8f91816*1612102203062816*2826121016182030按次低位分配按次低位分配收集收集收集收集118数据结构国家精品课程2024/7/27算法算法RadixSort(Q,n,p,r)/最低次序位法的基
84、数排序算法最低次序位法的基数排序算法/Q为队列，为队列，P是关键词的位数，是关键词的位数，r为基数为基数RadixSort1.形成队列形成队列Q用用LINK域链接形成队列域链接形成队列QRadixSort2.关键词低位到高位分别按基数排序关键词低位到高位分别按基数排序FORj=1TOpDO(把队列把队列Q0,Q1,Qr1清空清空.WHILENOT(QEmpty(Q)DO(XQ.令令X=(Kp,Kp1,K1).QKjX).合并合并Q0,Q1,Qr1形成新的形成新的Q)119数据结构国家精品课程2024/7/277.7.2值分布值分布设设记记录录序序列列R1，R2，Rn，相相应应的的关关键键词词满
85、满足足uKiv且且Ki为为整整数数(1in)，则使用辅助数组，则使用辅助数组COUNTu:v就可得出如下的排序算法。就可得出如下的排序算法。算法算法D（R,n,u,v.S）/*分布计数排序算法分布计数排序算法*/D1FORi=uTOvDOCOUNTi0.D2FORj=1TOnDOCOUNTKjCOUNTKj+1.D3FORi=u+1TOvDOCOUNTiCOUNTi+COUNTi1./此时此时COUNTKj是关键词等于是关键词等于Kj的所有记录最终排序位置的最大序号的所有记录最终排序位置的最大序号D4FORj=nTO1STEP1DO(iCOUNTKj.SiRj.COUNTKji1)120数据结
86、构国家精品课程2024/7/27如如果果已已知知K1，K2，Kn在在区区间间（K0，Kn+1）上上的的分分布布是某种熟悉的分布，则可通过这种分布和区间来选择桶。是某种熟悉的分布，则可通过这种分布和区间来选择桶。例例如如，如如果果K1，K2，Kn在在（K0，Kn+1）上上呈呈均均匀匀分分布布 ， 则则 有有 b个个 桶桶 B1， B2， ， Bb， 且且 Bj的的 定定 义义 如如 下下（1jb）：则则给给定定Ki就就可可确确定定一一个个桶桶j，然然后后分分别别独独立立地地排排序序各各桶桶，最后把所有的桶合并在一起，形成排序文件。最后把所有的桶合并在一起，形成排序文件。121数据结构国家精品课程
87、2024/7/27按时间代价分类，按时间代价分类，内排序算法内排序算法大致分为三大类：大致分为三大类：简简单单排排序序算算法法，它它们们一一般般都都比比较较简简单单，容容易易实实现现，但但时时间间复复杂杂度度相相对对较较高高，即即最最坏坏情情况况下下时时间间复复杂杂度度均均为为O(n2)，也有一些改进的算法，如也有一些改进的算法，如Shell排序；排序；O(nlog2n)类类算算法法，以以分分治治策策略略算算法法为为主主，采采用用堆堆结结构构也也可可实实现现，在在以以比比较较运运算算为为时时间间复复杂杂度度衡衡量量基基准准的的前前提提下下，此此类类算算法法是是最最优优的的策策略略，其其平平均均
88、情情况况下下时时间间复复杂杂度度均均为为O(nlog2n)；线线性性时时间间算算法法，不不以以关关键键词词比比较较为为基基础础，有有较较低低的的时时间间代代价价(即即O(n)，但但是是需需要要对对数数据据集集有有一一定定先先验验知知识识，比比如如数据分布于哪个区间内等等。数据分布于哪个区间内等等。内排序小结内排序小结122数据结构国家精品课程2024/7/27在在讨讨论论的的内内排排序序方方法法中中，没没有有哪哪一一个个方方法法可可以以称称为为是是最最好好的的，一一些些方方法法对对较较小小的的n具具有有较较好好的的性性能能，而而另另一些方法对较大的一些方法对较大的n 性能较好。性能较好。当当输
89、输入入记记录录是是部部分分有有序序时时，插插入入排排序序比比较较合合适适，这这种种方法对于较小的方法对于较小的n值，是最好的排序方法。值，是最好的排序方法。合合并并排排序序具具有有最最好好的的最最坏坏情情况况性性能能，但但是是它它比比堆堆排排序序需需要要更更多多的的存存储储空空间间；快快速速排排序序具具有有最最好好的的平平均均性性能能，但但它它的的最最坏坏情情况况是是O(n2)；基基数数排排序序的的性性能能取取决决于于关关键词值的范围以及基数键词值的范围以及基数r的选择。的选择。123数据结构国家精品课程2024/7/27第七章第七章 排序排序7.1基本概念基本概念7.2插入排序插入排序7.3
90、交换排序交换排序7.4选择排序选择排序7.5合并排序合并排序7.6基于关键词比较的排序算法分析基于关键词比较的排序算法分析7.7分布排序分布排序7.8外排序外排序124数据结构国家精品课程2024/7/27本章需要复习的知识点n排序的基本概念排序的基本概念u 排序的基本概念排序的基本概念u 关键词、初始关键词排列关键词、初始关键词排列u 关键词比较次数、记录移动次数关键词比较次数、记录移动次数u 稳定性稳定性u 附加存储空间附加存储空间n插入排序插入排序u 用实例表明直接插入排序、折半插入排序和希尔排用实例表明直接插入排序、折半插入排序和希尔排序的过程序的过程u 直接插入排序和折半插入排序的算
91、法直接插入排序和折半插入排序的算法125数据结构国家精品课程2024/7/27u 排序的性能分析排序的性能分析 当当待待排排序序的的关关键键词词序序列列已已经经基基本本有有序序时时，用用直直接接插插入入排排序序最快最快 n交换排序交换排序u 用实例表明冒泡排序和快速排序的过程用实例表明冒泡排序和快速排序的过程u 冒泡排序冒泡排序和和快速排序的算法快速排序的算法 u 算法算法的性能分析的性能分析 快速排序是一个递归的排序法快速排序是一个递归的排序法 当当待待排排序序关关键键词词序序列列已已经经基基本本有有序序时时，快快速速排排序序显显著著变变慢。慢。126数据结构国家精品课程2024/7/27n
92、选择排序选择排序u 用实例表明直接选择排序、堆排序的过程用实例表明直接选择排序、堆排序的过程u 直接选择排序和堆排序的算法直接选择排序和堆排序的算法u 两种选择排序的性能分析两种选择排序的性能分析 选选择择排排序序在在一一个个待待排排序序区区间间中中选选出出最最大大的的数数据据时时，与与区区间间后后一一个数据对调，这导致方法不稳定。个数据对调，这导致方法不稳定。n二路合并排序二路合并排序u 用实例表明二路合并排序的过程用实例表明二路合并排序的过程u 二路合并排序的算法二路合并排序的算法u 该算法的性能分析该算法的性能分析 合并排序需要较多的附加存储。合并排序需要较多的附加存储。 合合并并排排序序对对待待排排序序关关键键词词的的初初始始排排列列不不敏敏感感，故故排排序序速速度度较较稳稳定。定。127数据结构国家精品课程2024/7/27课后作业课后作业l247页：页：7-2、7-5、7-18、7-24、7-49；l上机实验：上机实验：7-4、7-11
