《数据结构预算法第十章排序(38页PPT).pptx》由会员分享，可在线阅读，更多相关《数据结构预算法第十章排序(38页PPT).pptx（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、v10.1 概述概述v10.2 插入排序插入排序v10.3 快速排序快速排序v10.4 选择排序选择排序v10.5 归并排序归并排序v10.6 各种排序方法的比较各种排序方法的比较v典型例题典型例题第十章 排序第一页，编辑于星期二：四点 六分。10.1 10.1 概述概述v1.1.排序就是排序就是将一组任意顺序的数据按一定的规律排列起来的过程。v2.2.排序过程中的两种基本操作排序过程中的两种基本操作(1)比较两个关键值的大小。(2)根据比较结果，移动记录的位置。v3.3.对关键字排序的对关键字排序的3 3个原则：个原则：v(1)关键字值为数值型，则按键值大小为依据。v(2)关键字值为ASCI
2、I码，则按键值的内码编排顺序为依据。v(3)关键字值为汉字字符串类型，则大多以汉字拼音的字典次序为依据。第二页，编辑于星期二：四点 六分。4.4.排序方法的稳定和不稳定排序方法的稳定和不稳定v若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对元先具有相同的键值元素间的位置关系，排序前和排序后保持一致，称此排序方法为稳定排序稳定排序，反之称为不稳定排序。5.5.待排序记录的待排序记录的3 3种存储方式种存储方式v(1)待排序记录存放在地址连续的一组存储单元上（线性表的顺序存储结构类似）。v(2)待排序记录放在静态链表中（记录之间的次序关系由指针指示，排序不需要移动记录）。v(3
3、)待排序记录存放在地址连续的一组存储单元，同时另设一个指示各个记录存储位置的地址向量，在排序过程中不移动记录本身，而移动地址向量中这些记录的“地址”，在排序结束后，再按照地址向量中的值调整记录的存储位置。6.6.内排序内排序：整个排序过程都在内存进行的排序为内排序。7.7.外排序：外排序：待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。第三页，编辑于星期二：四点 六分。10.2 10.2 插入排序插入排序10.2.1 10.2.1 直接插入排序直接插入排序 1.1.基本思想：基本思想：直接插入排序是将一个记录插入到已排序好的有序直接插入排序是
4、将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增表中，从而得到一个新的，记录数增1 1的有序表。的有序表。v 48 62 35 77 55 14 35 98 v 48 62 35 77 55 14 35 98v 35 48 62 77 55 14 35 98 v 35 48 62 77 55 14 35 98 v 35 48 55 62 77 14 35 98 v 14 35 48 55 62 77 35 98 v 14 35 35 48 55 62 77 98 v 14 35 35 48 55 62 77 98 第四页，编辑于星期二：四点 六分。v2.2.监视哨的作用：监视哨的
5、作用：v（1 1）在进入确定插入位置的循环之前，保存了插入值）在进入确定插入位置的循环之前，保存了插入值riri的副本，避免因的副本，避免因记录的移动而丢失记录的移动而丢失riri中的内容。中的内容。v（2 2）使内循环总能够结束，以免循环过程中数组下标越界。）使内循环总能够结束，以免循环过程中数组下标越界。v3.3.效率分析效率分析v直接插入排序是稳定排序，最适合待排序关键字基本有序的序列。时间复直接插入排序是稳定排序，最适合待排序关键字基本有序的序列。时间复杂度杂度O(),O(),辅助空间为辅助空间为O(1)O(1)。第五页，编辑于星期二：四点 六分。例例设待排序的表有设待排序的表有10个
6、记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说明。说明采用直接插入排序方法进行排序的过程。采用直接插入排序方法进行排序的过程。第六页，编辑于星期二：四点 六分。v10.2.2 二分插入排序highlowi插入位置5861 23 97 751436495280imm14364952586180 23 97 75high low插入位置imm14364952586180 23 97 75high low插入位置第七页，编辑于星期二：四点 六分。v1.1.基本思想：基本思想：v直接插入排序算法虽简单，但当记录数量大时，则比较次数将大大增加，对于有序表，为了减少关键
7、字的比较次数，可采用二分插入排序。v2.2.效率分析效率分析v二分插入排序是稳定的排序。时间复杂度和空间复杂度和直接插入排序的一样。第八页，编辑于星期二：四点 六分。v10.2.3 10.2.3 希尔排序希尔排序v希尔排序又称希尔排序又称“缩小增量排序缩小增量排序”，它也是一种插入排序的方法，但时，它也是一种插入排序的方法，但时间上比前两种排序方法有比较大的改进。间上比前两种排序方法有比较大的改进。v1.1.基本思想：基本思想：先将整个待排序记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序时”，再对全体记录进行一次直接插入排序。v2.2.特点：特点：子序列不是简单的
8、逐段分割，而是将相隔某个“增量”的记录组成一个子序列，所以关键字较小的记录不是一步一步地前移，而是跳跃式前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序。v3.3.效率分析：效率分析：v 希尔排序是一种不稳定排序。第九页，编辑于星期二：四点 六分。例如：例如：16 25 12 30 47 11 23 36 9 18 31 第一趟希尔排序，设增量第一趟希尔排序，设增量 d=5d=511 23 12 9 18 16 25 36 30 47 31 第二趟希尔排序，设增量第二趟希尔排序，设增量 d=3d=39 18 12 11 23 16 25 31 30 47 36第三趟希尔排序，设
9、增量第三趟希尔排序，设增量 d=1d=1 9 11 12 16 18 23 25 30 31 36 47 第十页，编辑于星期二：四点 六分。例例 设设 待待 排排 序序 的的 表表 有有 10个个 记记 录录,其其 关关 键键 字字 分分 别别 为为9,8,7,6,5,4,3,2,1,0。说明采用希尔排序方法进行排序的过程。说明采用希尔排序方法进行排序的过程。第十一页，编辑于星期二：四点 六分。10.3 10.3 快速排序快速排序v快速排序又称为交换排序，是根据记录的关键字的大小，通过记录交换来快速排序又称为交换排序，是根据记录的关键字的大小，通过记录交换来实现排序的。实现排序的。v10.3.
10、1.10.3.1.冒泡排序冒泡排序v1.1.基本思想：基本思想：冒泡排序也称沉底法，每相邻两个记录关键字比较大小，大冒泡排序也称沉底法，每相邻两个记录关键字比较大小，大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数）。交换一次，记录减少一个反序数）。v2.2.效率分析：效率分析：v冒泡排序是一种稳定排序。冒泡排序是一种稳定排序。第十二页，编辑于
11、星期二：四点 六分。例如：例如：第十三页，编辑于星期二：四点 六分。例例设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说。说明采用冒泡排序方法进行排序的过程。明采用冒泡排序方法进行排序的过程。第十四页，编辑于星期二：四点 六分。v10.3.2 10.3.2 快速排序快速排序v1.1.基本思想：基本思想：任取待排序序列中的某个元素作为基准，通过一趟任取待排序序列中的某个元素作为基准，通过一趟快速排序将待排序的元素分割成左右两个子序列，其中左子序列快速排序将待排序的元素分割成左右两个子序列，其中左子序列元素的排序关键字均比基准（也
12、称为枢轴）元素的关键字值小；元素的排序关键字均比基准（也称为枢轴）元素的关键字值小；右子序列元素的关键字均比基准元素的关键字值大，基准元素得右子序列元素的关键字均比基准元素的关键字值大，基准元素得到了它在整个序列中的最终位置并被存放好，这个过程称为一趟到了它在整个序列中的最终位置并被存放好，这个过程称为一趟快速排序。快速排序。v2.2.效率分析：效率分析：v快速排序是不稳定排序。快速排序是不稳定排序。第十五页，编辑于星期二：四点 六分。例例 设设 待待 排排 序序 的的 表表 有有 10个个 记记 录录,其其 关关 键键 字字 分分 别别 为为6,8,7,9,0,1,3,2,4,5。说明采用快
13、速排序方法进行排序的过程。说明采用快速排序方法进行排序的过程。第十六页，编辑于星期二：四点 六分。10.4 10.4 选择排序选择排序v选择排序选择排序是从待排序序列中选取一个关键字值最小的记录，把它与第一个是从待排序序列中选取一个关键字值最小的记录，把它与第一个记录交换存储位置，使之成为有序。然后在余下的无序的记录中，再选出记录交换存储位置，使之成为有序。然后在余下的无序的记录中，再选出关键字最小的记录与无序区中的第一个记录交换位置，又使之成为有序。关键字最小的记录与无序区中的第一个记录交换位置，又使之成为有序。依此类推，直至完成整个排序。依此类推，直至完成整个排序。v10.4.1 10.4
14、.1 简单选择排序简单选择排序v基本思想基本思想:v(1)(1)初始状态：整个数组r划分成两个部分，即有序区（初始为空）和无序区。v(2)(2)基本操作：从无序区中选择关键字值为最小的记录，将其与无序区的第一个记录交换位置（实质是添加到有序区尾部。）v(3)(3)从初态（有序区为空）开始，重复步骤（2），直到终态（无序区为空）。v效率分析：效率分析：v简单选择排序是不稳定排序。v 第十七页，编辑于星期二：四点 六分。例例 如如第十八页，编辑于星期二：四点 六分。例：例：设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为6,8,7,9,0,1,3,2,4,5。说明采用直接
15、选择排序方法进行排序的过程。说明采用直接选择排序方法进行排序的过程。第十九页，编辑于星期二：四点 六分。10.4.2 10.4.2 堆排序堆排序 v堆排序是堆排序是利用堆树来进行排序的方法。堆树是一种特殊的完全二叉树，如果该利用堆树来进行排序的方法。堆树是一种特殊的完全二叉树，如果该完全二叉树中每一个结点的值均大于或等于它的两个子结点的值，则称其为完全二叉树中每一个结点的值均大于或等于它的两个子结点的值，则称其为大顶堆（或大根堆）；如果该完全二叉树中每一个结点的值均小于或等于它大顶堆（或大根堆）；如果该完全二叉树中每一个结点的值均小于或等于它的两个子结点的值，则称其为小顶堆（或小根堆）。的两个
16、子结点的值，则称其为小顶堆（或小根堆）。v基本思想：基本思想：v（1 1）建堆：）建堆：把用数组存储的把用数组存储的n n个待排序数据，看作成一棵完全二叉树的顺序个待排序数据，看作成一棵完全二叉树的顺序存储形式，并对这棵完全二叉树进行一系列的比较交换，将其建成一棵堆树。存储形式，并对这棵完全二叉树进行一系列的比较交换，将其建成一棵堆树。v（2 2）交换：）交换：将堆顶数据和当前待排序序列的最后那个数据相交换，堆顶数据即可排到其最终将堆顶数据和当前待排序序列的最后那个数据相交换，堆顶数据即可排到其最终位置，待排序数据从而减少一个。位置，待排序数据从而减少一个。v（3 3）调整：）调整：由于最后那
17、个数据交换到堆顶，它破坏了原有的堆结构，应将其不断向由于最后那个数据交换到堆顶，它破坏了原有的堆结构，应将其不断向下交换，直到剩余的待排序数据重新调整成一棵堆树。下交换，直到剩余的待排序数据重新调整成一棵堆树。v（4 4）不断重复（不断重复（2 2）（）（3 3）两步，直到待排序数据只剩下一个为止，此时所有数据即已排）两步，直到待排序数据只剩下一个为止，此时所有数据即已排成有序。成有序。第二十页，编辑于星期二：四点 六分。堆的定义堆的定义完全二叉树的数组表示完全二叉树的数组表示 Ki K2i+1&Ki K2i i+2 Ki K2i+1+1&Ki K2i+2+2第二十一页，编辑于星期二：四点 六
18、分。例v设待排序的结点键值序列为e=93,35,29,45,48,82,76,17,按上述思想形成如下图所示的初始堆。第二十二页，编辑于星期二：四点 六分。例例 设设 待待 排排 序序 的的 表表 有有 10个个 记记 录录,其其 关关 键键 字字 分分 别别 为为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程。说明采用堆排序方法进行排序的过程。第二十三页，编辑于星期二：四点 六分。堆排序过程：堆排序过程：第二十四页，编辑于星期二：四点 六分。第二十五页，编辑于星期二：四点 六分。10.5 10.5 归并排序归并排序v归并排序归并排序是将两个或两个以上的有序子表合并成
19、为一个新的有序是将两个或两个以上的有序子表合并成为一个新的有序表。表。v基本思想：基本思想：v（1）将）将n个记录的待排序序列看成是由个记录的待排序序列看成是由n个长度都个长度都1的有序的有序子表组成。子表组成。v（2）将两个相邻的子表归并为一个有序子表。）将两个相邻的子表归并为一个有序子表。v（3）重复上述步骤，直至归并为一个长度为）重复上述步骤，直至归并为一个长度为n的有序表。的有序表。第二十六页，编辑于星期二：四点 六分。归并排序的示例为：归并排序的示例为：(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13
20、,19,27)(01,16,26,31)(01,05,13,16,19,26,27,31)第二十七页，编辑于星期二：四点 六分。例例设待排序的表有设待排序的表有8个记录个记录,其关键字分别为其关键字分别为18,2,20,34,12,32,6,16。说明采用归并排序方法进行排序的过程。说明采用归并排序方法进行排序的过程。第二十八页，编辑于星期二：四点 六分。基数排序基数排序前前面面所所讨讨论论的的排排序序算算法法均均是是基基于于关关键键字字之之间间的的比比较较来来实实现现的的,而而基基数数排排序序是是通通过过“分分配配”和和“收收集集”过过程程来来实实现现排排序序,是是一一种种借借助助于于多多关
21、关键键字排序的思想对单关键字排序的方法。字排序的思想对单关键字排序的方法。第二十九页，编辑于星期二：四点 六分。例例设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为75,23,98,44,57,12,29,64,38,82。说明采用基数排序方法进行。说明采用基数排序方法进行排序的过程。排序的过程。第三十页，编辑于星期二：四点 六分。10.6 10.6 各种排序方法的比较各种排序方法的比较通常可按平均时间将排序方法分为三类：通常可按平均时间将排序方法分为三类：（1 1）平平方方阶阶O(nO(n2 2)排排序序，一一般般称称为为简简单单排排序序，例例如如直直接接插插入入、
22、直直接选择和冒泡排序；接选择和冒泡排序；（2 2）线性对数阶）线性对数阶O(nlogO(nlog2 2n)n)排序，如快速、堆和归并排序；排序，如快速、堆和归并排序；（3 3）线性阶）线性阶O(n)O(n)排序，如基数排序。排序，如基数排序。第三十一页，编辑于星期二：四点 六分。排序方法排序方法时间复杂度时间复杂度空间复杂度空间复杂度稳定性稳定性复杂性复杂性平均情况平均情况最坏情况最坏情况最好情况最好情况直接插入排序直接插入排序O(n2)O(n2)O(n)O(1)稳定稳定简单简单希尔排序希尔排序O(nlog2n)O(nlog2n)O(1)不稳定不稳定较复杂较复杂冒泡排序冒泡排序O(n2)O(n
23、2)O(n)O(1)稳定稳定简单简单快速排序快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定不稳定较复杂较复杂直接选择排序直接选择排序O(n2)O(n2)O(n2)O(1)不稳定不稳定简单简单堆排序堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定不稳定较复杂较复杂归并排序归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定稳定较复杂较复杂基数排序基数排序O(d(n+r)O(d(n+r)O(d(n+r)O(n+r)稳定稳定较复杂较复杂第三十二页，编辑于星期二：四点 六分。典型例题典型例题 v1.1.当文件局部有序或文件
24、长度较小的情况下，最佳的排当文件局部有序或文件长度较小的情况下，最佳的排序方法是序方法是()()。vA)A)直接插入排序直接插入排序 B)B)直接选择排序直接选择排序 C)C)冒泡排序冒泡排序 D)D)归并排序归并排序v 分析分析 在教材介绍的几种排序方法中，冒泡排序在教材介绍的几种排序方法中，冒泡排序算法里设置了一个标志，以判断某趟排序过程中，算法里设置了一个标志，以判断某趟排序过程中，待排序空间是否自然有序。因此它适用于局部有待排序空间是否自然有序。因此它适用于局部有序的文件。另外，冒泡排序属于内部排序，在文序的文件。另外，冒泡排序属于内部排序，在文件较小时，允许用内部排序算法进行排序，故
25、本件较小时，允许用内部排序算法进行排序，故本题的正确答案是题的正确答案是B)B)。v 答案答案B)B)第三十三页，编辑于星期二：四点 六分。v2.2.当初始序列已按键值有序时，用直接插入算法进行排序，当初始序列已按键值有序时，用直接插入算法进行排序，需要比较的次数为需要比较的次数为()()。vA)n-1 B)log2nA)n-1 B)log2n（注：（注：2 2是下标）是下标）C)2log2n C)2log2n（注：后一个（注：后一个2 2是下标）是下标）D)n2 D)n2（注：（注：2 2是上标）是上标）v 分析分析 直接插入排序是每趟从待排序空间取一个元素，按键值从直接插入排序是每趟从待排
26、序空间取一个元素，按键值从有序区间的尾部向前查找插入位置。当初始序列已按键值有序时，有序区间的尾部向前查找插入位置。当初始序列已按键值有序时，则每趟比较一次就找到了正确的插入位置。则每趟比较一次就找到了正确的插入位置。n n个元素进行个元素进行n-1n-1趟排趟排序，故总的比较次数是序，故总的比较次数是n-1n-1。v 答案答案A)A)典型例题典型例题 第三十四页，编辑于星期二：四点 六分。v3.3.快速排序在最坏情况下的时间复杂度是快速排序在最坏情况下的时间复杂度是()()。vA)O(log2n)A)O(log2n)（注：（注：2 2是下标）是下标）B)O(nlog2n)B)O(nlog2n
27、)（注：（注：2 2是下标）是下标）C)O(n2)C)O(n2)（注：（注：2 2是上标）是上标）D)O(n3)D)O(n3)（注：（注：3 3是上标）是上标）v 分析分析 当待排序空间事先已基本有序时，每趟快速排序当待排序空间事先已基本有序时，每趟快速排序后得到的左、右两个待排序小空间严重不对称，因此，后得到的左、右两个待排序小空间严重不对称，因此，差不多要进行差不多要进行n n趟次快速排序，每趟排序又要进行趟次快速排序，每趟排序又要进行n n级次级次数的比较，故最坏情况下，总的比较次数将达到数的比较，故最坏情况下，总的比较次数将达到O()O()。v 答案答案C)C)典型例题典型例题 第三十
28、五页，编辑于星期二：四点 六分。v4.4.用某种排序方法对序列用某种排序方法对序列(25,84,21,15,27,68,35,20)(25,84,21,15,27,68,35,20)进行排序，进行排序，记录序列的变化情况如下：记录序列的变化情况如下：v25 84 21 47 15 27 68 35 2025 84 21 47 15 27 68 35 20v20 15 21 25 47 27 68 35 8420 15 21 25 47 27 68 35 84v15 20 21 25 35 27 47 68 8415 20 21 25 35 27 47 68 84v15 20 21 25 27
29、35 47 68 8415 20 21 25 27 35 47 68 84v则采用的排序方法是则采用的排序方法是()()。vA)A)直接选择排序直接选择排序 B)B)冒泡排序冒泡排序 C)C)快速排序快速排序 D)D)二路归并排二路归并排序序v 答案答案C)C)典型例题典型例题 第三十六页，编辑于星期二：四点 六分。v5.5.在排序过程中，键值比较的次数与初始序列的排列顺序无关在排序过程中，键值比较的次数与初始序列的排列顺序无关的是的是()()。vA)A)直接插入排序和快速排序直接插入排序和快速排序 B)B)直接插入排序和归并排序直接插入排序和归并排序vC)C)直接选择排序和归并排序直接选择排
30、序和归并排序 D)D)快速排序和归并排序和归并排快速排序和归并排序和归并排序序v 分析分析 初始序列的排列顺序对直接插入排序和快速排序有初始序列的排列顺序对直接插入排序和快速排序有影响，而对直接选择排序和归并排序则没有影响，故正确影响，而对直接选择排序和归并排序则没有影响，故正确的答案是的答案是C)C)。v 答案答案C)C)典型例题典型例题 第三十七页，编辑于星期二：四点 六分。1、每一个成功者都有一个开始。勇于开始，才能找到成功的路。11月-2211月-22Wednesday,November 9,20222、成功源于不懈的努力，人生最大的敌人是自己怯懦。06:03:3606:03:3606
31、:0311/9/2022 6:03:36 AM3、每天只看目标，别老想障碍。11月-2206:03:3606:03Nov-2209-Nov-224、宁愿辛苦一阵子，不要辛苦一辈子。06:03:3606:03:3606:03Wednesday,November 9,20225、积极向上的心态，是成功者的最基本要素。11月-2211月-2206:03:3606:03:36November 9,20226、生活总会给你另一个机会，这个机会叫明天。09十一月20226:03:36上午06:03:3611月-227、人生就像骑单车，想保持平衡就得往前走。十一月226:03上午11月-2206:03November 9,20228、业余生活要有意义，不要越轨。2022/11/96:03:3606:03:3609 November 20229、我们必须在失败中寻找胜利，在绝望中寻求希望。6:03:36上午6:03上午06:03:3611月-2210、一个人的梦想也许不值钱，但一个人的努力很值钱。11/9/2022 6:03:36 AM06:03:3609-11月-2211、在真实的生命里，每桩伟业都由信心开始，并由信心跨出第一步。11/9/2022 6:03 AM11/9/2022 6:03 AM11月-2211月-22谢谢大家谢谢大家第三十八页，编辑于星期二：四点 六分。