数据结构第9章.ppt

2 第9章排序 学习目标与要求 了解排序的定义 熟练掌握各种排序方法的基本思想 掌握各种排序方法时间复杂度的分析方法 并能分析各种排序方法在何种情况下使用 掌握各种排序方法的稳定性 3 9 1基本概念 排序是数据结构中一种非常重要且最为常用的一种技术 它在计算机的其它领域应用也非常广泛 在对数据进行处理的过程中 对数据进行排序是不可避免的 排序按照内存和外存的使用情况 可分为内排序和外排序 本章主要学习内排序 4 9 1基本概念 排序 把一个无序的元素序列按照元素的关键字递增或递减排列为有序的序列 稳定排序和不稳定排序 若对任意的数据元素序列 使用某个排序方法 对它按关键字进行排序 若对原先具有相同键值元素间的位置关系 排序前与排序后保持一致 称此排序方法是稳定的 反之 则称为不稳定的 5 9 1基本概念 例如 对数据键值为 5 3 8 3 6 6 排序 若排序后的序列为 3 3 5 6 6 8 其相同键值的元素位置依旧是3在3前 6在6前 与排序前保持一致 则表示这种排序法是稳定的 若排序后的序列为 3 3 5 6 6 8 则表示这种排序法是不稳定的 6 9 1基本概念 内排序和外排序 根据排序过程中 所利用的内存储器和外存储器的情况 将排序分为两类 内部排序和外部排序 内排序是指需要排序的元素数量不是特别大 在排序的过程中完全在内存中进行的方法 外排序是指需要排序的数据量非常大 在内存中不能一次完成排序 需要不断地在内存和外存中交替才能完成的排序 7 9 1基本概念 内排序的方法有许多 按照排序过程中采用的策略将排序分为几个大类 插入排序 选择排序 交换排序和归并排序 这些排序方法各有优点和不足 在使用时 可根据具体情况选择比较合适的方法 8 9 1基本概念 在排序过程中 主要需要以下两种基本操作 1 比较两个元素相应关键字的大小2 将元素从一个位置移动到另一个位置 9 待排序的元素的存储结构有三种方式 1 顺序存储 将待排序的元素存储在一组连续的存储单元中 这类似于线性表的顺序存储 元素E1和E2逻辑上相邻 其物理位置也相邻 在排序过程中 需要移动元素 9 1基本概念 10 待排序的元素的存储结构有三种方式 2 链式存储 将待排序元素存储在一组不连续的存储单元中 这类似于线性表的链式存储 元素E1和E2逻辑上相邻 其物理位置不一定相邻 在进行排序时 不需要移动元素 只需要修改相应的指针 9 1基本概念 11 待排序的元素的存储结构有三种方式 3 静态链表 元素之间的关系可以通过元素对应的游标指示 游标类似链表中的指针 9 1基本概念 12 9 1基本概念 本章讨论排序算法均使用顺序结构存储 且按关键字递增顺序排序 涉及记录的数据结构如下 defineMAXSIZE100 defineKEYTYPEinttypedefstruct KEYTYPEkey RECORDNODE 13 插入排序的算法思想是 在一个有序的元素序列中 不断地将新元素插入到该已经有序的元素序列中的合适位置 直到所有元素都插入到合适位置则完成排序 本节的主要学习内容包括 直接插入排序和希尔排序 9 2插入排序 14 9 2插入排序 9 2 1直接插入排序直接插入排序是一种最简单的排序方法 它的基本思想是 首先将第一个记录看成是已排好序的子序列 从第二个记录开始至第n个记录 每次将待排序记录插入到前面已排好序的序列的适当位置 直到全部记录排好序为止 15 具体的算法实现 假设待排序的元素有n个 对应的关键字分别是a1 a2 an 因为第一个元素是有序的 所以从第二个元素开始 将a2与a1进行比较 如果a2 a1 则将a2插入到a1之前 否则 说明已经有序 不需要移动a2 9 2 1直接插入排序 16 这样 有序的元素个数变为2 然后将a3与a2 a1进行比较 确定a3的位置 首先将a3与a2比较 如果a3 a2 则说明a1 a2 a3 已经是有序的了 如果a3 a2 则继续a3与a1比较 如果a3 a1 则将a3插入到a1之前 否则 将a3插入到a1与a2之间即完成了a1 a2 a3的排序 依次类推 直到最后一个关键字an插入到前n 1个有序排列 9 2 1直接插入排序 17 例 输入元素序列为 39 28 55 80 75 6 17 45 28按从小到大的序列排序 第一个取39 作第一个假设有序的记录 第二个取28 28 39 则交换 此后 每取来一个记录就与有序表最后一个关键字比较 若大于或等于最后一个关键字 则插入在其后 若小于最后一个关键字 则把取来的记录再与前一个关键字比较 其过程如图9 1 9 2 1直接插入排序 18 图9 1直接插入排序过程 19 排序以后 相同关键字元素的28和28与排序前的位置保持一致 即28仍然在28之前 所以直接插入排序方法是稳定的 监视哨 哨兵 的作用 1 在进入确定插入位置的循环之前 保存了插入值r i 的副本 避免因记录的移动而丢失r i 中的内容 2 使内循环总能够结束 以免循环过程中数组下标越界 9 2 1直接插入排序 20 voidinsertsort for i 2 i L i 依次插入r 2 r 3 r n if R i key R i 1 key R 0 R i 置监视哨j i 1 while R 0 key R j key 查找r i 的位置 R j 1 R j 向后移动记录j R j 1 R 0 插入r i 9 2 1直接插入排序 21 28 55 80 75 6 17 45 28 0 1 2 3 4 5 6 7 8 9 图9 2直接插入算法描述 39 9 2 1直接插入排序 22 从上面的分析 直接插入排序的算法简洁 容易实现 现在我们来看下他的效率怎样 空间效率 仅用了一个辅助单元 辅助空间为O 1 9 2 1直接插入排序 23 时间效率 向有序表中逐个插入记录的操作 进行了n 1趟 每趟操作分为比较关键码和移动记录 而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列 9 2 1直接插入排序 24 最好情况下 即待排序列已按关键字有序 每趟操作只需1次比较 0次移动 总比较次数n 1次总移动次数0次 9 2 1直接插入排序 25 最坏情况下 即第j趟操作 插入记录需要同前面的j个记录进行j次关键码比较 移动记录的次数为j 2次 9 2 1直接插入排序 26 若待排序记录是随机的 即待排序列中的记录可能出现的各类排列的概率相同 则我们可以取上述最小值和最大值的平均值 作为直接插入排序时所需进行关键字间的比较次数和移动记录的次数 约为n2 4 因此 直接插入排序的时间复杂度为O n2 9 2 1直接插入排序 27 9 2 2希尔排序 希尔排序 ShellSort 又称缩小增量排序 它是对直接插入排序的一种改进方法 希尔排序的基本思想是首先将待排序记录分割成若干个子序列 分别对每个子序列进行直接插入排序 待整个序列中的记录基本有序时 再对全体序列进行一次直接插入排序 28 9 2 2希尔排序 按照希尔排序 其排序过程如图9 2所示 29 9 2 2希尔排序 voidshellsort intd i j d n 2 while d 0 for i d 1 i0 30 交换排序的基本思想是 通过依次交换逆序的元素实现排序 本节的主要学习内容包括两种快速排序 冒泡排序和快速排序 9 3交换排序 31 9 3交换排序 9 3 1冒泡排序冒泡排序是一种简单的排序方法 其基本思想是 首先将第一个记录和第二个记录做比较 若逆序即r 1 key r 2 key 则将两个记录交换 然后再比较第二个记录和第三个记录 以此类推 直到第n 1个记录和第n个记录比较结束 这样完成一趟冒泡排序 第一趟排序结束后 最大的记录被交换到第n个位置 之后再对前面n 1个记录依前面的过程进行第二趟冒泡排序 将关键字次大的记录交换到第n 1个位置 32 9 3 1冒泡排序 按照冒泡排序方法 其排序过程如图9 3所示 33 9 3 1冒泡排序 voidbubblesort inti j for i 1 ir j 1 key r 0 r j r j r j 1 r j 1 r 0 34 9 3 1冒泡排序 算法分析 1 最好情况下 原数据按递增排列有序 改进后的冒泡排序算法共需比较数据n 1次 移动数据0次 35 9 3 1冒泡排序 算法分析 2 最坏情况下 原数据逆序排列 则需要进行n 1趟排序 每趟排序要进行n i次关键字的比较 且每次比较都必须移动记录三次来交换记录的位置 此时 比较和移动次数均达到最大值 36 9 3 2快速排序 快速排序的基本思想是 通过一趟快速排序用一个记录将待排序记录分成前后两部分 前一部分的关键字均比后一部分的关键字小 则支点的位置就确定了 然后再对前后两部分的记录进行快速排序 直到每个部分为空或只包含一个记录 整个快速排序结束 37 9 3 2快速排序 一趟快速排序的过程如下 1 设置两个整数变量i j 初始i j分别指向待排序记录的第一个元素和最后一个元素 将r i 复制到r 0 中 2 从j所指记录开始 比较r j key和r 0 key 若r j key r 0 key 则j 重复这个过程 直到找到一个小于r 0 key的记录为止 将该记录复制到位置i处 3 修改i i 1 从i所指记录开始 依次向后比较r i key和r 0 key 若r i key r 0 key 则i 重复这个过程 直到找到一个大于r 0 key的记录 将该记录复制到位置j处 4 修改j j 1 重复 2 和 3 过程 直到i j结束 5 将r 0 复制到位置i j 处 38 例 对数据序列 75 69 32 88 18 16 58进行快速排序 图9 5快速排序过程 75 69 32 88 0 1 2 3 4 18 16 58 5 6 7 9 3 2快速排序 39 intpart inti j i low j high r 0 r i while i r 0 key j if i j r i r j i 9 3 2快速排序 40 while i j 9 3 2快速排序 41 容易看出 快速排序是一种不稳定的排序算法 其空间复杂度在最好的情况下为O log2n 即每次正好将元素划分为相等的两个子序列 这样的快速排序就是将元素序列构成一棵完全二叉树的结构 在最坏情况下 即二叉树是一个单链 那么其空间复杂度为O n 9 3 2快速排序 42 其时间复杂度在最好的情况下 即每次划分 正好将分成两个等长的子序列 则时间复杂度为O nlog2n 在最坏的情况下 即快速排序每次划分 只得到一个子序列 这时快速排序蜕化为冒泡排序的过程 其时间复杂度最差 为O n2 9 3 2快速排序 43 通常 快速排序被认为是 在所有同数量级O nlog2n 排序方法中 其平均性能最好 但是 若初始记录序列按关键字有序或基本有序时 快速排序将蜕化为冒泡排序 其时间复杂度为O n2 可见算法的优劣不是绝对的 在序列基本排好序的情况下 要尽量避免使用快速排序的方法 9 3 2快速排序 44 9 4选择排序 9 4 1直接选择排序直接选择排序也是一种简单的排序方法 它的基本思想是 第一趟 从待排序记录中选出最小关键字的记录与第一个记录交换 第二趟再从剩余的数据中选出具有最小关键字的记录与第二个记录交换 以此类推 共进行n 1趟排序 将所有记录排好序 45 9 4 1直接选择排序 按照直接选择排序方法 排序过程如图9 6所示 46 9 4 1直接选择排序 voidselectsort inti j k 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 r 0 r i r i r k r k r 0 47 效率分析 简单选择排序比较次数与关键字初始排序无关 找第一个最小记录需进行n 1次比较 找第二个最小记录需要比较n 2次 找第i个最小记录需要进行n i次比较 总的比较次数为 n 1 n 2 n i 2 1 n n 1 2时间复杂度 O n2 辅助空间 O 1 简单选择排序是不稳定的排序方法 9 4 1直接选择排序 48 树形选择排序又称锦标赛排序 是一种按照锦标赛的思想进行选择排序的方法 首先对n个元素的关键字进行两两比较 然后在其中不大于n 2个较小者之间再进行两两比较 重复上面的操作 直到选出最小者为止 这个过程可以用一棵具有n个叶子结点的完全二叉树来表示 9 4 2堆排序 49 例 有16个选手参加的比赛 其成绩见图9 7各叶结点的值 图9 7选手成绩的二叉树 9 4 2堆排序 50 将叶子结点中的最大值改为最小值 与其兄弟结点比较 大者上升到父结点 兄弟结点之间再进行比较 如此反复 直到根结点 这样便选出了次小值 图9 7选手成绩的二叉树 9 4 2堆排序 51 从上面的分析我们可以看出 由于含有n个叶子结点的完全二叉树的深度为log2n 1 所以 除了最大的关键字之外 其他的关键字都只需要比较log2n次 所以 树形选择排序的时间复杂度为O nlog2n 但是该方法占用辅助空间较多 为了弥补缺陷 威洛姆斯在1964年提出了另一种形式的选择排序 堆排序 9 4 2堆排序 52 1 堆的定义堆排序主要是利用了二叉树的树形结构 按照完全二叉树的标号次序 将元素序列的关键字依次存放在相应的结点 然后从叶子结点开始 从互为兄弟的两个节点中 选择一个较大 或较小 的与其双亲结点比较 如果该结点都大于 或小于 双亲结点 则将两者进行交换 使较大 或较小 的成为双亲结点 将所有的结点都做类似操作 直到根结点为止 这时 根结点的元素值为关键字中最大 或最小 9 4 2堆排序 53 1 堆的定义这样便构成了堆 堆中的每一个结点都大于 或小于 其孩子结点 堆的数学形式定义 假设存在n个元素 其关键字序列为 k1 k2 kn 如果有 或 其中 i 1 2 n 2 9 4 2堆排序 54 在堆中 堆的根结点元素值一定是所有结点元素值的最大值或最小值 例如 序列 90 60 55 51 26 21 48 30 和 10 35 29 46 41 39 48 60 89 80 都是堆 其对应的完全二叉树表示如图所示 图9 8堆的示意图 9 4 2堆排序 55 如果将堆中的根结点输出以后 然后再将剩余的n 1个结点的元素值重新建立一个堆 则新堆的堆顶元素值是次大的 或次小 值 将该堆顶元素输出 然后将剩余的n 2个结点的元素值重新建立一个堆 反复执行以上操作 知道堆中没有结点 就构成了一个有序序列 这样的重复建堆并输出堆顶元素的过程称为堆排序 9 4 2堆排序 56 2 建堆建立大顶堆的算法思想是 从位于元素序列中的最后一个非叶子结点 即n 2 向下取整 个元素开始 逐层比较 直到根结点为止 假设当前结点的序号为i 则当前元素为a i 其左右孩子结点元素值分别为a 2 i 和a 2 i 1 将a 2 i key和a 2 i 1 key较大者与a i 比较 如果孩子结点元素值大于当前结点值 则交换 逐层向上执行此操作 直到根结点 9 4 2堆排序 57 图9 9建堆树的过程 9 4 2堆排序 58 3 调整堆实现堆排序要解决的一个问题 即输出堆顶元素后 怎样调整剩余n 1个元素 使其按关键码成为一个新堆 9 4 2堆排序 59 3 调整堆调整方法 设有m个元素的堆 输出堆顶元素后 剩下m 1个元素 将堆底元素送入堆顶 堆被破坏 其原因仅是根结点不满足堆的性质 将根结点与左 右子女中较大的进行交换 若与左子女交换 则左子树堆被破坏 且仅左子树的根结点不满足堆的性质 若与右子女交换 则右子树堆被破坏 且仅右子树的根结点不满足堆的性质 继续对不满足堆性质的子树进行上述交换操作 直到叶子结点 堆被建成 称这个自根结点到叶子结点的调整过程为筛选 9 4 2堆排序 60 图9 10堆排序的过程 a 输出堆顶元素88后 将堆底13送入堆顶 b 堆被破坏 根结点与左子女交换 c 左子树不满足堆 其根与左孩子交换 d 堆已建成 61 9 4 2堆排序 算法分析 堆排序适合于待排序记录较多