第八章排序优秀PPT.ppt

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

1、第八章排序第一页，本课件共有105页第第8章章 排排 序序学习目的要求学习目的要求:1.掌握排序的概念和排序的种类。掌握排序的概念和排序的种类。2.熟练掌握五类基本排序熟练掌握五类基本排序:插入排序、交换排插入排序、交换排序、选择排序、归并排序和基数排序的算法序、选择排序、归并排序和基数排序的算法思想、算法实现和性能分析。思想、算法实现和性能分析。第二页，本课件共有105页8.1 概述概述8.2 插入排序插入排序8.3 交换排序交换排序8.4 选择排序选择排序8.5 归并排序归并排序8.6 基数排序基数排序8.7 各种排序方法的综合比较各种排序方法的综合比较第三页，本课件共有105页8.1 概

2、概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类第四页，本课件共有105页一、什么是排序？一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。的记录序列。例如：例如：将下列关键字序列将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为调整为14,23,36,49,52,58,61,75,80,97第五页，本课件共有105页【排序算法的稳定性】：【排序算法的稳定性】：

3、如果待排序的序列中，存在多个具有相同关键字如果待排序的序列中，存在多个具有相同关键字的记录，若经过排序这些记录的相对次序保持不变，的记录，若经过排序这些记录的相对次序保持不变，则称这种排序算法是则称这种排序算法是稳定稳定的；经过排序这些记录的相的；经过排序这些记录的相对次序发生了改变，则称这种排序算法是对次序发生了改变，则称这种排序算法是不稳定不稳定的。的。第七页，本课件共有105页例如：例如：排序前排序前(56,34,47,23,66,18,82,47)若排序后得到结果若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是则称该排序方法是稳定稳定的的;若排序后得

4、到结果若排序后得到结果 (18,23,34,47,47,56,66,82)则称该排序方法是则称该排序方法是不稳定不稳定的。的。第八页，本课件共有105页二、内部排序和外部排序二、内部排序和外部排序 待排序记录存放在计算机随机存储器中进行的待排序记录存放在计算机随机存储器中进行的排序过程，为排序过程，为内部排序；内部排序；若待排序记录的数量很大，以至内存一次不能容纳若待排序记录的数量很大，以至内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过全部记录，在排序过程中尚需对外存进行访问的排序过程，为程，为外部排序外部排序。第九页，本课件共有105页三、内部排序的方法三、内部排序的方法内

5、部排序的过程是一个逐步扩大记录内部排序的过程是一个逐步扩大记录的有序序列长度的过程。的有序序列长度的过程。经过一趟排序经过一趟排序有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区第十页，本课件共有105页在排序过程中的基本操作：在排序过程中的基本操作：比较两个关键字的大小比较两个关键字的大小将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置 前一种操作对大多数排序方法来说是必要的，前一种操作对大多数排序方法来说是必要的，而后一种操作可通过改变记录的存储方式来予以避而后一种操作可通过改变记录的存储方式来予以避免。免。第十二页，本课件共

6、有105页 8.2 插插 入入 排排 序序将无序子序列中的将无序子序列中的一个或几个记录一个或几个记录“插入插入”到有到有序序列中，从而增加记录的有序子序列的长度。序序列中，从而增加记录的有序子序列的长度。第十四页，本课件共有105页【一趟直接插入排序的基本思想】：【一趟直接插入排序的基本思想】：把把 n 个记录的序列划分为个记录的序列划分为已排序部分已排序部分和和未排序未排序部分部分，即在涉及第，即在涉及第 i 个记录个记录 Ri 时时,（R1,.,Ri-1）是）是已排好的有序部分，（已排好的有序部分，（Ri,Ri+1,.,Rn）属于未排）属于未排序部分。序部分。找出找出 Ri 在此有序序列

7、中应插入的位置，将在此有序序列中应插入的位置，将 Ri插入插入。原位置上的记录至。原位置上的记录至 Ri-1 均顺序后移一位。均顺序后移一位。第十五页，本课件共有105页有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n有序序列有序序列R1.i无序序列无序序列 Ri+1.n图示图示第十六页，本课件共有105页直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）第十七页，本课件共有105页一、直接插入排

8、序一、直接插入排序利用利用“顺序查找顺序查找”实现实现“在在R1.i-1中中查找查找Ri的插的插入位置入位置”对于直接插入排序：其对于直接插入排序：其时间复杂度时间复杂度为为O(n2 2)适用于当适用于当待排序记录的数量很小待排序记录的数量很小时时 第十八页，本课件共有105页【直接插入排序示例】【直接插入排序示例】初始状态初始状态 18 12 10 12 30 16 第第1趟（趟（i=2）(12)12 18 10 12 30 16 第第2趟（趟（i=3）(10)10 12 18 12 30 16 第第3趟（趟（i=4）(12)10 12 12 18 30 16 第第4趟（趟（i=5）(30)

9、10 12 12 18 30 16 第第5趟（趟（i=6）(16)10 12 12 16 18 30 待排序记录序列为待排序记录序列为(18(18，1212，1010，1212，3030，1616）直接插入排序每一趟执行后的序列状态直接插入排序每一趟执行后的序列状态:监视哨监视哨第十九页，本课件共有105页1已知序列已知序列72，83，99，65，10，36，7，9，请，请给出采用插入排序法对该序列作升序排序时的每一趟给出采用插入排序法对该序列作升序排序时的每一趟的结果。的结果。【练习】【练习】第二十页，本课件共有105页1已知序列已知序列72，83，99，65，10，36，7，9，请给，请给

10、出采用插入排序法对该序列作升序排序时的每一趟的结出采用插入排序法对该序列作升序排序时的每一趟的结果。果。初始：初始：（72），），83，99，65，10，36，7，9第第1趟：（趟：（72，83），），99，65，10，36，7，9第第2趟：（趟：（72，83，99），），65，10，36，7，9第第3趟：（趟：（65，72，83，99），），10，36，7，9第第4趟：（趟：（10，65，72，83，99），），36，7，9第第5趟：（趟：（10，36，65，72，83，99），），7，9第第6趟：（趟：（7，10，36，65，72，83，99），），9第第7趟：（趟：（7，9，10，36，

11、65，72，83，99）【练习答案】【练习答案】第二十一页，本课件共有105页 因为因为 R1.i-1 是一个按关键字有序的有序序列，则是一个按关键字有序的有序序列，则可以可以利用折半查找实现利用折半查找实现“在在R1.i-1中中查找查找Ri的的插插入位置入位置”，如此实现的插入排序为，如此实现的插入排序为折半插入折半插入排序。排序。二、折半插入排序二、折半插入排序第二十二页，本课件共有105页14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh例如例如:插入位置L.r【折半插入排序折半插入排序示例】示例】第二十三页，本课件共有105页 对于折半

12、插入排序对于折半插入排序，仅减少了关键字比较的次数，仅减少了关键字比较的次数，记录的移动次数不变，其记录的移动次数不变，其时间复杂度时间复杂度为为O(nO(n2 2)；折半插入排序适用于当折半插入排序适用于当待排序记录的数量很大待排序记录的数量很大时，时，可大幅度降低关键字的比较次数。可大幅度降低关键字的比较次数。第二十四页，本课件共有105页三三 2-路插入排序路插入排序2-路插入排序是对折半插入排序的改进算法，它是利路插入排序是对折半插入排序的改进算法，它是利用增加辅助空间来减少排序过程中移动记录的次数，即用增加辅助空间来减少排序过程中移动记录的次数，即“以空间换时间以空间换时间”。第二十

13、五页，本课件共有105页具体做法是具体做法是:建立一个和待排序序列建立一个和待排序序列rn同类型的数组同类型的数组dn作为辅助空间。作为辅助空间。先将先将r0的值赋给的值赋给d0，将，将d0看成是处于最后看成是处于最后有序序列中处于中间位置的记录，有序序列中处于中间位置的记录，再从再从r1开始依次将记录插入到开始依次将记录插入到d0之前或之后的有序之前或之后的有序序列中。序列中。将数组将数组d看成是一循环向量（既首尾相连的环状空间），看成是一循环向量（既首尾相连的环状空间），并设置两个指针并设置两个指针first和和final分别指向有序序列的第一条和最后分别指向有序序列的第一条和最后一条记录

14、，将当前待插入记录一条记录，将当前待插入记录ri与与d0比较，若比较，若rid0，则将其插入，则将其插入d0之前的有序序列中，反之，之前的有序序列中，反之，则将其插入到则将其插入到d0之后的有序序列中。之后的有序序列中。当所有的记录都插入完成后，从指针当所有的记录都插入完成后，从指针first所指向的记录所指向的记录开始一直读取到指针开始一直读取到指针final所指向的记录，所得到的序列就是所指向的记录，所得到的序列就是排序后的有序序列。排序后的有序序列。第二十六页，本课件共有105页三三 2-路插入排序路插入排序42 36 56 78 67 11 27 26i=142i=24236i=342

15、5636i=442567836i=54256677836i=6425667781136i=742566778112736i=84256677811273636firstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinal第二十七页，本课件共有105页 四、希尔排序四、希尔排序(缩小增量排序缩小增量排序)基本思想基本思想：对待排记录序列先作：对待排记录序列先作“宏观宏观”调整，再调整，再作作“微观微观”调整。调整。所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插入排的插入排序。序

16、。即先将整个待排记录序列分割成若干子序列分别即先将整个待排记录序列分割成若干子序列分别进行直接插入排序进行直接插入排序，待整个序列中的记录，待整个序列中的记录“基本有序基本有序”时，再对全体记录进行一次直接插入排序。时，再对全体记录进行一次直接插入排序。第二十八页，本课件共有105页 将记录序列分成若干子序列，分别对每个将记录序列分成若干子序列，分别对每个子序列进行插入排序。子序列进行插入排序。后面实例，后面实例，d d 称为增量，它的值在排序过程中称为增量，它的值在排序过程中从大到小从大到小逐渐缩小，直至最后一趟排序逐渐缩小，直至最后一趟排序减为减为 1 1。增量增量d d的取值的取值:d:

17、d0 0=n/2n/2,d,d1 1=d d0 0/2/2,d,di i=d di-1i-1/2/2(除后的结果除后的结果都都应应”下取整下取整”)”)具体做法具体做法：第二十九页，本课件共有105页例：初始关键字例：初始关键字 49 38 65 97 76 13 27 49 55 04 二趟排序结果二趟排序结果 04 27 13 49 38 55 49 65 97 76设增量设增量 d=5设增量设增量 d=2设增量设增量 d=1一趟排序结果一趟排序结果 13 27 49 55 04 49 38 65 97 76 三趟排序结果三趟排序结果 04 13 27 38 49 49 55 65 76

18、97 49 13 38 27 65 49 97 55 76 0413 49 04 38 97 27 55 49 65 76 第三十页，本课件共有105页例如：例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量第一趟希尔排序，设增量 d=511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量第二趟希尔排序，设增量 d=39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设增量第三趟希尔排序，设增量 d=1 9 11 12 16 18 23 25 30 31 36 47 第三十一页，本课件共有1

19、05页 从上述排序过程可见，希尔排序中子序列的构成不是简从上述排序过程可见，希尔排序中子序列的构成不是简单地单地“逐段分割逐段分割”，而是，而是将相隔某个将相隔某个“增量增量”的记录组成一的记录组成一个子序列个子序列。关键字较小的记录不是一步一步地往前挪动，而。关键字较小的记录不是一步一步地往前挪动，而是是“跳跃式跳跃式”地往前移，从而使得在进行最后一躺增量为地往前移，从而使得在进行最后一躺增量为1的插入排序时，序列已基本有序，只要作记录的少量比较和的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序。移动即可完成排序。因而因而希尔排序的时间复杂度比直接插入排序希尔排序的时间复

20、杂度比直接插入排序低低。它的时间是所取它的时间是所取“增量增量”序列的函数。序列的函数。第三十二页，本课件共有105页 已知序列（已知序列（10，16，4，3，6，12，1，9，15，8），请给出采用希尔排序法对该序列作升序排），请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。序时的每一趟的结果。练习练习第三十三页，本课件共有105页 已知序列（已知序列（10，16，4，3，6，12，1，9，15，8），请给出采用希尔排序法对该序列作升序排），请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。序时的每一趟的结果。初始：初始：10，16，4，3，6，12，1，9，15，8d=5第第

21、1趟：趟：10，1，4，3，6，12，16，9，15，8d=2第第2趟：趟：4，1，6，3，10，8，15，9，16，12d=1第第3趟：趟：1，3，4，6，8，9，10，12，15，16【练习答案】【练习答案】第三十四页，本课件共有105页8.3 选选 择择 排排 序序从记录的无序子序列中从记录的无序子序列中“选择选择”关键字最小或关键字最小或最大最大的记录，并将它的记录，并将它加入到有序子序列加入到有序子序列中，以此方中，以此方法增加记录的有序子序列的长度。法增加记录的有序子序列的长度。简简 单单 选选 择择 排排 序序堆堆 排排 序序第三十五页，本课件共有105页一、简单选择排序一、简单

22、选择排序【基本思想】【基本思想】：一趟简单选择排序的操作为：一趟简单选择排序的操作为：通过通过n-in-i次关键字间的比较，从次关键字间的比较，从n-i+1n-i+1个记录中选个记录中选出出关键字最小关键字最小的记录，并和第的记录，并和第i i（1in)1in)个记录交换个记录交换之。之。简单选择排序时间复杂度为简单选择排序时间复杂度为O(nO(n2 2)第三十六页，本课件共有105页假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列R1.i-1无序序列无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小

23、的记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n第三十七页，本课件共有105页【简单选择排序【简单选择排序】-选择最小的浮上来选择最小的浮上来初始状态初始状态 2 7 2 4 3 1 第第1趟（趟（i=1）1 7 2 4 3 2第第2趟（趟（i=2）1 2 7 4 3 2 第第3趟（趟（i=3）1 2 2 4 3 7第第4趟（趟（i=4）1 2 2 3 4 7 第第5趟（趟（i=5）1 2 2 3 4 7待排序记录序列的关键字序列为（待排序记录序列的关键字序列为（2 2，7 7，2 2，4 4，3 3，1 1）简单选择排序每一趟执行后的序列状态：简单选择排序每一趟执行后的序列状态：

24、第三十八页，本课件共有105页练习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用简单选择排序法对该序列作升序排列时的每一请给出采用简单选择排序法对该序列作升序排列时的每一趟的结果趟的结果第三十九页，本课件共有105页 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用简单选择排序法对该序列作升序排，请给出采用简单选择排序法对该序列作升序排列时的每一趟的结果列时的每一趟的结果初始：初始：17，18，55，40，7，32，73，65，89第第1趟：趟：7，18，55，40，17，32，73，65，89第第2趟：趟：7，17，55，4

25、0，18，32，73，65，89第第3趟：趟：7，17，18，40，55，32，73，65，89第第4趟：趟：7，17，18，32，55，40，73，65，89第第5趟：趟：7，17，18，32，40，55，73，65，89第第6趟：趟：7，17，18，32，40，55，73，65，89第第7趟：趟：7，17，18，32，40，55，65，73，89第第8趟：趟：7，17，18，32，40，55，65，73，89【练习答案】【练习答案】第四十页，本课件共有105页二、堆排序二、堆排序堆是满足下列性质的数列堆是满足下列性质的数列r1,r2,，rn：或或堆的定义堆的定义:(小顶堆小顶堆)(大顶堆大

26、顶堆)第四十一页，本课件共有105页3412362765498173554098是堆是堆14不不例如例如:12,36,27,65,40,34,98,81,73,55,4912,36,27,65,40,14,98,81,73,55,49第四十三页，本课件共有105页建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。从一个非终的过程。从一个非终端结点端结点n/2(下取整下取整)开始开始40554973816436122798例如例如:排序之前的关键字序列为排序之前的关键字序列为123681734998817355 现在，左现在，左/右子树都已经调整为堆，最后只要调整根结右子树都已经调

27、整为堆，最后只要调整根结点，使整个二叉树是个点，使整个二叉树是个“堆堆”即可。即可。9849406336122740,55,49,73,12,27,98,81,63,36第四十五页，本课件共有105页98814973556412362740例如例如:是大顶堆是大顶堆12但在但在 98 98 和和 12 12 进行互换之后，它就进行互换之后，它就不不是堆了，是堆了，因此，需要对它进行因此，需要对它进行“筛选筛选”。98128173641298比较比较比较第四十六页，本课件共有105页 已知序列已知序列50，8，51，6，90，17，89，27，65，46，以下给出采用堆排序法排序的全过程，以下给

28、出采用堆排序法排序的全过程【示例】【示例】(a.初始化初始化)466527891790651850第四十七页，本课件共有105页(b.建堆建堆)466527891790651850665895190890506550468第四十八页，本课件共有105页（c）交换）交换90和和8862751174650896590908第四十九页，本课件共有105页（d）筛选调整）筛选调整 627511746508965890898518第五十页，本课件共有105页（e）交换）交换89和和6908927817465051656第五十一页，本课件共有105页（f）筛选调整）筛选调整 681746275150659

29、089第五十二页，本课件共有105页g.交换交换65和和6817462751506659089第五十三页，本课件共有105页h.筛选调整筛选调整864627175051659089第五十四页，本课件共有105页(i).交换交换51和和8，输出，输出51 65908951第五十五页，本课件共有105页（j）筛选调整）筛选调整 65908951第五十六页，本课件共有105页（k）交换）交换50和和8，输出，输出50（l）筛选调整）筛选调整 65908951506590895150第五十七页，本课件共有105页（m）交换）交换46和和8，输出，输出46（n）筛选调整）筛选调整（o）交换）交换27和和

30、6，输出，输出27（p）筛选调整）筛选调整 第五十八页，本课件共有105页（q.）交换）交换17和和6，输出，输出17（r）筛选调整）筛选调整（s）交换）交换8和和6，输出，输出8 （t）输出）输出6第五十九页，本课件共有105页第六十页，本课件共有105页通过通过“交换交换”无序序列中的记录从而得到无序序列中的记录从而得到其中其中关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它加入到加入到有序子序列中有序子序列中，以此方法增加记录的有序子，以此方法增加记录的有序子序列的长度。序列的长度。8.4 交交 换换 排排 序序第六十一页，本课件共有105页 一、冒泡排序一、冒泡排序 二、快

31、速排序二、快速排序交交 换换 排排 序分类序分类第六十二页，本课件共有105页基本思想基本思想：比较比较相邻记录相邻记录，将，将关键字最大关键字最大的记录的记录交换到交换到 后面后面的位置上的位置上一、冒泡排序一、冒泡排序冒泡排序总的冒泡排序总的时间复杂度时间复杂度为为O(nO(n2 2)第六十三页，本课件共有105页假设在排序过程中，记录序列假设在排序过程中，记录序列R1.n的状态为：的状态为：第第 i 趟冒泡排序趟冒泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较比较相邻记录相邻记录，将，将

32、关键关键字最大字最大的记录的记录交换到交换到 n-i+1 的位置上的位置上第六十四页，本课件共有105页【冒泡排序示例】【冒泡排序示例】-相邻两数比较，大值下沉相邻两数比较，大值下沉初始状态初始状态 65 97 76 13 27 49 58 第第1趟趟 65 76 13 27 49 58 97第第2趟趟 65 13 27 49 58 76 97第第3趟趟 13 27 49 58 65 76 97第第4趟趟 13 27 49 58 65 76 97第第5趟趟 13 27 49 58 65 76 97第第6趟趟 13 27 49 58 65 76 97 设待排记录序列的关键字为设待排记录序列的关键

33、字为(65,97,76,13,27,49,58)(65,97,76,13,27,49,58)冒泡排序每一趟执行后的序列状态如下：冒泡排序每一趟执行后的序列状态如下：第六十五页，本课件共有105页练习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用冒泡排序法对该序列作升序排序的每一趟的结请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。果。第六十六页，本课件共有105页 已知序列已知序列17，18，55，40，7，32，73，65，89,请给出采用冒泡排序法对该序列作升序排序的每一趟的请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。结果。初始：初始：

34、17，18，55，40，7，32，73，65，89第第1趟：趟：17，18，40，7，32，55，65，73，89第第2趟：趟：17，18，7，32，40，55，65，73，89第第3趟：趟：17，7，18，32，40，55，65，73，89第第4趟：趟：7，17，18，32，40，55，65，73，89第第5趟：趟：7，17，18，32，40，55，65，73，89第第6趟：趟：7，17，18，32，40，55，65，73，89第第7趟：趟：7，17，18，32，40，55，65，73，89第第8趟：趟：7，17，18，32，40，55，65，73，89第第9趟：趟：7，17，18，32，4

35、0，55，65，73，89【练习答案】【练习答案】第六十七页，本课件共有105页 目标目标：找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，凡其，凡其关键字小于枢轴关键字小于枢轴的记录均的记录均移动至该记录之前，移动至该记录之前，反之，凡反之，凡关键字大于枢轴关键字大于枢轴的记录均的记录均移动至该记录之后移动至该记录之后。致使致使一趟排序一趟排序之后，记录的无序序列之后，记录的无序序列Rs.t将将分分割成两部分割成两部分：Rs.i-1和和Ri+1.t，且且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。一趟快速排序（一次划分）一趟快速排

36、序（一次划分）二、快速排序二、快速排序第六十八页，本课件共有105页stlowhigh设设 Rs=52 为枢轴为枢轴 将将 Rhigh.key 和和 枢轴的关键字进行比较，要求枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字枢轴的关键字,则不交换则不交换 将将 Rlow.key 和和 枢轴的关键字进行比较，要求枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字枢轴的关键字,则交换两数则交换两数high23lowhighlow例例R052lowhighhighhighlow【快速排序示例】【快速排序示例】528052145252第六十九页，本课件共有105页 可见，经过可见，经过

37、“一次划分一次划分”，将关键字序列，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为调整为:23,49,14,36,(52)58,61,97,80,75第七十页，本课件共有105页快速排序基本思想快速排序基本思想 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后，之后分别分别对分割所得两个子序列对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序 快速排序的时间复杂度为快速排序

38、的时间复杂度为O(nlogn)第七十一页，本课件共有105页第第1趟：趟：(23,49,14,36)52 (58,61,97,80,75)第第2趟：趟：(14)23(49,36)52 58(61,97,80,75)第第3趟：趟：14 23(36)49 52 58 61(97,80,75)第第4趟：趟：14 23 36 49 52 58 61(75,80)97第第5趟：趟：14 23 36 49 52 58 61 75(80)97第第6趟：趟：14 23 36 49 52 58 61 75 80 97第七十二页，本课件共有105页练习练习 已知序列已知序列17，18，55，40，7，32，73，

39、65，89，请给出采用快速排序法对该序列作升序排列时的每一趟的请给出采用快速排序法对该序列作升序排列时的每一趟的结果结果第七十三页，本课件共有105页已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用快速排序法对该序列作升序排列时的每一趟请给出采用快速排序法对该序列作升序排列时的每一趟的结果的结果初初 始始：17，18，55，40，7，32，73，65，89第第1趟趟：(7)，17，(55，40，18，32，73，65，89)第第2趟趟：7，17，(32，40，18)，55，(73，65，89)第第3趟趟：7，17，(18)，32，(40)，55，(65)，73，(

40、89)第第4趟趟：7，17，18，32，40，55，65，73，89【练习答案】【练习答案】第七十四页，本课件共有105页8.5 归归 并并 排排 序序 归并排序的过程基于下列归并排序的过程基于下列基本思想基本思想进行：进行：将两个或两个以上的将两个或两个以上的有序子序列有序子序列“归并归并”为一为一个有序序列。个有序序列。第七十五页，本课件共有105页在内部排序中，通常采用的是在内部排序中，通常采用的是2-路归并路归并排序。即：排序。即：将将两个位置相邻的记录两个位置相邻的记录有序子序列有序子序列归并为一个记录的有序序列归并为一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序

41、子序列 Rl.m有序子序列有序子序列 Rm+1.n第七十六页，本课件共有105页52,23,80,36,68,14 (s=1,t=6)80 36 52 23,52146836,80 14,23,36,52,68,80 23【2-2-路归并排序的过程】路归并排序的过程】14,68 23,36，52,80第第1趟：趟：第第2趟：趟：第第3趟：趟：14,68第七十八页，本课件共有105页 容易看出，对容易看出，对 n 个记录进行归并排序的时间个记录进行归并排序的时间复杂度为复杂度为(nlogn)。即：即：每一趟归并的时间复杂度为每一趟归并的时间复杂度为 O(n)，总共需进行总共需进行 log2n 趟

42、。趟。第七十九页，本课件共有105页练习练习 已知序列（已知序列（11，16，6，5，3，14，1，9）请给）请给出采用归并排序法对该序列作升序排列时的每一趟的出采用归并排序法对该序列作升序排列时的每一趟的结果结果第八十页，本课件共有105页 已知序列（已知序列（11，16，6，5，3，14，1，9）请给出）请给出采用归并排序法对该序列作升序排列时的每一趟的结果采用归并排序法对该序列作升序排列时的每一趟的结果【练习答案】【练习答案】初始：初始：11，16，6，5，3，14，1，9第第1趟：趟：11，165，63，141，9第第2趟：趟：5，6，11，161，3，9，14第第3趟：趟：1，3，5

43、，6，9，11，14，16第第3趟归并完毕，则排序结束趟归并完毕，则排序结束第八十一页，本课件共有105页 基数排序是一种借助基数排序是一种借助“多关键字排序多关键字排序”的思想来实的思想来实现现“单关键字排序单关键字排序”的内部排序算法。的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序8.6 基基 数数 排排 序序第八十二页，本课件共有105页例如，扑克牌中例如，扑克牌中52张牌面的次序关系为张牌面的次序关系为:2 3 A2 3 A 2 3 A 2 3 A 每一张牌有两个每一张牌有两个“关键字关键字”:花色（花色（）和面值（）和面值（23A），且），且“花色花色”的地位高

44、于的地位高于“面面值值”，在比较任意两张牌面的大小时，必须先比较，在比较任意两张牌面的大小时，必须先比较“花色花色”，若，若“花色花色”相同，则再比较面值。相同，则再比较面值。8.6 基基 数数 排排 序序第八十三页，本课件共有105页一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 R1,R2,，Rn，且每个记录，且每个记录Ri中含有中含有d个关键字个关键字(Ki0,Ki1,Kid-1)，则记录序列对，则记录序列对关键字关键字 (Ki0,Ki1,Kid-1)有序有序是指：是指：其中其中:K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关

45、键字位关键字 对于序列中任意两个记录对于序列中任意两个记录 Ri 和和 Rj (1ijn)都都满足满足下列下列(词典词典)有序有序关系：关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)22 3第八十四页，本课件共有105页 实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:最低位优先最低位优先LSD法法 (Least Significant Digit first)最高位优先最高位优先MSD法 (Most Significant Digit first)第八十五页，本课件共有105页 先对先对K0进行排序进行排序，并，并按按 K0 的不同值将记录序列的不同值将记录

46、序列分分成若干子序列成若干子序列，每个子序列中的记录都具有相同的，每个子序列中的记录都具有相同的K0值；值；然后，分别然后，分别就每个子序列对就每个子序列对 K1 进行排序进行排序，按按 K1值不同值不同将记录序列将记录序列分成若干更小的子序列分成若干更小的子序列；依次重复依次重复，直至对直至对最次位关键字最次位关键字Kd-1进行进行排序排序，最后，将所有，最后，将所有子序列依次子序列依次联接联接在一起成为一个有序序列在一起成为一个有序序列。【最高位优先【最高位优先MSD法】第八十六页，本课件共有105页 先对先对 Kd-1 进行排序进行排序，然后对然后对 Kd-2 进行排序，依进行排序，依次

47、类推，次类推，直至对最主位关键字直至对最主位关键字 K0 排序完成为止排序完成为止。【最低位优先【最低位优先LSD法】法】排序过程中不需要根据排序过程中不需要根据“前一个前一个”关键字的排关键字的排序结果，将记录序列分割成若干个序结果，将记录序列分割成若干个(“(“前一个前一个”关键关键字不同的字不同的)子序列。子序列。第八十七页，本课件共有105页例如例如:学生记录含三个关键字学生记录含三个关键字:系别系别、班号班号和和班内的序列号班内的序列号，其中以系别为最主位关键字。其中以系别为最主位关键字。无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,

48、202,3,182,1,201,2,152,3,183,1,202,1,203,2,303,1,202,1,201,2,153,2,302,3,18 1,2,152,1,202,3,183,1,203,2,30LSD的排序过程如下的排序过程如下:第八十八页，本课件共有105页 按按LSD法法进行排序时，不必分成若干子序列，对进行排序时，不必分成若干子序列，对每个关键字都是整个序列参加排序，但对每个关键字都是整个序列参加排序，但对Ki(0 i k-2)进行排序时，只能用进行排序时，只能用稳定稳定的排序方法；的排序方法；按按LSD法法进行排序时，也可以不通过关键字间的比进行排序时，也可以不通过关键

49、字间的比较来实现排序，而是通过若干次较来实现排序，而是通过若干次“分配分配”和和“收集收集”来来实现排序。实现排序。第八十九页，本课件共有105页二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范假如多关键字的记录序列中，每个关键字的取值范围相同，则按围相同，则按LSD法进行排序时，可以采用法进行排序时，可以采用“分配分配-收集收集”的方法，其好处是不需要进行关键字间的比较。的方法，其好处是不需要进行关键字间的比较。对于对于数字型数字型或或字符串型字符串型的的单关键字单关键字，可以，可以看成看成是由是由多个数位多个数位或或多个字符多个字符构成的构成的多关键字多关键字，

50、此时可以，此时可以采用采用这种这种“分配分配-收集收集”的办法的办法进行排序进行排序，称作称作基数排序法基数排序法。第九十页，本课件共有105页例如：对下列这组关键字例如：对下列这组关键字 209,386,768,185,247,606,230,834,539 首先按其首先按其“个位数个位数”取值分别为取值分别为 0,1,9 “分配分配”成成 10 组，之后按从组，之后按从 0 至至 9 的顺序将的顺序将 它们它们“收收集集”在一起；在一起；然后按其然后按其“十位数十位数”取值分别为取值分别为 0,1,9 “分配分配”成成 10 组，之后再按从组，之后再按从 0 至至 9 的顺序将它们的顺序将