数据结构预算法第十章排序hard.pptx

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

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)关键字值为ASCII码，则按键值的内码编排顺序为依

2、据。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.基本思想：基本思想：直接插入排序是将一个记录插入到已排序好的直接插入排序是将一个记录插入到已排序好的有序表中，从而得到一个新的，记录数增有序表中，从而得到一个新的，记录数增1 1

4、的有序表。的有序表。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.监视哨的作用：监视哨的作用：v（1 1）在进入确定插入位置的循环之前，保存了插入值）在进入确定插入位置的循环之前，保存了插入值riri的副本，避免因记录的移

5、动而丢失的副本，避免因记录的移动而丢失riri中的内容。中的内容。v（2 2）使内循环总能够结束，以免循环过程中数组下标越界。）使内循环总能够结束，以免循环过程中数组下标越界。v3.3.效率分析效率分析v直接插入排序是稳定排序，最适合待排序关键字基本有序的直接插入排序是稳定排序，最适合待排序关键字基本有序的序列。时间复杂度序列。时间复杂度O(),O(),辅助空间为辅助空间为O(1)O(1)。例例设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用直接插入排序方法进行排。说明采用直接插入排序方法进行排序的过程。序的过程。v10

6、.2.2 二分插入排序highlowi插入位置5861 23 97 751436495280imm14364952586180 23 97 75high low插入位置imm14364952586180 23 97 75high low插入位置v1.1.基本思想：基本思想：v直接插入排序算法虽简单，但当记录数量大时，则比较次数将大大增加，对于有序表，为了减少关键字的比较次数，可采用二分插入排序。v2.2.效率分析效率分析v二分插入排序是稳定的排序。时间复杂度和空间复杂度和直接插入排序的一样。v10.2.3 10.2.3 希尔排序希尔排序v希尔排序又称希尔排序又称“缩小增量排序缩小增量排序”，它

7、也是一种插入排，它也是一种插入排序的方法，但时间上比前两种排序方法有比较大的改序的方法，但时间上比前两种排序方法有比较大的改进。进。v1.1.基本思想：基本思想：先将整个待排序记录序列分割成若干个子序列分别进行直接插入排序，待整个序列中的记录“基本有序时”，再对全体记录进行一次直接插入排序。v2.2.特点：特点：子序列不是简单的逐段分割，而是将相隔某个“增量”的记录组成一个子序列，所以关键字较小的记录不是一步一步地前移，而是跳跃式前移，从而使得在进行最后一趟增量为1的插入排序时，序列已基本有序。v3.3.效率分析：效率分析：v 希尔排序是一种不稳定排序。例如：例如：16 25 12 30 47

8、 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第三趟希尔排序，设增量第三趟希尔排序，设增量 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。说说明明采采用用希希尔尔排排序序方方法法进进行行

9、排排序序的的过程。过程。10.3 10.3 快速排序快速排序v快速排序又称为交换排序，是根据记录的关键字的大小，通快速排序又称为交换排序，是根据记录的关键字的大小，通过记录交换来实现排序的。过记录交换来实现排序的。v10.3.1.10.3.1.冒泡排序冒泡排序v1.1.基本思想：基本思想：冒泡排序也称沉底法，每相邻两个记录关键字冒泡排序也称沉底法，每相邻两个记录关键字比较大小，大的记录往下沉（也可以小的往上浮）。每一遍比较大小，大的记录往下沉（也可以小的往上浮）。每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生

10、下沉时，整个过程结束（每交换一次，到所有记录都不发生下沉时，整个过程结束（每交换一次，记录减少一个反序数）。记录减少一个反序数）。v2.2.效率分析：效率分析：v冒泡排序是一种稳定排序。冒泡排序是一种稳定排序。例如：例如：例例设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为9,8,7,6,5,4,3,2,1,0。说明采用冒泡排序方法进行排序的。说明采用冒泡排序方法进行排序的过程。过程。v10.3.2 10.3.2 快速排序快速排序v1.1.基本思想：基本思想：任取待排序序列中的某个元素作为基准，通任取待排序序列中的某个元素作为基准，通过一趟快速排序将待排序的元素分割成

11、左右两个子序列，过一趟快速排序将待排序的元素分割成左右两个子序列，其中左子序列元素的排序关键字均比基准（也称为枢轴）其中左子序列元素的排序关键字均比基准（也称为枢轴）元素的关键字值小；右子序列元素的关键字均比基准元素元素的关键字值小；右子序列元素的关键字均比基准元素的关键字值大，基准元素得到了它在整个序列中的最终位的关键字值大，基准元素得到了它在整个序列中的最终位置并被存放好，这个过程称为一趟快速排序。置并被存放好，这个过程称为一趟快速排序。v2.2.效率分析：效率分析：v快速排序是不稳定排序。快速排序是不稳定排序。例例 设设 待待 排排 序序 的的 表表 有有 10个个 记记 录录,其其 关

12、关 键键 字字 分分 别别 为为6,8,7,9,0,1,3,2,4,5。说说明明采采用用快快速速排排序序方方法法进进行行排排序序的的过程。过程。10.4 10.4 选择排序选择排序v选择排序选择排序是从待排序序列中选取一个关键字值最小的记录，是从待排序序列中选取一个关键字值最小的记录，把它与第一个记录交换存储位置，使之成为有序。然后在余把它与第一个记录交换存储位置，使之成为有序。然后在余下的无序的记录中，再选出关键字最小的记录与无序区中的下的无序的记录中，再选出关键字最小的记录与无序区中的第一个记录交换位置，又使之成为有序。依此类推，直至完第一个记录交换位置，又使之成为有序。依此类推，直至完成

13、整个排序。成整个排序。v10.4.1 10.4.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。说明采用直接选择排序方法进行排。说明采

14、用直接选择排序方法进行排序的过程。序的过程。10.4.2 10.4.2 堆排序堆排序 v堆排序是堆排序是利用堆树来进行排序的方法。堆树是一种特殊的完全二叉树，利用堆树来进行排序的方法。堆树是一种特殊的完全二叉树，如果该完全二叉树中每一个结点的值均大于或等于它的两个子结点的值，如果该完全二叉树中每一个结点的值均大于或等于它的两个子结点的值，则称其为大顶堆（或大根堆）；如果该完全二叉树中每一个结点的值均则称其为大顶堆（或大根堆）；如果该完全二叉树中每一个结点的值均小于或等于它的两个子结点的值，则称其为小顶堆（或小根堆）。小于或等于它的两个子结点的值，则称其为小顶堆（或小根堆）。v基本思想：基本思想

15、：v（1 1）建堆：）建堆：把用数组存储的把用数组存储的n n个待排序数据，看作成一棵完全二叉树的个待排序数据，看作成一棵完全二叉树的顺序存储形式，并对这棵完全二叉树进行一系列的比较交换，将其建成顺序存储形式，并对这棵完全二叉树进行一系列的比较交换，将其建成一棵堆树。一棵堆树。v（2 2）交换：）交换：将堆顶数据和当前待排序序列的最后那个数据相交换，堆顶将堆顶数据和当前待排序序列的最后那个数据相交换，堆顶数据即可排到其最终位置，待排序数据从而减少一个。数据即可排到其最终位置，待排序数据从而减少一个。v（3 3）调整：）调整：由于最后那个数据交换到堆顶，它破坏了原有的堆结构，应由于最后那个数据交

16、换到堆顶，它破坏了原有的堆结构，应将其不断向下交换，直到剩余的待排序数据重新调整成一棵堆树。将其不断向下交换，直到剩余的待排序数据重新调整成一棵堆树。v（4 4）不断重复（不断重复（2 2）（）（3 3）两步，直到待排序数据只剩下一个为止，此时）两步，直到待排序数据只剩下一个为止，此时所有数据即已排成有序。所有数据即已排成有序。堆的定义堆的定义完全二叉树的数组表示完全二叉树的数组表示 Ki K2i+1&Ki K2i+2 Ki K2i+1&Ki K2i+2例v设待排序的结点键值序列为e=93,35,29,45,48,82,76,17,按上述思想形成如下图所示的初始堆。例例 设设 待待 排排 序序

17、 的的 表表 有有 10个个 记记 录录,其其 关关 键键 字字 分分 别别 为为6,8,7,9,0,1,3,2,4,5。说明采用堆排序方法进行排序的过程。说明采用堆排序方法进行排序的过程。堆排序过程：堆排序过程：10.5 10.5 归并排序归并排序v归并排序归并排序是将两个或两个以上的有序子表合并成为一是将两个或两个以上的有序子表合并成为一个新的有序表。个新的有序表。v基本思想：基本思想：v（1）将）将n个记录的待排序序列看成是由个记录的待排序序列看成是由n个长度都个长度都1的的有序子表组成。有序子表组成。v（2）将两个相邻的子表归并为一个有序子表。）将两个相邻的子表归并为一个有序子表。v（

18、3）重复上述步骤，直至归并为一个长度为）重复上述步骤，直至归并为一个长度为n的有序的有序表。表。归并排序的示例为：归并排序的示例为：(19)(13)(05)(27)(01)(26)(31)(16)(13,19)(05,27)(01,26)(16,31)(05,13,19,27)(01,16,26,31)(01,05,13,16,19,26,27,31)例例设待排序的表有设待排序的表有8个记录个记录,其关键字分别为其关键字分别为18,2,20,34,12,32,6,16。说明采用归并排序方法进行排。说明采用归并排序方法进行排序的过程。序的过程。基数排序基数排序前前面面所所讨讨论论的的排排序序算算

19、法法均均是是基基于于关关键键字字之之间间的的比比较较来来实实现现的的,而而基基数数排排序序是是通通过过“分分配配”和和“收收集集”过过程程来来实实现现排排序序,是是一一种种借借助助于于多多关关键键字字排排序序的的思思想想对对单单关关键键字字排排序序的的方方法。法。例例设待排序的表有设待排序的表有10个记录个记录,其关键字分别为其关键字分别为75,23,98,44,57,12,29,64,38,82。说明采用基数排序方。说明采用基数排序方法进行排序的过程。法进行排序的过程。10.6 10.6 各种排序方法的比较各种排序方法的比较通常可按平均时间将排序方法分为三类：通常可按平均时间将排序方法分为三

20、类：（1 1）平平方方阶阶O(nO(n2 2)排排序序，一一般般称称为为简简单单排排序序，例例如如直直接接插插入入、直接选择和冒泡排序；直接选择和冒泡排序；（2 2）线性对数阶）线性对数阶O(nlogO(nlog2 2n)n)排序，如快速、堆和归并排序；排序，如快速、堆和归并排序；（3 3）线性阶）线性阶O(n)O(n)排序，如基数排序。排序，如基数排序。排序方法排序方法时间复杂度时间复杂度空间复杂度空间复杂度稳定性稳定性复杂性复杂性平均情况平均情况最坏情况最坏情况最好情况最好情况直接插入排序直接插入排序O(n2)O(n2)O(n)O(1)稳定稳定简单简单希尔排序希尔排序O(nlog2n)O(

21、nlog2n)O(1)不稳定不稳定较复杂较复杂冒泡排序冒泡排序O(n2)O(n2)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)稳定稳定较复杂较复杂典型例题

22、典型例题 v1.1.当文件局部有序或文件长度较小的情况下，最当文件局部有序或文件长度较小的情况下，最佳的排序方法是佳的排序方法是()()。vA)A)直接插入排序直接插入排序 B)B)直接选择排序直接选择排序 C)C)冒泡排序冒泡排序 D)D)归并排序归并排序v 分析分析 在教材介绍的几种排序方法中，冒泡排序在教材介绍的几种排序方法中，冒泡排序算法里设置了一个标志，以判断某趟排序过程算法里设置了一个标志，以判断某趟排序过程中，待排序空间是否自然有序。因此它适用于中，待排序空间是否自然有序。因此它适用于局部有序的文件。另外，冒泡排序属于内部排局部有序的文件。另外，冒泡排序属于内部排序，在文件较小时

23、，允许用内部排序算法进行序，在文件较小时，允许用内部排序算法进行排序，故本题的正确答案是排序，故本题的正确答案是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 分析分析 直接插入排序是每趟从待排序空间取一个元直接插入排序是每趟从待排序空间取一

24、个元素，按键值从有序区间的尾部向前查找插入位置。素，按键值从有序区间的尾部向前查找插入位置。当初始序列已按键值有序时，则每趟比较一次就找当初始序列已按键值有序时，则每趟比较一次就找到了正确的插入位置。到了正确的插入位置。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)（注：（注：2 2是下标）是下标）

25、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)典型例题典型例题 v4.4.用某种排序方法对序列用某种排序方

26、法对序列(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 35 47 68 8415 20 21 25 27 35 47 68 84

27、v则采用的排序方法是则采用的排序方法是()()。vA)A)直接选择排序直接选择排序 B)B)冒泡排序冒泡排序 C)C)快速排序快速排序 D)D)二二路归并排序路归并排序v 答案答案C)C)典型例题典型例题 v5.5.在排序过程中，键值比较的次数与初始序列的排在排序过程中，键值比较的次数与初始序列的排列顺序无关的是列顺序无关的是()()。vA)A)直接插入排序和快速排序直接插入排序和快速排序 B)B)直接插入排序和归直接插入排序和归并排序并排序vC)C)直接选择排序和归并排序直接选择排序和归并排序 D)D)快速排序和归并排快速排序和归并排序和归并排序序和归并排序v 分析分析 初始序列的排列顺序对直接插入排序和快速初始序列的排列顺序对直接插入排序和快速排序有影响，而对直接选择排序和归并排序则没有排序有影响，而对直接选择排序和归并排序则没有影响，故正确的答案是影响，故正确的答案是C)C)。v 答案答案C)C)典型例题典型例题