数据结构讲义第10章排序ppt课件.ppt

第10章排序 10 1概述10 2插入排序10 3选择排序10 4交换排序10 5分配排序10 6归并排序 1 10 1概述 1 排序的定义为了便于查找 通常希望计算机中的数据表是按关键码有序的 如有序表的折半查找 查找效率较高 还有 二叉排序树 B 树和B 树的构造过程就是一个排序过程 2 10 1概述 1 排序的定义排序 sorting 是计算机程序设计中的一种重要操作 其功能是对一个数据元素集合或序列重新排列成一个按关键码有序的序列 3 10 1概述 1 排序的定义 1 排序的定义 假设 R1 R2 Rn 是由n个记录组成的文件 K1 K2 Kn 是排序码集合 所谓排序是将记录按排序码递增 或递减 的排列 排序码可以是主关键码 也可以是次关键码 2 稳定性假设Ki Kj 1 i j n i j 且在排序前的序列中Ri领先于Rj 即i j 若在排序后的序列中Ri仍领先于Rj 则称所用的排序方法是稳定的 否则是不稳定的 4 10 1概述 1 排序的定义 3 排序的分类 待排序的记录在排序过程中全部存放在内存的称为内排序 如果排序过程中需要使用外存的称为外排序 按排序原则 排序分为 1 插入排序 2 选择排序 3 交换排序 4 分配排序 5 归并排序 6 外部排序按排序所需的工作量 排序分为 1 简单排序方法 其时间复杂度为O n2 2 先进的排序方法 其时间复杂度为O nlogn 3 基数排序 其时间复杂度为O d n 5 10 1概述 1 排序的定义 4 排序中的基本操作 i 比较关键码大小ii 移动记录 5 对于待排序的记录序列 有三种常见的存储表示方法 向量结构 即将待排序的记录存放在一组地址连续的存储单元中 链表结构 记录向量与地址向量结合 即将待排序记录存放在一组地址连续的存储单元中 同时另设一个指示各个记录位置的地址向量 6 10 1概述 1 排序的定义为简单起见 数据的存储结构采取向量的存储结构 definen20 记录数typedefintkeytype typedefstruct keytypekey datatypeother rectype rectyper n 1 7 10 1概述 1 排序的定义 6 排序算法的评价 i 算法的执行时间ii 算法执行时所需的附加空间 8 10 2插入排序 基本原理 每步将一个待排序的对象 按其关键字大小 插入到前面已经排好序的一组对象适当位置上 直到对象全部插入为止 9 10 2插入排序 10 2 1直接插入排序1 直接插入排序的基本思想先假定第1个记录为有序序列 然后从第2条记录开始 依次将记录插入到前面已经有序的序列中 直至全部记录有序 一般情况下 第i趟直接插入排序 将r i 插入到已经有序的序列r 1 i 1 中 使其变成有序序列r 1 i 整个排序进行n 1趟插入 10 10 2插入排序 10 2 1直接插入排序2 示例 初始 49 38659776132749 i 1 3849 659776132749 i 5 133849657697 2749 i 3 38496597 76132749 i 2 384965 9776132749 i 4 3849657697 132749 i 6 13273849657697 49 i 7 1327384949657697 11 10 2插入排序 10 2 1直接插入排序3 算法 voidInsertSort rectypeR intn inti j for i 2 i n i R 0 R i for j i 1 R 0 key R j key j R j 1 R j R j 1 R 0 12 10 2插入排序 10 2 1直接插入排序4 算法分析 空间效率 只需要一个记录的辅助空间 时间效率 比较记录的次数为 最小 n 1次 最大 n 2 n 1 2次移动记录的次数 最小 2 n 1 最大 n 4 n 1 2平均情况 O n2 13 10 2插入排序 10 2 2折半插入排序1 折半插入排序 将直接插入排序的查找过程改用折半查找 由此实现的排序称为二分法插入排序 14 10 2插入排序 10 2 2折半插入排序2 示例 1 1327384965769749low 1mid 4high 7 2 1327384965769749low 5mid 6high 7 3 1327384965769749low 5mid 5high 5 49 high 已找到插入位置low 5 4 1327384949657697 15 10 2插入排序 10 2 2折半插入排序3 算法 voidBinInsertSort rectyper intn for i 2 i low j r j 1 r j 记录后移 r low x 插入记录 16 10 2插入排序 10 2 2折半插入排序4 算法分析 算法分析 空间效率 同直接插入排序时间效率 比较次数确定 n log2i n log2ni 1移动记录次数 平均移动次数为O n2 时间复杂度为O n2 17 10 2插入排序 10 2 3希尔排序 Shell sSort 1 希尔排序 shell排序又称缩小增量排序 DiminishingIncrementSort 先将整个待排记录序列分割成若干个子序列分别进行直接插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次直接插入排序 就可以完成整个的排序工作 利用下面两点 当n很小时 直接插入排序的效率较高 当待排记录序列基本有序时 直接插入排序的效率也较高 shell排序对直接插入排序算法进行改进 18 10 2插入排序 10 2 3希尔排序 Shell sSort 2 示例 原始序列4938659713762749 1 d 4 2 d 213382749 49766597 3 d 113382749 49766597 排序结果13273849 49657697 19 10 2插入排序 10 2 3希尔排序 Shell sSort 3 算法 voidshellSort rectyper intn intd intk for l 0 l0 20 10 2插入排序 10 2 3希尔排序 Shell sSort 4 算法分析 Shell排序的平均比较次数和平均移动次数都为O n1 3 左右Shell排序算法中增加了一个辅助空间 Shell排序是不稳定的 21 10 3交换排序 交换排序基本思想 两两比较待排序记录的排序码 交换不满足排序要求的偶对 直到全部有序 22 10 3交换排序 10 3 1冒泡排序 BubbleSort 1 基本思想 设待排序记录顺序存放在R1 R2 R3 Rn中 依次比较 R1 R2 R2 R3 Rn 1 Rn 不满足顺序则交换 结果 最大者在Rn中 这叫一次起泡 此后 再对存放在R1 R2 R3 Rn 1中n 1个记录作同样处理 结果 最大者在Rn 1中 n 1次起泡能完成排序 设置标志noswap表示本次起泡是否有交换 若无交换 表示排序完成 23 10 3交换排序 10 3 1冒泡排序 BubbleSort 2 示例 3849657613274997 4938659776132749 3849651327497697 3849132749657697 3813274949657697 1327384949657697 1327384949657697 初始123456 24 10 3交换排序 10 3 1冒泡排序 BubbleSort 3 算法 voidbubbleSort rectypeR intn i 1 flag 1 for i 1 iR j 1 key temp R j 1 R j 1 R j R j temp flag 1 25 10 3交换排序 10 3 1冒泡排序 BubbleSort 4 算法分析 起泡排序的最坏时间复杂度为O n2 平均时间复杂度为O n2 起泡排序算法中增加一个辅助空间temp 辅助空间为S n O 1 起泡排序是稳定的 26 10 3交换排序 10 3 2快速排序 QuickSort 1 基本思想 快速排序的基本思想是 从待排序记录序列中选取一个记录 通常选取第一个记录 作为 枢轴 通过一趟排序 一次划分 将待排记录分割成独立的两部分 其中一部分记录的关键字比枢轴小 另一部分记录的关键字比枢轴大 然后则可分别对这两部分记录继续进行划分 以达到整个序列有序 27 10 3交换排序 10 3 2快速排序 QuickSort 1 基本思想 一趟快速排序 一次划分 的具体做法是 附设两个指针low和high 它们的初值分别是一个序列的第一个和最后一个记录的位置 设枢轴记录的关键字为pivotKey 在首先从high所指位置起向前搜索直到第一个关键字小于pivotKey的记录和枢轴记录交换 然后从low所指位置起向后搜索 找到第一个关键字大于pivotKey的记录和枢轴记录互相交换 重复交替这两步直到low high为止 28 10 3交换排序 10 3 2快速排序 QuickSort 2 示例 设记录的关键码序列为 4938659776132749对其进行快速排序 29 10 3交换排序 10 3 2快速排序 QuickSort 3 算法 intPartition rectypeR intn intlow inthigh pivotkey R low key while low pivotkey high r low r high while low high 30 10 3交换排序 10 3 2快速排序 QuickSort 3 算法 voidQSort rectypeR intn intlow inthigh if low high pivotloc Partition R n low high QSort R low pivotloc 1 QSort R pivotloc 1 high voidQuickSort rectypeR intn QSort R n 1 n 31 10 3交换排序 10 3 2快速排序 QuickSort 4 算法分析 最坏情况下 即当初始序列已经有序时 快速排序退化为起泡排序 为O n2 最好时间复杂度为O nlog2n 平均时间复杂度是T n O nlog2n 算法需要一个栈空间实现递归 栈的大小取决于递归调用的深度 最多不超过n 理想情况下不超过log2n 所以快速排序的辅助空间最坏为S n O n 最好为S n O log2n 快速排序是不稳定的 32 10 4选择排序 选择排序 SelectionSort 的基本思想是 每一趟在n i 1 i 1 2 n 1 个记录中选取关键字最小的记录作为有序序列中第i个记录 33 10 4选择排序 10 4 1简单选择排序 SimpleSelectionSort 1 基本思想 第i趟简单选择排序是指通过n i次关键字的比较 从n i 1个记录中选出关键字最小的记录 并和第i个记录进行交换 共需进行i 1趟比较 直到所有记录排序完成为止 34 10 4选择排序 10 4 1简单选择排序 SimpleSelectionSort 2 示例 4938659749132776 13 38659749492776 1327 659749493876 132738 9749496576 13273849 97496576 1327384949 976576 132738494965 9776 13273849496576 97 1327384949657697 35 10 4选择排序 10 4 1简单选择排序 SimpleSelectionSort 3 算法 voidSelectSort rectypeR intn for i 1 i n 1 i k i for j i 1 j n j if R j key R k key k j if k i temp R i R i R k R k temp 36 10 4选择排序 10 4 1简单选择排序 SimpleSelectionSort 4 算法分析 直接选择排序的比较次数与文件初始状态无关 直接选择排序的时间复杂度 移动 最好 0最坏 3 n 1 比较 n n 1 2总的时间复杂度 O n2 稳定性 不稳定 37 10 4选择排序 10 4 1简单选择排序 SimpleSelectionSort 4 算法分析 直接选择排序的比较次数与文件初始状态无关 直接选择排序的时间复杂度 移动 最好时 0最坏时 3 n 1 比较 n n 1 2总的时间复杂度 O n2 稳定性 不稳定 38 10 4选择排序 10 4 2树形选择排序 TreeSelectionSort 1基本思想 简单选择排序的主要操作是比较 要提高它的速度必须减少比较的次数 而实际上如果能利用以前的比较结果则可以提高排序速度 树形选择排序 TreeSelectionSort 又称锦标赛排序 Tournamentsort 其方法是 首先对n个记录的关键字进行两两比较 然后在 n 2 个较小者之间再进行两两比较 如此重复直到选出最小关键字的记录为止 然后对剩下的记录作同样的操作 选出具有次小关键字的记录 这个过程可以用一个完全二叉树来表示 39 10 4选择排序 10 4 2树形选择排序 TreeSelectionSort 2示例 40 10 4选择排序 10 4 2树形选择排序 TreeSelectionSort 2示例 41 10 4选择排序 10 4 2树形选择排序 TreeSelectionSort 3算法分析 在树型选择排序中 含有n个叶子节点的完全二叉树的深度为 log2n 1 则在树型选择排序中 每选择一个小关键字需要进行 log2n 次比较 因此其时间复杂度为O nlog2n 移动记录次数不超过比较次数 故总的算法时间复杂度为O nlog2n 缺点是使用了较多的辅助空间 n 1 并且和 最大值 进行了多余的比较 42 10 4选择排序 10 4 3堆排序 HeapSort 1堆的定义 堆排序是对树型选择排序的进一步改进 采用堆排序时 只需要一个记录大小的辅助空间 1964年Willioms提出了堆排序 堆的定义 n个元素的序列 k1 k2 kn 当且仅当满足如下关系时 称之为堆 ki k2iki k2iki k2i 1ki k2i 1 i 1 2 n 2 43 10 4选择排序 10 4 3堆排序 HeapSort 1堆的定义 堆的示例 若将和此序列对应的一维数组看成是一个完全二叉树 则堆的含义表明 完全二叉树中所有非终端结点的值均不小于 或不大于 其左右孩子结点的值 a 大根堆 b 小根堆 44 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 若序列 k1 k2 kn 是堆 则堆顶元素必为序列中n个元素的最大值 或最小值 如果在输出堆顶的最大值后 使得剩余n 1个元素的序列重又建成一个堆 则得到次大值 反复执行便能得到所有记录的有序序列 这个过程称为堆排序 45 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 现在剩下两个问题 1 如何由一个无序序列建成一个堆 2 如何在输出堆顶元素后 调整剩余元素为一个新的堆 46 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 问题1 当堆顶元素改变时 如何重建堆 筛选 法调整成堆 97 38 27 49 76 65 49 13 27 38 49 49 76 65 97 13 a 堆 b 13和97交换后的情形 c 调整后的新堆 47 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 问题2 如何由一个任意序列建初堆 一个任意序列看成是对应的完全二叉树 由于叶结点可以视为单元素的堆 因而可以反复利用 筛选 法 自底向上逐层把所有子树调整为堆 直到将整个完全二叉树调整为堆 48 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 对无序序列 49 38 65 97 76 13 27 49 建堆示例 49 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 对无序序列 49 38 65 97 76 13 27 49 建堆示例 50 10 4选择排序 10 4 3堆排序 HeapSort 2堆排序的基本思想 问题3 如何利用堆进行排序 进行堆排序的步骤 将待排序记录按照堆的定义建初堆 并输出堆顶元素 调整剩余的记录序列 利用筛选法将前n i个元素重新筛选建成为一个新堆 再输出堆顶元素 重复执行步骤 n 1次进行筛选 新筛选成的堆会越来越小 而新堆后面的有序关键字会越来越多 最后使待排序记录序列成为一个有序的序列 这个过程称之为堆排序 51 例 初始序列为26 5 77 1 61 11 59 15 48 19 26 05 77 01 61 11 59 15 48 19 1 初始完全二叉树 26 05 77 01 61 11 59 15 48 19 2 调整序号为4的结点 52 26 05 77 48 61 11 59 15 01 19 3 调整序号为3的结点 26 05 77 48 61 11 59 15 01 19 4 调整序号为2的结点 53 26 61 77 48 19 11 59 15 01 05 5 调整序号为1的结点 77 61 59 48 19 11 26 15 01 05 6 调整序号为0的结点 54 05 61 59 48 19 11 26 15 01 77 7 结点77与结点5互换 61 59 15 19 11 26 05 01 77 8 重建堆 48 55 9 结点61与结点1互换 59 26 15 19 11 01 05 61 77 10 重建堆 48 01 59 15 19 11 26 05 61 77 48 56 11 结点59与结点05互换 05 26 15 19 11 01 59 61 77 12 重建堆 48 48 26 15 05 11 01 59 61 77 19 57 12 结点48与结点1互换 13 重建堆 01 26 15 05 11 48 59 61 77 19 26 11 15 05 01 48 59 61 77 19 58 15 结点26与结点1互换 16 重建堆 01 11 15 05 26 48 59 61 77 19 19 11 01 05 26 48 59 61 77 15 59 17 结点19与结点5互换 18 重建堆 05 11 01 19 26 48 59 61 77 15 15 11 01 19 26 48 59 61 77 05 60 19 结点15与结点1互换 20 重建堆 01 11 15 19 26 48 59 61 77 05 11 01 15 19 26 48 59 61 77 05 61 10 4选择排序 10 4 3堆排序 HeapSort 3算法 voidSift rectypeR ints intm 筛选算法temp R s for j 2 s j R j key break R s R j s j R s temp 62 10 4选择排序 10 4 3堆排序 HeapSort 3算法 堆排序算法voidHeapSort rectypeR intn for i n 2 i 1 i 初始建堆Sift R i n for i n i 1 i temp R 1 R 1 R i R i temp Sift R 1 i 1 63 10 4选择排序 10 4 3堆排序 HeapSort 4算法分析 初始建堆比较次数为 O n 排序中比较次数为 O n log2n 移动次数小于比较次数 在最坏的情况下 时间复杂度也是O nlogn 且仅需一个记录大小的辅助空间 堆排序适用于n值较大的情况 堆排序是不稳定的排序方法 64 10 5归并排序 10 5 1归并排序 MergingSort 1基本思想 归并的含义是将两个或两个以上的有序表合并成一个有序表 利用归并的思想就可以实现排序 假设初始的序列含有n个记录 可以看成n个有序的子序列 每个子序列的长度为1 然后两两归并 得到 n 2 个长度为2或1的有序子序列 再两两归并 如此重复直到得到一个长度为n的有序序列为止 这种排序方法称为二路归并排序 65 10 5归并排序 10 5 1归并排序 MergingSort 2示例 初始序列为25 57 48 37 12 82 75 29 16 请用二路归并排序法排序 初始排序码255748371282752916 第一趟归并后255737481282297516 第二趟归并后253748571229758216 第三趟归并后122529374857758216 第四趟归并后121625293748577582排序后的结果为 12 16 25 29 37 48 57 75 82 66 10 5归并排序 10 5 1归并排序 MergingSort 3算法 voidMerge rectypeR rectypeR1 intlow intmid inthigh i low j mid 1 k low while i mid 67 10 5归并排序 10 5 1归并排序 MergingSort 3算法 voidMSort rectypeR rectypeR1 ints intt if s t r1 s r s else m s t 2 MSort R R2 s m MSort R R2 m 1 t Merge r2 r1 s m t voidMergeSort rectypeR intn MSort r r 1 n 68 10 5归并排序 10 5 1归并排序 MergingSort 4算法分析 时间复杂度 O nlog2n 空间复杂度 和待排记录等量的空间 二路归并算法是稳定的 一般情况下很少用于内部排序 69 10 6分配排序 10 6 1概述 分配类排序则利用分配和收集两种基本操作 基数类排序就是典型的分配类排序 分配排序的思想是把排序码分解成若干部分 然后通过对各个部分排序码的分别排序 最终达到整个排序码的排序 70 10 6分配排序 10 6 1概述 一般情况下 假设文件F有n个记录F R0 R1 Rn 1 且每个记录Ri的排序码中含有d个部分 ki0 ki1 kid 1 则文件F对排序码 k0 k1 kd 1 有序是指 文件中任意两个记录Ri和Rj 0 i j n 1 满足词典次序有序关系 ki0 ki1 kid 1 kj0 kj1 kjd 1 其中k0称为最高位排序码 kd 1称为最低位排序码 实现分配排序 有两种方法 第一种是先对最高位排序码k0排序 称为最高位优先法 MostSignificantDigitfirst 第二种是先对最低位排序码kd 1排序 称为最低位优先法 LeastSignificantDigitfirst 71 10 6分配排序 10 6 1概述 例如 我们可以将一副扑克牌的排序过程看成由花色和面值两个关键字进行排序的问题 若规定花色和面值的顺序如下 花色 梅花 方块 红桃 黑桃面值 A 2 3 10 J Q K并进一步规定花色的优先级高于面值 则一副扑克牌从小到大的顺序为 梅花A 梅花2 梅花K 方块A 方块2 方块K 红桃A 红桃2 红桃K 黑桃A 黑桃2 黑桃K 72 10 6分配排序 10 6 1概述 最高位优先 先按花色分成有序的四类 然后再按面值对每一类从小到大排序 最低位优先 先按面值从小到大把牌摆成13叠 每叠4张牌 然后将每叠牌按面值的次序收集到一起 再对这些牌按花色摆成4叠 每叠有13张牌 最后把这4叠牌按花色的次序收集到一起 于是就得到了有序序列 73 10 6分配排序 10 6 1概述 低位优先法比高位优先法简单 高位优先排序必须将文件逐层分割成若干子文件 然后各子文件独立排序 低位优先排序不必分成子堆 对每个排序码都是整个文件参加排序 且可通过若干次 分配 和 收集 实现排序 但对Ki 0 i d 2 进行排序时 只能用稳定的排序方法 下面将介绍的基数排序就是用排序码低位优先法的思想对排序码进行分解后排序的一种方法 74 10 6分配排序 10 6 2链式基数排序 采用基