第八章排序PPT讲稿.ppt

《第八章排序PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第八章排序PPT讲稿.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

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

2、第3页，共105页，编辑于2022年，星期三8.1 概概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类第4页，共105页，编辑于2022年，星期三一、什么是排序？一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将一组排序是计算机内经常进行的一种操作，其目的是将一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。的记录序列。例如：例如：将下列关键字序列将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为调整为14,23,36,49,52,58,61,75,80,9

3、7第5页，共105页，编辑于2022年，星期三【排序算法的稳定性】：【排序算法的稳定性】：如果待排序的序列中，存在多个具有相同关键字如果待排序的序列中，存在多个具有相同关键字的记录，若经过排序这些记录的相对次序保持不变，的记录，若经过排序这些记录的相对次序保持不变，则称这种排序算法是则称这种排序算法是稳定稳定的；经过排序这些记录的相的；经过排序这些记录的相对次序发生了改变，则称这种排序算法是对次序发生了改变，则称这种排序算法是不稳定不稳定的。的。第7页，共105页，编辑于2022年，星期三例如：例如：排序前排序前(56,34,47,23,66,18,82,47)若排序后得到结果若排序后得到结果

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

5、排序过程中尚需对外存进行访问的排序过程，为为外部排序外部排序。第9页，共105页，编辑于2022年，星期三三、内部排序的方法三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序内部排序的过程是一个逐步扩大记录的有序序列长度的过程。序列长度的过程。经过一趟排序经过一趟排序有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区第10页，共105页，编辑于2022年，星期三在排序过程中的基本操作：在排序过程中的基本操作：比较两个关键字的大小比较两个关键字的大小将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置 前一种操作对大多数排序方法来说

6、是必要的，而后一种前一种操作对大多数排序方法来说是必要的，而后一种操作可通过改变记录的存储方式来予以避免。操作可通过改变记录的存储方式来予以避免。第12页，共105页，编辑于2022年，星期三 8.2 插插 入入 排排 序序将无序子序列中的将无序子序列中的一个或几个记录一个或几个记录“插入插入”到到有序序列中，从而增加记录的有序子序列的长度。有序序列中，从而增加记录的有序子序列的长度。第14页，共105页，编辑于2022年，星期三【一趟直接插入排序的基本思想】：【一趟直接插入排序的基本思想】：把把 n 个记录的序列划分为个记录的序列划分为已排序部分已排序部分和和未排序部未排序部分分，即在涉及第

7、，即在涉及第 i 个记录个记录 Ri 时时,（R1,.,Ri-1）是已排）是已排好的有序部分，（好的有序部分，（Ri,Ri+1,.,Rn）属于未排序部分。）属于未排序部分。找出找出 Ri 在此有序序列中应插入的位置，将在此有序序列中应插入的位置，将 Ri插入插入。原位。原位置上的记录至置上的记录至 Ri-1 均顺序后移一位。均顺序后移一位。第15页，共105页，编辑于2022年，星期三有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n有序序列有序序列R1.i无序序列无序序列 Ri+1.n图示图示第16页，共105页，编辑于2022年，星期三直接插入排序直接插入排序（基于顺序查找）（基于

8、顺序查找）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）第17页，共105页，编辑于2022年，星期三一、直接插入排序一、直接插入排序利用利用“顺序查找顺序查找”实现实现“在在R1.i-1中中查找查找Ri的插的插入位置入位置”对于直接插入排序：其对于直接插入排序：其时间复杂度时间复杂度为为O(n2 2)适用于当适用于当待排序记录的数量很小待排序记录的数量很小时时 第18页，共105页，编辑于2022年，星期三【直接插入排序示例】【直接插入排序示例】初始状态初

9、始状态 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)10 12 12 18 30 16 第第5趟（趟（i=6）(16)10 12 12 16 18 30 待排序记录序列为待排序记录序列为(18(18，1212，1010，1212，3030，1616）直接插入排序每一趟执行后的序列状态直接插入排序每一趟执行后的序列状态:监视哨监视哨第19页，共105页，编辑于2022年，星期三1

10、已知序列已知序列72，83，99，65，10，36，7，9，请给出，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。采用插入排序法对该序列作升序排序时的每一趟的结果。【练习】【练习】第20页，共105页，编辑于2022年，星期三1已知序列已知序列72，83，99，65，10，36，7，9，请，请给出采用插入排序法对该序列作升序排序时的每一趟给出采用插入排序法对该序列作升序排序时的每一趟的结果。的结果。初始：初始：（72），），83，99，65，10，36，7，9第第1趟：（趟：（72，83），），99，65，10，36，7，9第第2趟：（趟：（72，83，99），），65，10，36，

11、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，65，72，83，99）【练习答案】【练习答案】第21页，共105页，编辑于2022年，星期三 因为因为 R1.i-1 是一个按关键字有序的有序序列，则可是一个按关键字有序的有序序列，则可以以利用折半查找实现利用折半查找实现“在在R1.i-1中中查找查找Ri的的插入位置插入位置”，如此实现的

12、插入排序为，如此实现的插入排序为折半插入折半插入排序。排序。二、折半插入排序二、折半插入排序第22页，共105页，编辑于2022年，星期三14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh例如例如:插入位置L.r【折半插入排序折半插入排序示例】示例】第23页，共105页，编辑于2022年，星期三 对于折半插入排序对于折半插入排序，仅减少了关键字比较的次数，仅减少了关键字比较的次数，记录的移动次数不变，其记录的移动次数不变，其时间复杂度时间复杂度为为O(nO(n2 2)；折半插入排序适用于当折半插入排序适用于当待排序记录的数量很大待排序记录的数量

13、很大时，时，可大幅度降低关键字的比较次数。可大幅度降低关键字的比较次数。第24页，共105页，编辑于2022年，星期三三三 2-路插入排序路插入排序2-路插入排序是对折半插入排序的改进算法，它是利用路插入排序是对折半插入排序的改进算法，它是利用增加辅助空间来减少排序过程中移动记录的次数，即增加辅助空间来减少排序过程中移动记录的次数，即“以空间以空间换时间换时间”。第25页，共105页，编辑于2022年，星期三具体做法是具体做法是:建立一个和待排序序列建立一个和待排序序列rn同类型的数组同类型的数组dn作为辅助空间。作为辅助空间。先将先将r0的值赋给的值赋给d0，将，将d0看成是处于最后有序序列

14、看成是处于最后有序序列中处于中间位置的记录，中处于中间位置的记录，再从再从r1开始依次将记录插入到开始依次将记录插入到d0之前或之后的有序序列中。之前或之后的有序序列中。将数组将数组d看成是一循环向量（既首尾相连的环状空间），并设置看成是一循环向量（既首尾相连的环状空间），并设置两个指针两个指针first和和final分别指向有序序列的第一条和最后一条记录，将分别指向有序序列的第一条和最后一条记录，将当前待插入记录当前待插入记录ri与与d0比较，若比较，若rid0，则将其插，则将其插入入d0之前的有序序列中，反之，则将其插入到之前的有序序列中，反之，则将其插入到d0之后的有之后的有序序列中。序

15、序列中。当所有的记录都插入完成后，从指针当所有的记录都插入完成后，从指针first所指向的记录开始一直读所指向的记录开始一直读取到指针取到指针final所指向的记录，所得到的序列就是排序后的有序序列。所指向的记录，所得到的序列就是排序后的有序序列。第26页，共105页，编辑于2022年，星期三三三 2-路插入排序路插入排序42 36 56 78 67 11 27 26i=142i=24236i=3425636i=442567836i=54256677836i=6425667781136i=742566778112736i=84256677811273636firstfinalfirstfina

16、lfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinal第27页，共105页，编辑于2022年，星期三 四、希尔排序四、希尔排序(缩小增量排序缩小增量排序)基本思想基本思想：对待排记录序列先作：对待排记录序列先作“宏观宏观”调整，再调整，再作作“微观微观”调整。调整。所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插入排序。的插入排序。即先将整个待排记录序列分割成若干子序列分别进行即先将整个待排记录序列分割成若干子序列分别进行直接插入排序直接插入排序，待整个序列中的记录，待整个序列中的记录“基本有序基本有序”时

17、，时，再对全体记录进行一次直接插入排序。再对全体记录进行一次直接插入排序。第28页，共105页，编辑于2022年，星期三 将记录序列分成若干子序列，分别对每个子将记录序列分成若干子序列，分别对每个子序列进行插入排序。序列进行插入排序。后面实例，后面实例，d d 称为增量，它的值在排序过程中称为增量，它的值在排序过程中从大到小从大到小逐渐缩小，直至最后一趟排序逐渐缩小，直至最后一趟排序减为减为 1 1。增量增量d d的取值的取值:d:d0 0=n/2n/2,d,d1 1=d d0 0/2/2,d,di i=d di-1i-1/2/2(除后的结果除后的结果都都应应”下取整下取整”)”)具体做法具体

18、做法：第29页，共105页，编辑于2022年，星期三例：初始关键字例：初始关键字 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 97 49 13 38 27 65 49 97 55 76 0413 49 04 38 97 27 55 49 65 76 第30页，共105页，编

19、辑于2022年，星期三例如：例如：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 第31页，共105页，编辑于2022年，星期三 从上述排序过程可见，希尔排序中子序列的构成不是从上述排序过程可见，希尔排序中子序列的构成不是简单地简单地“

20、逐段分割逐段分割”，而是，而是将相隔某个将相隔某个“增量增量”的记录组的记录组成一个子序列成一个子序列。关键字较小的记录不是一步一步地往前。关键字较小的记录不是一步一步地往前挪动，而是挪动，而是“跳跃式跳跃式”地往前移，从而使得在进行最后地往前移，从而使得在进行最后一躺增量为一躺增量为1的插入排序时，序列已基本有序，只要作的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序。记录的少量比较和移动即可完成排序。因而因而希尔排序的时间复杂度比直接插入排序希尔排序的时间复杂度比直接插入排序低低。它的。它的时间是所取时间是所取“增量增量”序列的函数。序列的函数。第32页，共105页，编

21、辑于2022年，星期三 已知序列（已知序列（10，16，4，3，6，12，1，9，15，8），请给出采用希尔排序法对该序列作升序排序时），请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。的每一趟的结果。练习练习第33页，共105页，编辑于2022年，星期三 已知序列（已知序列（10，16，4，3，6，12，1，9，15，8），请给出采用希尔排序法对该序列作升序排），请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。序时的每一趟的结果。初始：初始：10，16，4，3，6，12，1，9，15，8d=5第第1趟：趟：10，1，4，3，6，12，16，9，15，8d=2第第2趟：趟：4，

22、1，6，3，10，8，15，9，16，12d=1第第3趟：趟：1，3，4，6，8，9，10，12，15，16【练习答案】【练习答案】第34页，共105页，编辑于2022年，星期三8.3 选选 择择 排排 序序从记录的无序子序列中从记录的无序子序列中“选择选择”关键字最小或最大关键字最小或最大的记录，并将它的记录，并将它加入到有序子序列加入到有序子序列中，以此方法增加记中，以此方法增加记录的有序子序列的长度。录的有序子序列的长度。简简 单单 选选 择择 排排 序序堆堆 排排 序序第35页，共105页，编辑于2022年，星期三一、简单选择排序一、简单选择排序【基本思想】【基本思想】：一趟简单选择排

23、序的操作为：一趟简单选择排序的操作为：通过通过n-in-i次关键字间的比较，从次关键字间的比较，从n-i+1n-i+1个记录中选出个记录中选出关关键字最小键字最小的记录，并和第的记录，并和第i i（1in)1in)个记录交换之。个记录交换之。简单选择排序时间复杂度为简单选择排序时间复杂度为O(nO(n2 2)第36页，共105页，编辑于2022年，星期三假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列R1.i-1无序序列无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的记录有序序列有序序列R1.i无

24、序序列无序序列 Ri+1.n第37页，共105页，编辑于2022年，星期三【简单选择排序【简单选择排序】-选择最小的浮上来选择最小的浮上来初始状态初始状态 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）简单选择排序每一趟执行后的序列状态：简单选择排序每一趟执行后的序列状态：第38页，共10

25、5页，编辑于2022年，星期三练习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用简单选择排序法对该序列作升序排列时的每一趟请给出采用简单选择排序法对该序列作升序排列时的每一趟的结果的结果第39页，共105页，编辑于2022年，星期三 已知序列已知序列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，

26、17，55，40，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【练习答案】【练习答案】第40页，共105页，编辑于2022年，星期三二、堆排序二、堆排序堆是满足下列性质的数列堆是满足下列性质的数列r1,r2,，rn：或或堆的定义堆的

27、定义:(小顶堆小顶堆)(大顶堆大顶堆)第41页，共105页，编辑于2022年，星期三3412362765498173554098是堆是堆14不不例如例如:12,36,27,65,40,34,98,81,73,55,4912,36,27,65,40,14,98,81,73,55,49第43页，共105页，编辑于2022年，星期三建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。从一个非终端结的过程。从一个非终端结点点n/2(下取整下取整)开始开始40554973816436122798例如例如:排序之前的关键字序列为排序之前的关键字序列为123681734998817355 现在，

28、左现在，左/右子树都已经调整为堆，最后只要调整根结点，右子树都已经调整为堆，最后只要调整根结点，使整个二叉树是个使整个二叉树是个“堆堆”即可。即可。9849406336122740,55,49,73,12,27,98,81,63,36第45页，共105页，编辑于2022年，星期三98814973556412362740例如例如:是大顶堆是大顶堆12但在但在 98 98 和和 12 12 进行互换之后，它就进行互换之后，它就不不是堆了，是堆了，因此，需要对它进行因此，需要对它进行“筛选筛选”。98128173641298比较比较比较第46页，共105页，编辑于2022年，星期三 已知序列已知序列

29、50，8，51，6，90，17，89，27，65，46，以下给出采用堆排序法排序的全过程，以下给出采用堆排序法排序的全过程【示例】【示例】(a.初始化初始化)466527891790651850第47页，共105页，编辑于2022年，星期三(b.建堆建堆)466527891790651850665895190890506550468第48页，共105页，编辑于2022年，星期三（c）交换）交换90和和8862751174650896590908第49页，共105页，编辑于2022年，星期三（d）筛选调整）筛选调整 627511746508965890898518第50页，共105页，编辑于20

30、22年，星期三（e）交换）交换89和和6908927817465051656第51页，共105页，编辑于2022年，星期三（f）筛选调整）筛选调整 681746275150659089第52页，共105页，编辑于2022年，星期三g.交换交换65和和6817462751506659089第53页，共105页，编辑于2022年，星期三h.筛选调整筛选调整864627175051659089第54页，共105页，编辑于2022年，星期三(i).交换交换51和和8，输出，输出51 65908951第55页，共105页，编辑于2022年，星期三（j）筛选调整）筛选调整 65908951第56页，共10

31、5页，编辑于2022年，星期三（k）交换）交换50和和8，输出，输出50（l）筛选调整）筛选调整 65908951506590895150第57页，共105页，编辑于2022年，星期三（m）交换）交换46和和8，输出，输出46（n）筛选调整）筛选调整（o）交换）交换27和和6，输出，输出27（p）筛选调整）筛选调整 第58页，共105页，编辑于2022年，星期三（q.）交换）交换17和和6，输出，输出17（r）筛选调整）筛选调整（s）交换）交换8和和6，输出，输出8 （t）输出）输出6第59页，共105页，编辑于2022年，星期三第60页，共105页，编辑于2022年，星期三通过通过“交换交换

32、”无序序列中的记录从而得到无序序列中的记录从而得到其中其中关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它加入到有加入到有序子序列中序子序列中，以此方法增加记录的有序子序列的长，以此方法增加记录的有序子序列的长度。度。8.4 交交 换换 排排 序序第61页，共105页，编辑于2022年，星期三 一、冒泡排序一、冒泡排序 二、快速排序二、快速排序交交 换换 排排 序分类序分类第62页，共105页，编辑于2022年，星期三基本思想基本思想：比较比较相邻记录相邻记录，将，将关键字最大关键字最大的记录的记录交交换到换到 后面后面的位置上的位置上一、冒泡排序一、冒泡排序冒泡排序总的冒泡排序总

33、的时间复杂度时间复杂度为为O(nO(n2 2)第63页，共105页，编辑于2022年，星期三假设在排序过程中，记录序列假设在排序过程中，记录序列R1.n的状态为：的状态为：第第 i 趟冒泡排序趟冒泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较比较相邻记录相邻记录，将，将关键关键字最大字最大的记录的记录交换到交换到 n-i+1 的位置上的位置上第64页，共105页，编辑于2022年，星期三【冒泡排序示例】【冒泡排序示例】-相邻两数比较，大值下沉相邻两数比较，大值下沉初始状态初始状态 65 97

34、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 设待排记录序列的关键字为设待排记录序列的关键字为(65,97,76,13,27,49,58)(65,97,76,13,27,49,58)冒泡排序每一趟执行后的序列状态如下：冒泡排序每一趟执行后的序列状态如下：第65页，共105页，编辑于2022年，星期三练

35、习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请，请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。给出采用冒泡排序法对该序列作升序排序的每一趟的结果。第66页，共105页，编辑于2022年，星期三 已知序列已知序列17，18，55，40，7，32，73，65，89,请给出采用冒泡排序法对该序列作升序排序的每一趟的结请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。果。初始：初始：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

36、第第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，40，55，65，73，89【练习答案】【练习答案】第67页，共105页，编辑于2022年，星期三 目标目标：找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，

37、凡其凡其关键字小于枢轴关键字小于枢轴的记录均的记录均移动至该记录之前，移动至该记录之前，反之，反之，凡凡关键字大于枢轴关键字大于枢轴的记录均的记录均移动至该记录之后移动至该记录之后。致使致使一趟排序一趟排序之后，记录的无序序列之后，记录的无序序列Rs.t将将分割分割成两部分成两部分：Rs.i-1和和Ri+1.t，且且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。一趟快速排序（一次划分）一趟快速排序（一次划分）二、快速排序二、快速排序第68页，共105页，编辑于2022年，星期三stlowhigh设设 Rs=52 为枢轴为枢轴 将将 Rhigh.key 和和

38、 枢轴的关键字进行比较，要求枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字枢轴的关键字,则不交换则不交换 将将 Rlow.key 和和 枢轴的关键字进行比较，要求枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字枢轴的关键字,则交换两数则交换两数high23lowhighlow例例R052lowhighhighhighlow【快速排序示例】【快速排序示例】528052145252第69页，共105页，编辑于2022年，星期三 可见，经过可见，经过“一次划分一次划分”，将关键字序列，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为调整为:23,4

39、9,14,36,(52)58,61,97,80,75第70页，共105页，编辑于2022年，星期三快速排序基本思想快速排序基本思想 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后，之后分别分别对对分割所得两个子序列分割所得两个子序列“递归递归”进行快速排序进行快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序 快速排序的时间复杂度为快速排序的时间复杂度为O(nlogn)第71页，共105页，编辑于2022年，星期三第第1趟：趟：(23,49,14,36

40、)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第72页，共105页，编辑于2022年，星期三练习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用快速排序法对该序列作升序排列时的每一趟的结请给出采用快速排序

41、法对该序列作升序排列时的每一趟的结果果第73页，共105页，编辑于2022年，星期三已知序列已知序列17，18，55，40，7，32，73，65，89，请，请给出采用快速排序法对该序列作升序排列时的每一趟的结给出采用快速排序法对该序列作升序排列时的每一趟的结果果初初 始始：17，1 8，5 5，4 0，7，3 2，7 3，6 5，8 9第第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，(89)第第 4趟趟：7，1 7，1 8，3 2，4

42、 0，5 5，6 5，7 3，8 9【练习答案】【练习答案】第74页，共105页，编辑于2022年，星期三8.5 归归 并并 排排 序序 归并排序的过程基于下列归并排序的过程基于下列基本思想基本思想进行：进行：将两个或两个以上的将两个或两个以上的有序子序列有序子序列“归并归并”为一为一个有序序列。个有序序列。第75页，共105页，编辑于2022年，星期三在内部排序中，通常采用的是在内部排序中，通常采用的是2-路归并路归并排序。即：排序。即：将将两个位置相邻的记录两个位置相邻的记录有序子序列有序子序列归并为一个记录的有序序列归并为一个记录的有序序列。有有 序序 序序 列列 Rl.n有序子序列有序

43、子序列 Rl.m有序子序列有序子序列 Rm+1.n第76页，共105页，编辑于2022年，星期三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第78页，共105页，编辑于2022年，星期三 容易看出，对容易看出，对 n 个记录进行归并排序的时间个记录进行归并排序的时间复杂度为复杂度为(nlogn)。即：即：每一趟归并的时间复杂度为每一趟归并的时间复杂度为 O(n)，总共

44、需进行总共需进行 log2n 趟。趟。第79页，共105页，编辑于2022年，星期三练习练习 已知序列（已知序列（11，16，6，5，3，14，1，9）请给出采用归）请给出采用归并排序法对该序列作升序排列时的每一趟的结果并排序法对该序列作升序排列时的每一趟的结果第80页，共105页，编辑于2022年，星期三 已知序列（已知序列（11，16，6，5，3，14，1，9）请给出）请给出采用归并排序法对该序列作升序排列时的每一趟的结果采用归并排序法对该序列作升序排列时的每一趟的结果【练习答案】【练习答案】初始：初始：11，16，6，5，3，14，1，9第第1趟：趟：11，165，63，141，9第第2

45、趟：趟：5，6，11，161，3，9，14第第3趟：趟：1，3，5，6，9，11，14，16第第3趟归并完毕，则排序结束趟归并完毕，则排序结束第81页，共105页，编辑于2022年，星期三 基数排序是一种借助基数排序是一种借助“多关键字排序多关键字排序”的思想来实的思想来实现现“单关键字排序单关键字排序”的内部排序算法。的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序8.6 基基 数数 排排 序序第82页，共105页，编辑于2022年，星期三例如，扑克牌中例如，扑克牌中52张牌面的次序关系为张牌面的次序关系为:2 3 A2 3 A 2 3 A 2 3 A 每一张牌有两个每一

46、张牌有两个“关键字关键字”:花色（花色（）和面）和面值（值（23A），且），且“花色花色”的地位高于的地位高于“面值面值”，在比，在比较任意两张牌面的大小时，必须先比较较任意两张牌面的大小时，必须先比较“花色花色”，若，若“花色花色”相同，则再比较面值。相同，则再比较面值。8.6 基基 数数 排排 序序第83页，共105页，编辑于2022年，星期三一、多关键字的排序一、多关键字的排序 n 个记录的序列个记录的序列 R1,R2,，Rn，且每个记录，且每个记录Ri中中含有含有d个关键字个关键字(Ki0,Ki1,Kid-1)，则记录序列对关键字，则记录序列对关键字 (Ki0,Ki1,Kid-1)有序

47、有序是指：是指：其中其中:K0 被称为被称为 “最主最主”位关键字位关键字Kd-1 被称为被称为 “最次最次”位关键字位关键字 对于序列中任意两个记录对于序列中任意两个记录 Ri 和和 Rj (1ijn)都都满足满足下列下列(词典词典)有序有序关系：关系：(Ki0,Ki1,Kid-1)(Kj0,Kj1,Kjd-1)22 3第84页，共105页，编辑于2022年，星期三 实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:最低位优先最低位优先LSD法法 (Least Significant Digit first)最高位优先最高位优先MSD法 (Most Significant Dig

48、it first)第85页，共105页，编辑于2022年，星期三 先对先对K0进行排序进行排序，并，并按按 K0 的不同值将记录序列的不同值将记录序列分成分成若干子序列若干子序列，每个子序列中的记录都具有相同的，每个子序列中的记录都具有相同的K0值；然后，值；然后，分别分别就每个子序列对就每个子序列对 K1 进行排序进行排序，按按 K1值不同将记录值不同将记录序列序列分成若干更小的子序列分成若干更小的子序列；依次重复依次重复，直至对最次位关直至对最次位关键字键字Kd-1进行进行排序排序，最后，将所有，最后，将所有子序列依次联接子序列依次联接在一起成在一起成为一个有序序列为一个有序序列。【最高位

49、优先【最高位优先MSD法】第86页，共105页，编辑于2022年，星期三 先对先对 Kd-1 进行排序进行排序，然后对然后对 Kd-2 进行排序，依次进行排序，依次类推，类推，直至对最主位关键字直至对最主位关键字 K0 排序完成为止排序完成为止。【最低位优先【最低位优先LSD法】法】排序过程中不需要根据排序过程中不需要根据“前一个前一个”关键字的排序结关键字的排序结果，将记录序列分割成若干个果，将记录序列分割成若干个(“(“前一个前一个”关键字不同的关键字不同的)子序列。子序列。第87页，共105页，编辑于2022年，星期三例如例如:学生记录含三个关键字学生记录含三个关键字:系别系别、班号班号

50、和和班内的序列号班内的序列号，其中以系别为最主位关键字。其中以系别为最主位关键字。无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3,2,301,2,153,1,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的排序过程如下的排序过程如下:第88页，共105页，编辑于2022年，星期三 按按LSD法法进行排序时，不必分成若干子序列，对每个进行排序时，不必分成若干子序列，对每个关键字都是整个序列参加排序，但对关键字