《第八章排序精选文档.ppt》由会员分享，可在线阅读，更多相关《第八章排序精选文档.ppt（105页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章排序本讲稿第一页，共一百零五页第第8章章 排排 序序学习目的要求学习目的要求:1.掌握排序的概念和排序的种类。掌握排序的概念和排序的种类。2.熟练掌握五类基本排序熟练掌握五类基本排序:插入排序、交换排序、插入排序、交换排序、选择排序、归并排序和基数排序的算法思想、选择排序、归并排序和基数排序的算法思想、算法实现和性能分析。算法实现和性能分析。本讲稿第二页，共一百零五页8.1 概述概述8.2 插入排序插入排序8.3 交换排序交换排序8.4 选择排序选择排序8.5 归并排序归并排序8.6 基数排序基数排序8.7 各种排序方法的综合比较各种排序方法的综合比较本讲稿第三页，共一百零五页8.1 概
2、概 述述一、排序的定义一、排序的定义二、内部排序和外部排序二、内部排序和外部排序三、内部排序方法的分类三、内部排序方法的分类本讲稿第四页，共一百零五页一、什么是排序？一、什么是排序？排序是计算机内经常进行的一种操作，其目的是将排序是计算机内经常进行的一种操作，其目的是将一组一组“无序无序”的记录序列调整为的记录序列调整为“有序有序”的记录序列。的记录序列。例如：例如：将下列关键字序列将下列关键字序列52,49,80,36,14,58,61,23,97,75调整为调整为14,23,36,49,52,58,61,75,80,97本讲稿第五页，共一百零五页【排序算法的稳定性】：【排序算法的稳定性】：
3、如果待排序的序列中，存在多个具有相同关键如果待排序的序列中，存在多个具有相同关键字的记录，若经过排序这些记录的相对次序保持不字的记录，若经过排序这些记录的相对次序保持不变，则称这种排序算法是变，则称这种排序算法是稳定稳定的；经过排序这些记的；经过排序这些记录的相对次序发生了改变，则称这种排序算法是录的相对次序发生了改变，则称这种排序算法是不稳不稳定定的。的。本讲稿第七页，共一百零五页例如：例如：排序前排序前(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)则称该排序方法是则称该排序方法是不稳定不稳定的。的。本讲稿第八页，共一百零五页二、内部排序和外部排序二、内部排序和外部排序 待排序记录存放在计算机随机存储器中进行的排序待排序记录存放在计算机随机存储器中进行的排序过程，为过程，为内部排序；内部排序；若待排序记录的数量很大，以至内存一次不能若待排序记录的数量很大，以至内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问容纳全部记录，在排序过程中尚需对外存进行访问的排序过程，为的排序过程，为外部排序外部排序。本讲稿第九页，共一百零五页三、内部排序的方法三、内部排序的方法内
5、部排序的过程是一个逐步扩大记录的有内部排序的过程是一个逐步扩大记录的有序序列长度的过程。序序列长度的过程。经过一趟排序经过一趟排序有序序列区有序序列区无无 序序 序序 列列 区区有序序列区有序序列区无无 序序 序序 列列 区区本讲稿第十页，共一百零五页在排序过程中的基本操作：在排序过程中的基本操作：比较两个关键字的大小比较两个关键字的大小将记录从一个位置移动到另一个位置将记录从一个位置移动到另一个位置 前一种操作对大多数排序方法来说是必要的，而后一种前一种操作对大多数排序方法来说是必要的，而后一种操作可通过改变记录的存储方式来予以避免。操作可通过改变记录的存储方式来予以避免。本讲稿第十二页，共
6、一百零五页 8.2 插插 入入 排排 序序将无序子序列中的将无序子序列中的一个或几个记录一个或几个记录“插入插入”到有到有序序列中，从而增加记录的有序子序列的长度。序序列中，从而增加记录的有序子序列的长度。本讲稿第十四页，共一百零五页【一趟直接插入排序的基本思想】：【一趟直接插入排序的基本思想】：把把 n 个记录的序列划分为个记录的序列划分为已排序部分已排序部分和和未排序部分未排序部分，即在涉及第即在涉及第 i 个记录个记录 Ri 时时,（R1,.,Ri-1）是已排）是已排好的有序部分，（好的有序部分，（Ri,Ri+1,.,Rn）属于未排序部分。）属于未排序部分。找出找出 Ri 在此有序序列中
7、应插入的位置，将在此有序序列中应插入的位置，将 Ri插入插入。原位置上的记录至原位置上的记录至 Ri-1 均顺序后移一位。均顺序后移一位。本讲稿第十五页，共一百零五页有序序列有序序列R1.i-1Ri无序序列无序序列 Ri.n有序序列有序序列R1.i无序序列无序序列 Ri+1.n图示图示本讲稿第十六页，共一百零五页直接插入排序直接插入排序（基于顺序查找）（基于顺序查找）不同的具体实现方法导致不同的算法描述不同的具体实现方法导致不同的算法描述折半插入排序折半插入排序（基于折半查找）（基于折半查找）希尔排序希尔排序（基于逐趟缩小增量）（基于逐趟缩小增量）本讲稿第十七页，共一百零五页一、直接插入排序一
8、、直接插入排序利用利用“顺序查找顺序查找”实现实现“在在R1.i-1中中查找查找Ri的插的插入位置入位置”对于直接插入排序：其对于直接插入排序：其时间复杂度时间复杂度为为O(n2 2)适用于当适用于当待排序记录的数量很小待排序记录的数量很小时时 本讲稿第十八页，共一百零五页【直接插入排序示例】【直接插入排序示例】初始状态初始状态 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
9、 12 12 18 30 16 第第5趟（趟（i=6）(16)10 12 12 16 18 30 待排序记录序列为待排序记录序列为(18(18，1212，1010，1212，3030，1616）直接插入排序每一趟执行后的序列状态直接插入排序每一趟执行后的序列状态:监视哨监视哨本讲稿第十九页，共一百零五页1已知序列已知序列72，83，99，65，10，36，7，9，请，请给出采用插入排序法对该序列作升序排序时的每一趟给出采用插入排序法对该序列作升序排序时的每一趟的结果。的结果。【练习】【练习】本讲稿第二十页，共一百零五页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，65
11、，72，83，99）【练习答案】【练习答案】本讲稿第二十一页，共一百零五页 因为因为 R1.i-1 是一个按关键字有序的有序序列，是一个按关键字有序的有序序列，则可以则可以利用折半查找实现利用折半查找实现“在在R1.i-1中中查找查找Ri的的插入插入位置位置”，如此实现的插入排序为，如此实现的插入排序为折半插入折半插入排序。排序。二、折半插入排序二、折半插入排序本讲稿第二十二页，共一百零五页14 36 49 52 80 58 61 23 97 75ilowhighmmlowlowmhigh例如例如:插入位置L.r【折半插入排序折半插入排序示例】示例】本讲稿第二十三页，共一百零五页 对于折半插入
12、排序对于折半插入排序，仅减少了关键字比较的次数，记仅减少了关键字比较的次数，记录的移动次数不变，其录的移动次数不变，其时间复杂度时间复杂度为为O(nO(n2 2)；折半插入排序适用于当折半插入排序适用于当待排序记录的数量很大待排序记录的数量很大时，时，可大幅度降低关键字的比较次数。可大幅度降低关键字的比较次数。本讲稿第二十四页，共一百零五页三三 2-路插入排序路插入排序2-路插入排序是对折半插入排序的改进算法，它是利用增路插入排序是对折半插入排序的改进算法，它是利用增加辅助空间来减少排序过程中移动记录的次数，即加辅助空间来减少排序过程中移动记录的次数，即“以空间换以空间换时间时间”。本讲稿第二
13、十五页，共一百零五页具体做法是具体做法是:建立一个和待排序序列建立一个和待排序序列rn同类型的数组同类型的数组dn作为辅助空间。作为辅助空间。先将先将r0的值赋给的值赋给d0，将，将d0看成是处于最后有看成是处于最后有序序列中处于中间位置的记录，序序列中处于中间位置的记录，再从再从r1开始依次将记录插入到开始依次将记录插入到d0之前或之后的有序之前或之后的有序序列中。序列中。将数组将数组d看成是一循环向量（既首尾相连的环状空间），看成是一循环向量（既首尾相连的环状空间），并设置两个指针并设置两个指针first和和final分别指向有序序列的第一条和最后分别指向有序序列的第一条和最后一条记录，将
14、当前待插入记录一条记录，将当前待插入记录ri与与d0比较，若比较，若rid0，则将其插入，则将其插入d0之前的有序序列中，反之，之前的有序序列中，反之，则将其插入到则将其插入到d0之后的有序序列中。之后的有序序列中。当所有的记录都插入完成后，从指针当所有的记录都插入完成后，从指针first所指向的记录开始一直读所指向的记录开始一直读取到指针取到指针final所指向的记录，所得到的序列就是排序后的有序序列。所指向的记录，所得到的序列就是排序后的有序序列。本讲稿第二十六页，共一百零五页三三 2-路插入排序路插入排序42 36 56 78 67 11 27 26i=142i=24236i=34256
15、36i=442567836i=54256677836i=6425667781136i=742566778112736i=84256677811273636firstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinalfirstfinal本讲稿第二十七页，共一百零五页 四、希尔排序四、希尔排序(缩小增量排序缩小增量排序)基本思想基本思想：对待排记录序列先作：对待排记录序列先作“宏观宏观”调整，调整，再作再作“微观微观”调整。调整。所谓所谓“宏观宏观”调整，指的是，调整，指的是，“跳跃式跳跃式”的插入排序。的插入排序。即
16、先将整个待排记录序列分割成若干子序列分别进行即先将整个待排记录序列分割成若干子序列分别进行直接插入排序直接插入排序，待整个序列中的记录，待整个序列中的记录“基本有序基本有序”时，时，再对全体记录进行一次直接插入排序。再对全体记录进行一次直接插入排序。本讲稿第二十八页，共一百零五页 将记录序列分成若干子序列，分别对每个子将记录序列分成若干子序列，分别对每个子序列进行插入排序。序列进行插入排序。后面实例，后面实例，d d 称为增量，它的值在排序过程称为增量，它的值在排序过程中中从大到小从大到小逐渐缩小，直至最后一趟排序逐渐缩小，直至最后一趟排序减为减为 1 1。增量增量d d的取值的取值:d:d0
17、 0=n/2n/2,d,d1 1=d d0 0/2/2,d,di i=d di-1i-1/2/2(除后的结果除后的结果都都应应”下取整下取整”)”)具体做法具体做法：本讲稿第二十九页，共一百零五页例：初始关键字例：初始关键字 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
18、 49 13 38 27 65 49 97 55 76 0413 49 04 38 97 27 55 49 65 76 本讲稿第三十页，共一百零五页例如：例如：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 本讲稿第三十一页，共一百零五
19、页 从上述排序过程可见，希尔排序中子序列的构成不是简从上述排序过程可见，希尔排序中子序列的构成不是简单地单地“逐段分割逐段分割”，而是，而是将相隔某个将相隔某个“增量增量”的记录组成一的记录组成一个子序列个子序列。关键字较小的记录不是一步一步地往前挪动，。关键字较小的记录不是一步一步地往前挪动，而是而是“跳跃式跳跃式”地往前移，从而使得在进行最后一躺增量地往前移，从而使得在进行最后一躺增量为为1的插入排序时，序列已基本有序，只要作记录的少量的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序。比较和移动即可完成排序。因而因而希尔排序的时间复杂度比直接插入排序希尔排序的时间复杂度
20、比直接插入排序低低。它的时。它的时间是所取间是所取“增量增量”序列的函数。序列的函数。本讲稿第三十二页，共一百零五页 已知序列（已知序列（10，16，4，3，6，12，1，9，15，8），请给出采用希尔排序法对该序列作升序排序时），请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。的每一趟的结果。练习练习本讲稿第三十三页，共一百零五页 已知序列（已知序列（10，16，4，3，6，12，1，9，15，8），请给出采用希尔排序法对该序列作升序排），请给出采用希尔排序法对该序列作升序排序时的每一趟的结果。序时的每一趟的结果。初始：初始：10，16，4，3，6，12，1，9，15，8d=5第第1
21、趟：趟：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【练习答案】【练习答案】本讲稿第三十四页，共一百零五页8.3 选选 择择 排排 序序从记录的无序子序列中从记录的无序子序列中“选择选择”关键字最小或最大关键字最小或最大的记录，并将它的记录，并将它加入到有序子序列加入到有序子序列中，以此方法增加中，以此方法增加记录的有序子序列的长度。记录的有序子序列的长度。简简 单单 选选 择择 排排 序序堆堆 排排 序序本讲稿第三十五页，共一百零五页一、简单选择排序一、简单选
22、择排序【基本思想】【基本思想】：一趟简单选择排序的操作为：一趟简单选择排序的操作为：通过通过n-in-i次关键字间的比较，从次关键字间的比较，从n-i+1n-i+1个记录中选个记录中选出出关键字最小关键字最小的记录，并和第的记录，并和第i i（1in)1in)个记录交换之。个记录交换之。简单选择排序时间复杂度为简单选择排序时间复杂度为O(nO(n2 2)本讲稿第三十六页，共一百零五页假设排序过程中，待排记录序列的状态为：假设排序过程中，待排记录序列的状态为：有序序列有序序列R1.i-1无序序列无序序列 Ri.n 第第 i 趟趟简单选择排序简单选择排序从中选出从中选出关键字最小的记录关键字最小的
23、记录有序序列有序序列R1.i无序序列无序序列 Ri+1.n本讲稿第三十七页，共一百零五页【简单选择排序【简单选择排序】-选择最小的浮上来选择最小的浮上来初始状态初始状态 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、讲稿第三十八页，共一百零五页练习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用简单选择排序法对该序列作升序排列时的每一请给出采用简单选择排序法对该序列作升序排列时的每一趟的结果趟的结果本讲稿第三十九页，共一百零五页 已知序列已知序列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，40，
25、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【练习答案】【练习答案】本讲稿第四十页，共一百零五页二、堆排序二、堆排序堆是满足下列性质的数列堆是满足下列性质的数列r1,r2,，rn：或或堆的定义堆的定义:(小顶堆小顶堆)(大顶堆大顶堆
26、)本讲稿第四十一页，共一百零五页3412362765498173554098是堆是堆14不不例如例如:12,36,27,65,40,34,98,81,73,55,4912,36,27,65,40,14,98,81,73,55,49本讲稿第四十三页，共一百零五页建堆是一个从下往上进行建堆是一个从下往上进行“筛选筛选”的过程。从一个非终端结的过程。从一个非终端结点点n/2(下取整下取整)开始开始40554973816436122798例如例如:排序之前的关键字序列为排序之前的关键字序列为123681734998817355 现在，左现在，左/右子树都已经调整为堆，最后只要调整根结右子树都已经调整为
27、堆，最后只要调整根结点，使整个二叉树是个点，使整个二叉树是个“堆堆”即可。即可。9849406336122740,55,49,73,12,27,98,81,63,36本讲稿第四十五页，共一百零五页98814973556412362740例如例如:是大顶堆是大顶堆12但在但在 98 98 和和 12 12 进行互换之后，它就进行互换之后，它就不不是堆了，是堆了，因此，需要对它进行因此，需要对它进行“筛选筛选”。98128173641298比较比较比较本讲稿第四十六页，共一百零五页 已知序列已知序列50，8，51，6，90，17，89，27，65，46，以下给出采用堆排序法排序的全过程，以下给出采
28、用堆排序法排序的全过程【示例】【示例】(a.初始化初始化)466527891790651850本讲稿第四十七页，共一百零五页(b.建堆建堆)466527891790651850665895190890506550468本讲稿第四十八页，共一百零五页（c）交换）交换90和和8862751174650896590908本讲稿第四十九页，共一百零五页（d）筛选调整）筛选调整 627511746508965890898518本讲稿第五十页，共一百零五页（e）交换）交换89和和6908927817465051656本讲稿第五十一页，共一百零五页（f）筛选调整）筛选调整 68174627515065908
29、9本讲稿第五十二页，共一百零五页g.交换交换65和和6817462751506659089本讲稿第五十三页，共一百零五页h.筛选调整筛选调整864627175051659089本讲稿第五十四页，共一百零五页(i).交换交换51和和8，输出，输出51 65908951本讲稿第五十五页，共一百零五页（j）筛选调整）筛选调整 65908951本讲稿第五十六页，共一百零五页（k）交换）交换50和和8，输出，输出50（l）筛选调整）筛选调整 65908951506590895150本讲稿第五十七页，共一百零五页（m）交换）交换46和和8，输出，输出46（n）筛选调整）筛选调整（o）交换）交换27和和6，
30、输出，输出27（p）筛选调整）筛选调整 本讲稿第五十八页，共一百零五页（q.）交换）交换17和和6，输出，输出17（r）筛选调整）筛选调整（s）交换）交换8和和6，输出，输出8 （t）输出）输出6本讲稿第五十九页，共一百零五页本讲稿第六十页，共一百零五页通过通过“交换交换”无序序列中的记录从而得到无序序列中的记录从而得到其中其中关键字最小关键字最小或或最大最大的记录，并将它的记录，并将它加入到有加入到有序子序列中序子序列中，以此方法增加记录的有序子序列的，以此方法增加记录的有序子序列的长度。长度。8.4 交交 换换 排排 序序本讲稿第六十一页，共一百零五页 一、冒泡排序一、冒泡排序 二、快速排
31、序二、快速排序交交 换换 排排 序分类序分类本讲稿第六十二页，共一百零五页基本思想基本思想：比较比较相邻记录相邻记录，将，将关键字最大关键字最大的记录的记录交交换到换到 后面后面的位置上的位置上一、冒泡排序一、冒泡排序冒泡排序总的冒泡排序总的时间复杂度时间复杂度为为O(nO(n2 2)本讲稿第六十三页，共一百零五页假设在排序过程中，记录序列假设在排序过程中，记录序列R1.n的状态为：的状态为：第第 i 趟冒泡排序趟冒泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较比较相邻记录相邻记录，将，将关键
32、关键字最大字最大的记录的记录交换到交换到 n-i+1 的位置上的位置上本讲稿第六十四页，共一百零五页【冒泡排序示例】【冒泡排序示例】-相邻两数比较，大值下沉相邻两数比较，大值下沉初始状态初始状态 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)冒泡排序每一趟执行后的序列状态如下：冒泡排序每一趟执行后的序列状态如下：本讲稿第六十五页，共一百零五页练习练习 已知序列已知序列17，18，55，40，7，32，73，65，89，请给出采用冒泡排序法对该序列作升序排序的每一趟的结请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。果。本讲稿第六十六页，共一百零五页 已知序列已知序列17，18，55，40，7，32，73，65，89,请给出请给出采用冒泡排序法对该序列作升序排序的每一趟的结果。采用冒泡排序法对该序列作升序排序的每一趟的结果。初始：初始：17
34、，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，40，
35、55，65，73，89【练习答案】【练习答案】本讲稿第六十七页，共一百零五页 目标目标：找一个记录，以它的关键字作为找一个记录，以它的关键字作为“枢轴枢轴”，凡其，凡其关键字小于枢轴关键字小于枢轴的记录均的记录均移动至该记录之前，移动至该记录之前，反之，反之，凡凡关键字大于枢轴关键字大于枢轴的记录均的记录均移动至该记录之后移动至该记录之后。致使致使一趟排序一趟排序之后，记录的无序序列之后，记录的无序序列Rs.t将将分割成分割成两部分两部分：Rs.i-1和和Ri+1.t，且且 Rj.key Ri.key Rj.key (sji-1)枢轴枢轴 (i+1jt)。一趟快速排序（一次划分）一趟快速排序（
36、一次划分）二、快速排序二、快速排序本讲稿第六十八页，共一百零五页stlowhigh设设 Rs=52 为枢轴为枢轴 将将 Rhigh.key 和和 枢轴的关键字进行比较，要求枢轴的关键字进行比较，要求Rhigh.key 枢轴的关键字枢轴的关键字,则不交换则不交换 将将 Rlow.key 和和 枢轴的关键字进行比较，要求枢轴的关键字进行比较，要求Rlow.key 枢轴的关键字枢轴的关键字,则交换两数则交换两数high23lowhighlow例例R052lowhighhighhighlow【快速排序示例】【快速排序示例】528052145252本讲稿第六十九页，共一百零五页 可见，经过可见，经过“一
37、次划分一次划分”，将关键字序列，将关键字序列 52,49,80,36,14,58,61,97,23,75 调整为调整为:23,49,14,36,(52)58,61,97,80,75本讲稿第七十页，共一百零五页快速排序基本思想快速排序基本思想 首先对无序的记录序列进行首先对无序的记录序列进行“一次划分一次划分”，之后，之后分别分别对分割所得两个子序列对分割所得两个子序列“递归递归”进行快速排序进行快速排序。无无 序序 的的 记记 录录 序序 列列无序记录子序列无序记录子序列(1)无序子序列无序子序列(2)枢轴枢轴一次划分一次划分分别进行快速排序分别进行快速排序 快速排序的时间复杂度为快速排序的时
38、间复杂度为O(nlogn)本讲稿第七十一页，共一百零五页第第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本讲稿第七十二页，共一百零五页练习练习 已知序列已知序列17，18，55，40，7，32，73，65
39、，89，请给出采用快速排序法对该序列作升序排列时的每一趟的请给出采用快速排序法对该序列作升序排列时的每一趟的结果结果本讲稿第七十三页，共一百零五页已知序列已知序列17，18，55，40，7，32，73，65，89，请给，请给出采用快速排序法对该序列作升序排列时的每一趟的结果出采用快速排序法对该序列作升序排列时的每一趟的结果初初 始始：1 7，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，(6
40、5)，73，(89)第第 4趟趟：7，1 7，1 8，3 2，4 0，5 5，6 5，7 3，8 9【练习答案】【练习答案】本讲稿第七十四页，共一百零五页8.5 归归 并并 排排 序序 归并排序的过程基于下列归并排序的过程基于下列基本思想基本思想进行：进行：将两个或两个以上的将两个或两个以上的有序子序列有序子序列“归并归并”为一个为一个有序序列。有序序列。本讲稿第七十五页，共一百零五页在内部排序中，通常采用的是在内部排序中，通常采用的是2-路归并路归并排序。即：排序。即：将将两个位置相邻的记录两个位置相邻的记录有序子序列有序子序列归并为一个记录的有序序列归并为一个记录的有序序列。有有 序序 序
41、序 列列 Rl.n有序子序列有序子序列 Rl.m有序子序列有序子序列 Rm+1.n本讲稿第七十六页，共一百零五页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本讲稿第七十八页，共一百零五页 容易看出，对容易看出，对 n 个记录进行归并排序的时间个记录进行归并排序的时间复杂度为复杂度为(nlogn)。即：即：每一趟归并的时间复杂度为每一趟归并的时间复杂度为 O(n)，总共
42、需进行总共需进行 log2n 趟。趟。本讲稿第七十九页，共一百零五页练习练习 已知序列（已知序列（11，16，6，5，3，14，1，9）请给出采）请给出采用归并排序法对该序列作升序排列时的每一趟的结果用归并排序法对该序列作升序排列时的每一趟的结果本讲稿第八十页，共一百零五页 已知序列（已知序列（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，
43、9，14第第3趟：趟：1，3，5，6，9，11，14，16第第3趟归并完毕，则排序结束趟归并完毕，则排序结束本讲稿第八十一页，共一百零五页 基数排序是一种借助基数排序是一种借助“多关键字排序多关键字排序”的思想来实现的思想来实现“单关键字排序单关键字排序”的内部排序算法。的内部排序算法。多关键字的排序多关键字的排序链式基数排序链式基数排序8.6 基基 数数 排排 序序本讲稿第八十二页，共一百零五页例如，扑克牌中例如，扑克牌中52张牌面的次序关系为张牌面的次序关系为:2 3 A2 3 A 2 3 A 2 3 A 每一张牌有两个每一张牌有两个“关键字关键字”:花色（花色（）和面值（和面值（23A）
44、，且），且“花色花色”的地位高于的地位高于“面值面值”，在，在比较任意两张牌面的大小时，必须先比较比较任意两张牌面的大小时，必须先比较“花色花色”，若，若“花色花色”相同，则再比较面值。相同，则再比较面值。8.6 基基 数数 排排 序序本讲稿第八十三页，共一百零五页一、多关键字的排序一、多关键字的排序 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本讲稿第八十四页，共一百零五页 实现多关键字排序通常有两种作法实现多关键字排序通常有两种作法:最低位优先最低位优先LSD法法 (Least Significant Digit first)最高位优先最高位优先MSD法 (Most Significant Digit first)本讲稿第八十五页，共一百零五页 先对先对K0进行排序进行排序，并，并按按 K0 的
46、不同值将记录序列的不同值将记录序列分成分成若干子序列若干子序列，每个子序列中的记录都具有相同的，每个子序列中的记录都具有相同的K0值；然后，值；然后，分别分别就每个子序列对就每个子序列对 K1 进行排序进行排序，按按 K1值不同将记录值不同将记录序列序列分成若干更小的子序列分成若干更小的子序列；依次重复依次重复，直至对最次位直至对最次位关键字关键字Kd-1进行进行排序排序，最后，将所有，最后，将所有子序列依次联接子序列依次联接在一起在一起成为一个有序序列成为一个有序序列。【最高位优先【最高位优先MSD法】本讲稿第八十六页，共一百零五页 先对先对 Kd-1 进行排序进行排序，然后对然后对 Kd-
47、2 进行排序，依进行排序，依次类推，次类推，直至对最主位关键字直至对最主位关键字 K0 排序完成为止排序完成为止。【最低位优先【最低位优先LSD法】法】排序过程中不需要根据排序过程中不需要根据“前一个前一个”关键字的排序关键字的排序结果，将记录序列分割成若干个结果，将记录序列分割成若干个(“(“前一个前一个”关键字不同关键字不同的的)子序列。子序列。本讲稿第八十七页，共一百零五页例如例如:学生记录含三个关键字学生记录含三个关键字:系别系别、班号班号和和班内的序列号班内的序列号，其中以系别为最主位关键字。其中以系别为最主位关键字。无序序列无序序列对对K2排序排序对对K1排序排序对对K0排序排序3
48、,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的排序过程如下的排序过程如下:本讲稿第八十八页，共一百零五页 按按LSD法法进行排序时，不必分成若干子序列，对进行排序时，不必分成若干子序列，对每个关键字都是整个序列参加排序，但对每个关键字都是整个序列参加排序，但对Ki(0 i k-2)进行排序时，只能用进行排序时，只能用稳定稳定的排序方法；的排序方法；按按LSD法法进行排序时，也可以不通过关键字间的
49、比进行排序时，也可以不通过关键字间的比较来实现排序，而是通过若干次较来实现排序，而是通过若干次“分配分配”和和“收集收集”来来实现排序。实现排序。本讲稿第八十九页，共一百零五页二、链式基数排序二、链式基数排序假如多关键字的记录序列中，每个关键字的取值范围假如多关键字的记录序列中，每个关键字的取值范围相同，则按相同，则按LSD法进行排序时，可以采用法进行排序时，可以采用“分配分配-收集收集”的的方法，其好处是不需要进行关键字间的比较。方法，其好处是不需要进行关键字间的比较。对于对于数字型数字型或或字符串型字符串型的的单关键字单关键字，可以，可以看成看成是由是由多个多个数位数位或或多个字符多个字符
50、构成的构成的多关键字多关键字，此时可以，此时可以采用采用这种这种“分分配配-收集收集”的办法的办法进行排序进行排序，称作称作基数排序法基数排序法。本讲稿第九十页，共一百零五页例如：对下列这组关键字例如：对下列这组关键字 209,386,768,185,247,606,230,834,539 首先按其首先按其“个位数个位数”取值分别为取值分别为 0,1,9 “分分配配”成成 10 组，之后按从组，之后按从 0 至至 9 的顺序将的顺序将 它们它们“收集收集”在在一起；一起；然后按其然后按其“十位数十位数”取值分别为取值分别为 0,1,9 “分分配配”成成 10 组，之后再按从组，之后再按从 0