数据结构第10章排序.ppt

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

1、电子工程学院电子工程学院电子工程学院电子工程学院第第10章章 内部排序内部排序12/25/20221电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录1 1 概述概述2 2 插入排序（直接插入排序、希尔排序）插入排序（直接插入排序、希尔排序）3 3直接选择排序直接选择排序4 4交换排序交换排序(起泡排序、起泡排序、快速排序快速排序）5 5归并排序归并排序6 6内部排序方法的比较内部排序方法的比较习题习题12/25/20222电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录1 1 概述概述n基本概念基本概念基本概念基本概念n定义：将文件中的数据记录按关键字值

2、的递增或递定义：将文件中的数据记录按关键字值的递增或递定义：将文件中的数据记录按关键字值的递增或递定义：将文件中的数据记录按关键字值的递增或递减的顺序排列起来。减的顺序排列起来。减的顺序排列起来。减的顺序排列起来。R R1,1,R R2,.,2,.,R Rn n R Ri1,i1,R Ri2,.,i2,.,R Rinin 其中关键字其中关键字其中关键字其中关键字 k k1,1,k k2,.,2,.,k kn n 有序序列有序序列有序序列有序序列 k ki1,i1,k ki2,.,i2,.,k kininn排序方法的稳定性：排序方法的稳定性：排序方法的稳定性：排序方法的稳定性：对于对于对于对于k

3、 ki ik kj j的记录的记录的记录的记录R Ri iR Rj j（R Ri i在在在在R Rj j之前）之前）之前）之前）,排序后：排序后：排序后：排序后：R Ri i仍在仍在仍在仍在R Rj j之前，则排序方法是稳定的；之前，则排序方法是稳定的；之前，则排序方法是稳定的；之前，则排序方法是稳定的；R Ri i在在在在R Rj j之后，之后，之后，之后，则排序方法是不稳定的；则排序方法是不稳定的；则排序方法是不稳定的；则排序方法是不稳定的；12/25/20223电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n n基本概念基本概念基本概念基本概念n n方法分类：方法分

4、类：方法分类：方法分类：u内部排序：在内存中进行，适于小文件内部排序：在内存中进行，适于小文件u外部排序：使用内存和外存，适于大文件，内存不够用外部排序：使用内存和外存，适于大文件，内存不够用内部排序内部排序内部排序内部排序：文件可有三种存储结构：文件可有三种存储结构：文件可有三种存储结构：文件可有三种存储结构(1)(1)一维数组：对记录的物理位置重排一维数组：对记录的物理位置重排一维数组：对记录的物理位置重排一维数组：对记录的物理位置重排(2)(2)链表：修改指针链表：修改指针链表：修改指针链表：修改指针(3)(3)索引表：对索引进行物理重排，记录位置不动（由于不方便索引表：对索引进行物理重

5、排，记录位置不动（由于不方便索引表：对索引进行物理重排，记录位置不动（由于不方便索引表：对索引进行物理重排，记录位置不动（由于不方便移动等原因）移动等原因）移动等原因）移动等原因）本章仅考虑：记录数组本章仅考虑：记录数组本章仅考虑：记录数组本章仅考虑：记录数组RnRn，关键字，关键字，关键字，关键字keykey为整数为整数为整数为整数n n标准：标准：标准：标准：执行时间执行时间执行时间执行时间(最重要的标志最重要的标志最重要的标志最重要的标志)，所需空间，算法复杂度，所需空间，算法复杂度，所需空间，算法复杂度，所需空间，算法复杂度 排序的时间代价主要指：算法中关键字的比较次数和记录的排序的时

6、间代价主要指：算法中关键字的比较次数和记录的 移动次数移动次数12/25/20224电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录以以记记录录数数组组作作为为文文件件的的存存储储结结构构，关关键键字字为为整整数数，文文件件类类型说明如下：型说明如下：typedefstruct/*定义记录为结构类型定义记录为结构类型*/intkey;/*关键字域关键字域*/datatypeother;/*记录的其他域记录的其他域*/rectype;rectypeRn;/*R为记录类型的数组为记录类型的数组*/其中：其中：n为文件的记录总数。为文件的记录总数。12/25/20225电子工程学

7、院电子工程学院电子工程学院电子工程学院上一页下一页回主目录2 2 插入排序插入排序将记录分为有序区和无序区，每次将无序区的第将记录分为有序区和无序区，每次将无序区的第一个记录插入到有序区的适当位置，使之保持有序。一个记录插入到有序区的适当位置，使之保持有序。2.1直接插入排序直接插入排序(最简单最简单)具体做法：具体做法：把把第第i个个记记录录Ri插插入入到到有有序序区区R1,R2,Ri-1;将将关关键键字字ki依依次次与与关关键键字字ki-1,ki-2,k1进进行行比比较较，从从而而找找到到应应该该插插入入的的位位置置，然后将然后将ki插入。插入。12/25/20226电子工程学院电子工程学

8、院电子工程学院电子工程学院上一页下一页回主目录假设假设R1Rn为待排序的记录区，下面给出算法描述：为待排序的记录区，下面给出算法描述：INSERTSORT(rectypeR)/对数组对数组R按递增序进行插入排序按递增序进行插入排序/R0是监视哨是监视哨*/inti,j;for(i=2;i=n;i+)/*依次插入依次插入R2,Rn*/R0=Ri;j=i 1;while(R0.keyRj.key)/*查找查找Ri的插入位置的插入位置*/Rj+1=Rj;j-;/将关键字大于将关键字大于Ri.key的记录后移的记录后移Rj+1=R0;/*插入插入Ri*/*INSERTSORT*/12/25/20227

9、电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录算法采用的是查找比较操作和记录移动操作交替进行的方法算法采用的是查找比较操作和记录移动操作交替进行的方法具体做法具体做法是：是：将待插入记录将待插入记录Ri的关键字依次与有序区中记录的关键字依次与有序区中记录Rj(j=i 1,i 2,1)的关键字进行比较，若的关键字进行比较，若Rj的关键字的关键字大于大于Ri的关键字，则将的关键字，则将Rj后移一个位置；若后移一个位置；若Rj的关键字的关键字小于或等于小于或等于Ri的关键字，则查找过程结束，的关键字，则查找过程结束，j+1即为即为Ri的的插入位置。因为关键字比插入位置。因为关键

10、字比Ri大的记录均已后移，故只要将大的记录均已后移，故只要将Ri插入该位置即可。插入该位置即可。附加记录附加记录R0，其作用有两个其作用有两个：1.进进入入查查找找循循环环之之前前，它它保保存存了了Ri的的副副本本，使使得得不不致致于于因因记记录的后移而丢失录的后移而丢失Ri中的内容；中的内容；2.在在while循循环环中中“监监视视”下下标标变变量量j是是否否越越界界，以以避避免免循循环环内内每每次次都都要要检检测测j是是否否越越界界。因因此此，我我们们将将R0称称为为“监监视视哨哨”，这使得测试循环条件的时间大约减少一半。，这使得测试循环条件的时间大约减少一半。12/25/20228电子工

11、程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录根根据据上上述述算算法法，我我们们用用一一例例子子来来说说明明直直接接插插入入排排序序的的过过程程。设设待待排排序序的的文文件件有有八八个个记记录录，其其关关键键字字分分别别为为47,33,61,82,72,11,25,47，直接插入排序过程如图，直接插入排序过程如图14.1所示。所示。12/25/20229电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录直接插入排序的算法分析直接插入排序的算法分析：整整个个排排序序过过程程只只有有两两种种运运算算，即即比比较较关关键键字字和和移移动动记记录录。外循环外循环：n

12、1趟插入排序；趟插入排序；内循环内循环：每一趟排序所需进行的关键字的比较和记录的后移。：每一趟排序所需进行的关键字的比较和记录的后移。文件正序时文件正序时：每趟排序的关键字比较次数为每趟排序的关键字比较次数为1，总的比较次数，总的比较次数Cmin=n 1；每趟记录移动次数是每趟记录移动次数是2次，总的移动次数次，总的移动次数Mmin=2(n 1)；文件逆序时文件逆序时：关键字的比较次数和记录移动次数均取最大值。：关键字的比较次数和记录移动次数均取最大值。每趟进行每趟进行i次比较次比较:与前与前i 1个记录及个记录及“监视哨监视哨”进行比较进行比较每每趟趟排排序序中中除除了了上上面面提提到到的的

13、两两次次移移动动外外，还还需需将将关关键键字字大大于于Ri的记录后移一个位置。的记录后移一个位置。因此，总的比较次数和记录的移动次数为因此，总的比较次数和记录的移动次数为:12/25/202210电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录在随机情况下在随机情况下:关键字各种排列出现的概率相同，则可取上述两种情况的关键字各种排列出现的概率相同，则可取上述两种情况的平均值作为比较和记录移动的平均次数，平均值作为比较和记录移动的平均次数，约为约为n2/4。由此，直由此，直接插入排序的时间复杂度为接插入排序的时间复杂度为O(n2)，空间复杂度为空间复杂度为O(1)。直接插入排

14、序是稳定的排序方法。直接插入排序是稳定的排序方法。12/25/202211电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录2.2希尔排序希尔排序希希尔尔排排序序（Shells method）又又称称为为“缩缩小小增增量量排排序序”（DiminishingIncrementSort）。）。基基本本思思想想：先先取取一一个个小小于于n的的整整数数d1并并作作为为第第一一个个增增量量，将将文文件件的的全全部部记记录录分分成成d1个个组组，所所有有距距离离为为d1倍倍数数的的记记录录放放在在同同一一个个组组中中，在在各各组组内内进进行行直直接接插插入入排排序序；然然后后取取第第二二

15、个个增增量量d2d1，重重 复复 上上 述述 的的 分分 组组 和和 排排 序序，直直 至至 所所 取取 的的 增增 量量dt=1(dtdt 1d2d1)为为止止，此此时时，所所有有的的记记录录放放在在同同一一组组中中进行直接插入排序。进行直接插入排序。12/25/202212电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录例例：设待排序文件共有：设待排序文件共有10个记录，其关键字分别为个记录，其关键字分别为47,33,61,82,71,11,25,47,57,02，增量序列取值依次为，增量序列取值依次为5,3,1。排序过程如下：。排序过程如下：12/25/202213电

16、子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录算法设计：如何设置监视哨？算法设计：如何设置监视哨？设设某某一一趟趟希希尔尔排排序序的的增增量量为为h，则则整整个个文文件件被被分分成成h组组：(R1,Rh+1,R2h+1,),(R2,Rh+2,R2h+2,),，(Rh,R2h,R3h,)，因因为为各各组组中中记记录录之之间间的的距距离离均均是是h，故故第第1组组至至第第h组的哨兵位置依次为组的哨兵位置依次为1 h,2 h,0。如如果果像像直直接接插插入入排排序序算算法法那那样样，将将待待插插入入记记录录Ri(h+1in)在在查查找找插插入入位位置置之之前前保保存存到到监监视视

17、哨哨中中，那那么么必必须须先先计计算算Ri属属于于哪哪一一组组，才才能能决决定定使使用用哪哪个个监监视视哨哨来来保保存存Ri。为为了了避避免免这这种种计计算算，我我们们可可以以将将Ri保保存存到到另另一一个个辅辅助助记记录录x中中，而而将将所所有有监监视视哨哨R1 h,R2 h,R0的的关关键键字字设设置置为为小小于于文文件件中中任任何何关关键键字字即即可可。因因为为增增量量是是变变化化的的，所所以以各各趟趟排排序序中中所所需需的的监监视视哨哨数数目目也也不不同同，但但是是我我们们可可以以按按最最大大增增量量d来来设设置置监监视视哨哨。具具体体算算法法描述如下：描述如下：12/25/20221

18、4电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录rectypeRn+d;/*R0Rd 1为为d个监视哨个监视哨，d=d0*/intdt;/*d0dt 1为增量序列为增量序列*/SHELLSORT(rectypeR,intd)inti,j,k,h;rectypetemp;intmaxint=32767;/*机器中的最大整数机器中的最大整数*/for(i=0;id0;i+)Ri.key=maxint;/*设置哨兵设置哨兵*/k=0;do h=dk;/*取本趟增量取本趟增量*/for(i=d+h;in+d;i+)/*Rh+dRn+d 1插入当前有序区插入当前有序区*/temp=

19、Ri;/*保存待插入记录保存待插入记录*/j=i h;while(temp.keyRj.key)/*查找正确的插入位置查找正确的插入位置*/Rj+h=Rj;/*后移记录后移记录*/j=j h;/*得到前一记录位置得到前一记录位置*/Rj+h=temp;/*插入插入Ri*/*本趟排序完成本趟排序完成*/k+;while(h!=1);/*增量为增量为1排序后终止算法排序后终止算法*/*SHELLSORT具具体体算算法法描描述述如如下下：12/25/202215电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录分析分析：实质是一种插入排序，比直接插入排序快，但不稳定；：实质是一种插

20、入排序，比直接插入排序快，但不稳定；主要特点主要特点：1.每每一一趟趟以以不不同同的的增增量量进进行行排排序序。例例如如第第一一趟趟增增量量为为5，第第二二趟趟增增量量为为3，第第三三趟趟增增量量为为1。在在前前两两趟趟的的插插入入排排序序中中，记记录录的的关关键键字字是是和和同同一一组组中中的的前前一一个个关关键键字字进进行行比比较较，由由于于此此时时增增量量取取值值较较大大，所所以以关关键键字字较较小小的的记记录录在在排排序序过过程程中中就就不不是是一一步一步地向前移动，而是作跳跃式的移动。步一步地向前移动，而是作跳跃式的移动。2.开开始始时时，增增量量取取值值较较大大，每每组组中中记记录

21、录较较少少，故故排排序序比比较较快快；随随后后，增增量量值值变变小小，每每组组中中记记录录变变多多，但但此此时时记记录录已已基基本本有有序序了了，因因次次在在进进行行最最后后一一趟趟增增量量为为1的的插插入入排排序序时时，只只需需作作少少量的比较和移动便可完成排序，从而提高了排序速度。量的比较和移动便可完成排序，从而提高了排序速度。如何选择增量序列？如何选择增量序列？希尔本人最初提出取希尔本人最初提出取d1=n/2，di+1=di/2，dt=1，t=log2n。后来又有人提出其他选择增量序列的方法，如后来又有人提出其他选择增量序列的方法，如di+1=(di 1)/3，dt=1，t=log3n

22、1 以及以及di+1=(di 1)/2，dt=1，t=log2n 1。12/25/202216电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录3 3 选择排序选择排序（Select Sort）基基本本思思想想：每每一一趟趟在在待待排排序序的的记记录录中中选选出出关关键键字字最最小小的的记记录录，依依次次放放在在已已排排序序的的记记录录序序列列的的最最后后，直直至至全全部部记记录录排排完完为为止。止。直接选择排序和堆排序都归属于此类排序。直接选择排序和堆排序都归属于此类排序。本节主要介绍直接选择排序本节主要介绍直接选择排序。12/25/202217电子工程学院电子工程学院电子

23、工程学院电子工程学院上一页下一页回主目录直接选择排序基本思想：直接选择排序基本思想：1.第第一一趟趟排排序序是是在在无无序序区区R0Rn 1中中选选出出最最小小的的记记录录，将它与将它与R0交换；交换；2.第第二二趟趟排排序序是是在在无无序序区区R1Rn 1中中选选关关键键字字最最小小的的记记录，将它与录，将它与R1交换；交换；3.第第i趟趟排排序序时时R0Ri 2已已是是有有序序区区，在在当当前前的的无无序序区区Ri 1Rn 1中中选选出出关关键键字字最最小小的的记记录录Rk，将将它它与与无无序序区区中中第第1个个记记录录Ri 1交交换换，使使R1Ri 1变变为为新新的的有有序区。序区。因因

24、为为每每趟趟排排序序都都使使有有序序区区中中增增加加了了一一个个记记录录，且且有有序序区区中中的的记记录录关关键键字字均均不不大大于于无无序序区区中中记记录录的的关关键键字字，所所以以，进进行行n 1趟趟排排序序后后，整整个个文文件件就就是是递递增增有有序序的的。其其排排序序过过程程如如图图14.3所示。所示。12/25/202218电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录直接选择排序过程直接选择排序过程12/25/202219电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录直接选择排序的算法如下：直接选择排序的算法如下：SELECTSORT(r

25、ectypeR)/对对R0Rn 1进进行行直直接接选选择择排排序序inti,j,k;rectypetemp;for(i=0;in 1;i+)/进行进行n 1趟选择排序趟选择排序k=i;for(j=i+1;jn;j+)/在当前无序区选关键字最小的记录在当前无序区选关键字最小的记录Rkif(Rj.keyRk.key)/稳定性稳定性kj），则则将将两两个个记记录录交交换换位位置置。这这样样的的操操作作反反复复进进行行，直直至至全全部部记记录录都都比比较较、交交换换完完为为止止。如如此此一一趟趟排排序序后后，就就将将关关键键字字最最小小的的记记录录安安排排在在第第一一个个记录的位置上。记录的位置上。2

26、.对对后后n 1个个记记录录重重复复同同样样操操作作，再再将将次次小小关关键键字字记记录录安安排排在在第二个记录的位置上。第二个记录的位置上。3.重复上述过程，直至没有记录需要交换为止。重复上述过程，直至没有记录需要交换为止。4.1 起泡排序起泡排序（Bubble method）12/25/202223电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录在在排排序序过过程程中中，关关键键字字小小的的记记录录像像气气泡泡一一样样逐逐趟趟向向上上飘飘，而大的记录则逐渐下沉，故形象的称为而大的记录则逐渐下沉，故形象的称为“起泡排序起泡排序”。12/25/202224电子工程学院电子工

27、程学院电子工程学院电子工程学院上一页下一页回主目录从上述排序过程中可看到：从上述排序过程中可看到：n对对任任一一组组记记录录进进行行起起泡泡排排序序时时，至至多多要要进进行行n 1趟趟排排序序过过程。程。n若若在在某某一一趟趟排排序序中中没没有有记记录录需需要要交交换换，则则说说明明待待排排序序记记录录已已按按关关键键字字有有序序，起起泡泡排排序序过过程程便便可可在在此此趟趟排排序序后后终终止止。例例如如在在图图14.4中中，第第四四趟趟排排序序过过程程中中已已没没有有记记录录需需要要交交换，说明此时整个文件已达到有序状态。换，说明此时整个文件已达到有序状态。为为此此，引引入入一一个个布布尔尔

28、量量noswap，在在每每趟趟排排序序之之前前，先先将将它它置置为为TRUE。在在一一趟趟排排序序结结束束时时，我我们们再再检检查查noswap，若若未未曾曾交换过记录便终止算法。交换过记录便终止算法。12/25/202225电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录具体算法如下：具体算法如下：BUBBLESORT(rectypeR)/*从下往上扫描的起泡排序从下往上扫描的起泡排序*/inti,j,nowsap;rectypetemp;for(i=0;ii;j-)/*从下往上扫描从下往上扫描*/if(Rj1.keyRj.key)/*交换记录交换记录*/temp=Rj1

29、;Rj1=Rj;Rj=temp;noswap=FALSE;if(noswap)break;/*本趟排序中未发生交换，则终止算法本趟排序中未发生交换，则终止算法/*BUBBLESORT*/12/25/202226电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录容易看出：容易看出：n若若文文件件按按关关键键字字递递增增有有序序，则则只只需需进进行行一一趟趟排排序序，比比较较次次数数为为n 1，记记录录移移动动次次数数为为0，即即比比较较次次数数和和记记录录移移动动次次数均为最小值；数均为最小值；n若若文文件件按按关关键键字字递递减减有有序序，则则需需进进行行n 1趟趟排排序序，

30、比比较较次数和记录移动次数均为最大值，分别为：次数和记录移动次数均为最大值，分别为：因此，起泡排序的时间复杂度为因此，起泡排序的时间复杂度为O(n2)。12/25/202227电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录上述起泡排序还可作如下改进：上述起泡排序还可作如下改进：(1)在在每每趟趟扫扫描描中中，记记住住最最后后一一次次交交换换发发生生的的位位置置k，因因为为该该位位置置之之前前的的记记录录都都已已排排序序，所所以以下下一一趟趟排排序序可可终终止止于于位位置置k，而不必进行到预定的下界而不必进行到预定的下界i。例如：例如：1，2，3，9，8，7。(2)上面提到

31、若文件初态为正序时只需进行一趟扫描，初上面提到若文件初态为正序时只需进行一趟扫描，初态为逆序时则需进行态为逆序时则需进行n 1趟扫描。趟扫描。实际上，如果只有最轻的气泡位于文件最末的位置，其实际上，如果只有最轻的气泡位于文件最末的位置，其余的记录均已排好序，那么也只需一趟扫描就可以完成排序。余的记录均已排好序，那么也只需一趟扫描就可以完成排序。例如对于初始关键字序列例如对于初始关键字序列6,9,12,14,19,22,35,2就仅需一趟就仅需一趟扫描。扫描。而当只有最重的气泡位于文件首记录的位置，其余的记而当只有最重的气泡位于文件首记录的位置，其余的记录均已排好序时，则仍需录均已排好序时，则仍

32、需n 1趟扫描才能完成排序。例如对趟扫描才能完成排序。例如对于初始关键字于初始关键字35,2,6,9,12,14,19,22就需七趟扫描。就需七趟扫描。12/25/202228电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录造成这种不对称性的原因是：造成这种不对称性的原因是：扫描方向扫描方向从从上上到到下下进进行行扫扫描描：最最重重的的气气泡泡“沉沉到到”该该区区的的底底部部，而而最最轻轻气泡只能气泡只能“上浮上浮”一个位置；一个位置；从从下下到到上上进进行行扫扫描描：最最重重的的气气泡泡“下下沉沉”一一个个位位置置，而而最最轻轻气气泡能泡能“浮到浮到”顶部；顶部；因因此此

33、，对对于于序序列列6,9,12,14,19,22,35,2就就必必须须从从上上到到下下扫扫描描七七趟趟才才能能完完成成排排序序，而而对对序序列列35,2,6,9,12,14,19,22只只需需从从上到下扫描一趟就可完成排序。上到下扫描一趟就可完成排序。为为了了改改变变上上述述两两种种情情况况下下的的不不对对称称性性，我我们们可可在在排排序序过过程程中交替改变扫描方向：中交替改变扫描方向：双向起泡排序双向起泡排序12/25/202229电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n n基本思想基本思想基本思想基本思想:任取待排序记录序列中的某个记录任取待排序记录序列中的某

34、个记录任取待排序记录序列中的某个记录任取待排序记录序列中的某个记录(例如取第一个例如取第一个例如取第一个例如取第一个记录记录记录记录)作为枢轴作为枢轴作为枢轴作为枢轴(pivot)(pivot)，以该记录的关键字作为基准，以该记录的关键字作为基准，以该记录的关键字作为基准，以该记录的关键字作为基准，将整个记录序列划分为左右两个子序列：将整个记录序列划分为左右两个子序列：将整个记录序列划分为左右两个子序列：将整个记录序列划分为左右两个子序列：uu 左侧子序列中所有记录的关键字都小于或等于枢轴左侧子序列中所有记录的关键字都小于或等于枢轴左侧子序列中所有记录的关键字都小于或等于枢轴左侧子序列中所有记

35、录的关键字都小于或等于枢轴记录的关键字记录的关键字记录的关键字记录的关键字uu 右侧子序列中所有记录的关键字都大于枢轴记录的右侧子序列中所有记录的关键字都大于枢轴记录的右侧子序列中所有记录的关键字都大于枢轴记录的右侧子序列中所有记录的关键字都大于枢轴记录的关键字关键字关键字关键字n n枢轴记录则排在这两个子序列中间枢轴记录则排在这两个子序列中间枢轴记录则排在这两个子序列中间枢轴记录则排在这两个子序列中间(这也是该记录最终这也是该记录最终这也是该记录最终这也是该记录最终应安放的位置应安放的位置应安放的位置应安放的位置)。n n然后分别对这两个子序列重复施行上述方法，直到所然后分别对这两个子序列重

36、复施行上述方法，直到所然后分别对这两个子序列重复施行上述方法，直到所然后分别对这两个子序列重复施行上述方法，直到所有的记录都按关键字有序排在相应位置上为止。有的记录都按关键字有序排在相应位置上为止。有的记录都按关键字有序排在相应位置上为止。有的记录都按关键字有序排在相应位置上为止。4.2 快速排序快速排序（Quick Sort）12/25/202230电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n快速排序算法快速排序算法快速排序算法快速排序算法采采采采 用用用用 快快快快 速速速速 排排排排 序序序序 方方方方 法法法法 对对对对 n n个个个个 记记记记 录录录录 排

37、排排排 序序序序，只只只只 须须须须 调调调调 用用用用QuickSort(R,1,n)QuickSort(R,1,n)，即即即即可可可可完完完完成成成成对对对对R1.nR1.n的的的的排排排排序序序序。快快快快速速速速排排排排序序序序算算算算法如下：法如下：法如下：法如下：voidvoidQUICKSORT(rectypeQUICKSORT(rectypeR,R,intints1,intt1);s1,intt1);/对对对对RsRs1 1 到到到到RtRt1 1 做快速排序做快速排序做快速排序做快速排序 intinti;i;if(s1t1)if(s1=temp.key)&(itemp.key

38、)&(itemp.key)&(itemp.key)&(ij)jj)jj)jj)j;if(iif(iif(iif(ij)j)j)j)RiRiRiRi+=+=+=+=RjRjRjRj;/交换交换交换交换RiRiRiRi 和和和和RjRjRjRj while(Ri.keywhile(Ri.keywhile(Ri.keywhile(Ri.key=temp.key)&(itemp.key)&(itemp.key)&(itemp.key)&(ij)i+;j)i+;j)i+;j)i+;/从左向右扫描，查找第一个关键字大于从左向右扫描，查找第一个关键字大于从左向右扫描，查找第一个关键字大于从左向右扫描，查找第

39、一个关键字大于temp.keytemp.keytemp.keytemp.key的记录的记录的记录的记录 if(iif(iif(iif(ij)j)j)j)RjRjRjRj=RiRiRiRi;/交换交换交换交换RiRiRiRi 和和和和RjRjRjRj while(iwhile(iwhile(iwhile(i!=j);!=j);!=j);!=j);RiRiRiRi=temp;=temp;=temp;=temp;/基准基准基准基准temptemptemptemp已被最后定位已被最后定位已被最后定位已被最后定位 return i;return i;return i;return i;12/25/202

40、232电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录第一次划分的过程第一次划分的过程电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录各趟排序之后的状态各趟排序之后的状态注意注意：对对 整整 个个 文文 件件 R0 Rn 1排排 序序，只只 需需 调调 用用QUICKSORT(R,0,n 1)即可。即可。电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录最坏情况：最坏情况：当当待待排排序序文文件件的的记记录录已已按按关关键键字字有有序序或或基基本本有有序序时时，情情况况反反而而恶恶化化了了，原原因因是是在在第第一一趟趟快快速速排排序序中

41、中，经经过过n 1次次比比较较之之后后，将将第第一一个个记记录录仍仍定定位位在在它它原原来来的的位位置置上上，并并得得到到一一个个包包括括n 1个个记记录录的的子子文文件件；第第二二次次递递归归调调用用，经经过过n 2次次比比较较，将将第第二二个个记记录录仍仍定定位位在在它它原原来来的的位位置置上上，从从而而得得到到一一个个包包括括n 2个个记记录录的的子子文文件件；依依次次类类推推，最最后后，得得到到总总比比较较次数为次数为这使快速排序蜕变为起泡排序，其时间复杂度为这使快速排序蜕变为起泡排序，其时间复杂度为O(n2)。改改进进方方法法：在在这这种种情情况况下下，通通常常采采用用“三三者者取取

42、中中”的的规规则则加加以以改改进进。即即在在进进行行一一趟趟快快速速排排序序之之前前，对对Rl.key、Rh.key和和R(l+h)/2.key进进行行比比较较，再再将将三三者者中中取取中中值值的的记记录录和和Rl交换，就可以改善快速排序在最坏情况下的性能。交换，就可以改善快速排序在最坏情况下的性能。12/25/202235电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录最好情况：最好情况：每每次次划划分分所所取取的的基基准准都都是是无无序序区区的的“中中值值”记记录录，划划分分的的结果是基准的左、右两个无序子区的长度大致相等。结果是基准的左、右两个无序子区的长度大致相等。

43、设设C(n)表表示示对对长长度度为为n的的文文件件进进行行快快速速排排序序所所需需的的比比较较次次数数，显显然然它它应应该该等等于于对对长长度度为为n的的无无序序区区进进行行划划分分所所需需的的比比较较次次数数n 1，加加上上递递归归地地对对划划分分所所得得的的左左、右右两两个个无无序序子子区区（长长度度n/2）进进行行快快速速排排序序所所需需的的比比较较次次数数。假假设设文文件件长长度度n=2k，那么总的比较次数为那么总的比较次数为C(n)n+2C(n/2)n+2n/2+2C(n/22)=2n+4C(n/22)2n+4n/4+2C(n/23)=3n+8C(n/23)kn+2kC(n/2k)=

44、n(log2n)+nC(1)=O(nlog2n)12/25/202236电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录一一般般来来说说，快快速速排排序序有有非非常常好好的的时时间间复复杂杂度度，它它优优于于各各种种排排序算法。可以证明，对序算法。可以证明，对n个记录进行快速排序个记录进行快速排序:最坏情况：最坏情况：待排序文件的记录已按关键字有序或基本有序时；待排序文件的记录已按关键字有序或基本有序时；最好情况最好情况：O(nlog2n);因因为为快快速速排排序序的的记记录录移移动动次次数数不不大大于于比比较较的的次次数数，所所以以，可以证明：可以证明：一般情况：一般情况

45、：平均时间复杂度也是平均时间复杂度也是O(nlog2n)，它它是是目目前前基基于于比比较较的的内内部部排排序序方方法法中中速度最快的，因而称为快速排序。速度最快的，因而称为快速排序。（不稳定）（不稳定）12/25/202237电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录5 5 归并排序归并排序（Merge Sort）n算法思想算法思想算法思想算法思想 假设初始表含有假设初始表含有假设初始表含有假设初始表含有n n n n个记录，则可看成是个记录，则可看成是个记录，则可看成是个记录，则可看成是n n n n个有序的子表，个有序的子表，个有序的子表，个有序的子表，每个子表的

46、长度为每个子表的长度为每个子表的长度为每个子表的长度为1 1 1 1，然后两两归并，得到，然后两两归并，得到，然后两两归并，得到，然后两两归并，得到 n/2n/2n/2n/2 个长度为个长度为个长度为个长度为2 2 2 2或或或或1 1 1 1的有序子表，再两两归并，的有序子表，再两两归并，的有序子表，再两两归并，的有序子表，再两两归并，,如此重复，直至得到一个如此重复，直至得到一个如此重复，直至得到一个如此重复，直至得到一个长度为长度为长度为长度为n n n n的有序子表为止。的有序子表为止。的有序子表为止。的有序子表为止。这种方法称为这种方法称为“二路归并排序二路归并排序”n归并的过程归并

47、的过程归并的过程归并的过程 将两个有序子表合并为一个有序子表的过程类似于玩扑将两个有序子表合并为一个有序子表的过程类似于玩扑将两个有序子表合并为一个有序子表的过程类似于玩扑将两个有序子表合并为一个有序子表的过程类似于玩扑克牌：假设桌上有两堆面朝上的牌，最小的排在上面，现要克牌：假设桌上有两堆面朝上的牌，最小的排在上面，现要克牌：假设桌上有两堆面朝上的牌，最小的排在上面，现要克牌：假设桌上有两堆面朝上的牌，最小的排在上面，现要将这两堆牌（看作输入）合并成一堆有序的牌（看作输出）。将这两堆牌（看作输入）合并成一堆有序的牌（看作输出）。将这两堆牌（看作输入）合并成一堆有序的牌（看作输出）。将这两堆牌

48、（看作输入）合并成一堆有序的牌（看作输出）。基本步骤是比较两输入堆顶上的两张牌，取出较小的那张牌基本步骤是比较两输入堆顶上的两张牌，取出较小的那张牌基本步骤是比较两输入堆顶上的两张牌，取出较小的那张牌基本步骤是比较两输入堆顶上的两张牌，取出较小的那张牌将它面朝下放到输出堆中。重复这一步骤，直至某一输入堆将它面朝下放到输出堆中。重复这一步骤，直至某一输入堆将它面朝下放到输出堆中。重复这一步骤，直至某一输入堆将它面朝下放到输出堆中。重复这一步骤，直至某一输入堆为空，这是将另一输入堆中剩余的牌面朝下全部放入到输出为空，这是将另一输入堆中剩余的牌面朝下全部放入到输出为空，这是将另一输入堆中剩余的牌面朝

49、下全部放入到输出为空，这是将另一输入堆中剩余的牌面朝下全部放入到输出堆中即可。如图所示：堆中即可。如图所示：堆中即可。如图所示：堆中即可。如图所示：12/25/202238电子工程学院电子工程学院电子工程学院电子工程学院上一页下一页回主目录n n设两个有序子表（相当于输入堆）放在同一向量中相设两个有序子表（相当于输入堆）放在同一向量中相设两个有序子表（相当于输入堆）放在同一向量中相设两个有序子表（相当于输入堆）放在同一向量中相邻的位置上：邻的位置上：邻的位置上：邻的位置上：Rlow.mid,Rmid+1.highRlow.mid,Rmid+1.highRlow.mid,Rmid+1.highR

50、low.mid,Rmid+1.high，先将它，先将它，先将它，先将它们合并到一个局部的暂存变量们合并到一个局部的暂存变量们合并到一个局部的暂存变量们合并到一个局部的暂存变量R1R1R1R1（相当于输出堆）中，（相当于输出堆）中，（相当于输出堆）中，（相当于输出堆）中，待合并完成后将待合并完成后将待合并完成后将待合并完成后将R1R1R1R1复制回复制回复制回复制回Rlow.highRlow.highRlow.highRlow.high 中。中。中。中。R Ri ji jlow highlow highk kR1R1low mid mid+low mid mid+1 1 high high说明：