严蔚敏版数据结构C语言版第十章 原版ppt课件.ppt

数据结构 10 1概述 10 2插入类排序 10 4选择类排序 第10章内部排序 10 3交换类排序 10 5归并排序 10 6基数排序 10 7各种排序方法的总和比较 1 数据结构 10 1概述 第10章内部排序 排序是计算机内经常进行的一种操作 其目的是将一组 无序 的记录序列调整为 有序 的记录序列 例如 将下列关键字序列 52 49 80 36 14 58 61 23 97 75 调整为 14 23 36 49 52 58 61 75 80 97 2 数据结构 10 1概述 第10章内部排序 排序的定义 假设含n个记录的序列为 a0 a1 an 1 其相应的关键字序列为 K0 K1 Kn 1 这些关键字相互之间可以进行比较 即在它们之间存在着这样一个关系 Kp0 Kp1 Kpn 1 按此固有关系将上式记录序列重新排列为 ap0 ap1 apn 1 的操作称作排序 3 数据结构 10 1概述 第10章内部排序 排序 内部排序 外部排序 整个排序过程不需要访问外存便能完成 若参加排序的记录数量很大 整个序列的排序过程不可能在内存中完成 稳定排序 不稳定排序 排序 相同关键字的领先关系在排序过程中未发生变化 相同关键字的领先关系在排序过程中发生变化 4 数据结构 10 1概述 第10章内部排序 内部排序的过程 是一个逐步扩大记录的有序序列长度的过程 经过一趟排序 有序序列区 无序序列区 有序序列区 无序序列区 内部排序的方法 5 数据结构 10 1概述 第10章内部排序 基于不同的 扩大 有序序列长度的方法 内部排序方法大致可分下列几种类型 插入类 交换类 选择类 归并类 其它方法 6 数据结构 10 1概述 第10章内部排序 待排记录的数据类型定义如下 defineMAXSIZE1000typedefintKeyType typedefstruct KeyTypekey OtherTypeother data RecordType typedefstruct RcdTyper MAXSIZE 1 intlength SqList 7 数据结构 10 2插入类排序 第10章内部排序 将无序子序列中的一个或几个记录 插入 到有序序列中 从而增加记录的有序子序列的长度 有序序列a 1 i 1 a i 无序序列a i n 1 一趟直接插入排序的基本思想 有序序列a 1 i 无序序列a i 1 n 1 8 数据结构 10 2插入类排序 第10章内部排序 实现 一趟插入排序 可分三步进行 3 将a i 插入 复制 到a j 1 的位置上 2 将a j 1 i 中的所有记录均后移一个位置 1 在a 1 i 1 中查找a i 的插入位置 a 1 j key a i key a j 1 i key 9 数据结构 10 2插入类排序 第10章内部排序 直接插入排序 基于顺序查找 希尔排序 基于逐趟缩小增量 不同的具体实现方法导致不同的算法描述 折半插入排序 基于折半查找 表插入排序 基于链表存储 10 数据结构 10 2插入类排序 第10章内部排序 直接插入排序 利用顺序查找实现在r 1 i 1 中查找r i 的插入位置 48 62 35 77 55 14 35 98 第1趟 48 62 r 0 62 35 2 35 48 62 3 77 77 4 55 55 62 77 5 14 14 35 48 55 62 77 6 35 35 48 55 62 77 7 98 98 从r i 1 起向前进行顺序查找 监视哨设置在r 0 r 0 r i 循环结束表明r i 的插入位置为j 1 r 0 j r i for j i 1 r 0 key r j key j j i 1 插入位置 11 数据结构 10 2插入类排序 第10章内部排序 对于在查找过程中找到的那些关键字不小于r i key的记录 并在查找的同时实现记录向后移动 for j i 1 r 0 key r j key j r j 1 r j 上述循环结束后可以直接进行 插入 r j 1 r 0 r 0 j r i j i 1 插入位置 直接插入排序 12 令i 2 3 n 实现整个序列的排序 for i 2 i n i if r i key r i 1 key 在r 1 i 1 中查找r i 的插入位置 插入r i 数据结构 10 2插入类排序 第10章内部排序 直接插入排序 13 数据结构 10 2插入类排序 第10章内部排序 直接插入排序 voidInsertionSort SqList i if L r i key L r i 1 key L r 0 L r i for j i 1 L r 0 key L r j key j L r j 1 L r j L r j 1 L r 0 14 内部排序的时间分析 实现内部排序的基本操作有两个 2 移动 记录 1 比较 序列中两个关键字的大小 数据结构 10 2插入类排序 第10章内部排序 直接插入排序 15 对于直接插入排序 最好的情况 关键字在记录序列中顺序有序 比较 的次数 最坏的情况 关键字在记录序列中逆序有序 比较 的次数 0 移动 的次数 移动 的次数 数据结构 10 2插入类排序 第10章内部排序 直接插入排序 16 数据结构 10 2插入类排序 第10章内部排序 折半插入排序 因为r 1 i 1 是一个按关键字有序的有序序列 则可以利用折半查找实现 在r 1 i 1 中查找r i 的插入位置 如此实现的插入排序为折半插入排序 i low high m high m high m low 例如 插入位置 L r 17 数据结构 10 2插入类排序 第10章内部排序 折半插入排序 voidBiInsertionSort SqList L 在L r 1 i 1 中折半查找插入位置 for i 2 i L length i L r 0 L r i for j i 1 j low j L r j 1 L r j L r low L r 0 18 数据结构 10 2插入类排序 第10章内部排序 折半插入排序 low 1 high i 1 while low high m low high 2 if L r 0 key L r m key high m 1 elselow m 1 在L r 1 i 1 中折半查找插入位置 19 数据结构 10 2插入类排序 第10章内部排序 希尔排序 基本思想 对待排记录序列先作 宏观 调整 再作 微观 调整 所谓 宏观 调整 指的是 跳跃式 的插入排序 又称缩小增量排序 20 将记录序列分成若干子序列 分别对每个子序列进行插入排序 其中 d称为增量 它的值在排序过程中从大到小逐渐缩小 直至最后一趟排序减为1 例如 将n个记录分成d个子序列 R 1 R 1 d R 1 2d R 1 kd R 2 R 2 d R 2 2d R 2 kd R d R 2d R 3d R kd R k 1 d 数据结构 10 2插入类排序 第10章内部排序 希尔排序 又称缩小增量排序 具体做法为 21 数据结构 10 2插入类排序 第10章内部排序 希尔排序 又称缩小增量排序 d1 4 17 55 05 13 d2 2 05 13 46 94 d3 1 13 17 70 94 22 数据结构 10 2插入类排序 第10章内部排序 希尔排序 又称缩小增量排序 voidShellInsert SqList 23 数据结构 10 2插入类排序 第10章内部排序 希尔排序 又称缩小增量排序 voidShellSort SqList 24 数据结构 10 3交换类排序 第10章内部排序 基本思想 通过交换逆序元素进行排序的方法 冒泡排序 相邻比逆法 快速排序 通过 交换 无序序列中的记录从而得到其中关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 25 数据结构 10 3交换类排序 第10章内部排序 冒泡排序 相邻比逆法 思想 在扫描的过程中顺次比较相邻的两个元素的大小 若逆序就交换位置 第1趟 35 62 55 77 14 77 35 77 22 98 40 98 9次 第2趟 77 35 48 55 14 35 62 22 40 8次 第n 1趟 排序结束 n i次 第i趟 26 数据结构 10 3交换类排序 第10章内部排序 冒泡排序 相邻比逆法 voidBubbleSort RecordTyper intlength n length for i 1 ir j 1 key x a j r j r j 1 r j 1 x 27 数据结构 10 3交换类排序 第10章内部排序 冒泡排序 时间分析 28 数据结构 10 3交换类排序 第10章内部排序 快速排序 改进冒泡排序中一次交换只能消除一个逆序的缺点 即实现一次交换消除多个逆序 思想 找一个记录 以它的关键字作为 枢轴 凡其关键字小于枢轴的记录均移动至该记录之前 凡其关键字大于枢轴的记录均移动至该记录之后 即对无序的记录序列进行 一次划分 之后分别对分割所得两个子序列 递归 进行快速排序 29 数据结构 10 3交换类排序 第10章内部排序 快速排序 一次划分 一趟快速排序 r 0 48 low high high 35 low 62 high 14 low low 77 high high 48 30 数据结构 10 3交换类排序 第10章内部排序 快速排序 intQKpass RecordTyper intlow inthigh r 0 r low while low high while low r 0 key high r low r high while low high r high r low r low r 0 returnlow 一趟快速排序算法 31 voidQKSort RecordTyper intlow inthigh r 0 r low if low high pos QKpass r low high QKSort r low pos 1 QkSort r pos 1 high 数据结构 10 3交换类排序 第10章内部排序 快速排序 算法 32 数据结构 10 4选择类排序 第10章内部排序 从记录的无序子序列中 选择 关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 简单选择排序 堆排序 树型选择排序 33 数据结构 10 4选择类排序 第10章内部排序 简单选择排序 i 第1趟 k j j k j j j k j j 14 48 2 i k j 35 62 3 35 62 4 48 77 5 55 6 62 77 7 77 8 98 voidSelectSort RecordTyper intn n length 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 x r i r i r k r k x 34 数据结构 10 4选择类排序 第10章内部排序 树型选择排序 是一种按锦标赛的思想进行排序的方法 49 38 27 65 97 76 49 13 38 65 13 27 38 13 13 76 13 27 27 27 49 49 38 38 49 49 49 49 65 49 49 76 65 65 97 97 76 76 97 97 35 数据结构 10 4选择类排序 第10章内部排序 堆排序 对树型排序的进一步改进 堆是满足下列性质的数列 r1 r2 rn 或 堆的定义 12 36 27 65 40 34 98 81 73 55 49 例如 是小顶堆 12 36 27 65 40 14 98 81 73 55 49 不是堆 小顶堆 大顶堆 36 ri r2i r2i 1 若将该数列视作完全二叉树 则r2i是ri的左孩子 r2i 1是ri的右孩子 例如 数据结构 10 4选择类排序 第10章内部排序 堆排序 12 36 27 65 40 34 98 81 73 55 49 12 36 27 65 40 34 98 81 73 55 49 14 14 是小顶堆 不 37 堆排序即是利用堆的特性对记录序列进行排序 例如 建大顶堆 98 81 49 73 36 27 40 55 64 12 12 81 49 73 36 27 40 55 64 98 交换98和12 重新调整为大顶堆 81 73 49 64 36 27 40 55 12 98 40 55 49 73 12 27 98 81 64 36 经过筛选 数据结构 10 4选择类排序 第10章内部排序 堆排序 38 1 如何由一个无序序列 建初堆 堆排序的两个问题 2 输出堆顶后 如何 筛选 数据结构 10 4选择类排序 第10章内部排序 堆排序 所谓 筛选 指的是 对一棵左 右子树均为堆的完全二叉树 调整 根结点使整个二叉树也成为一个堆 39 数据结构 10 4选择类排序 第10章内部排序 堆排序 48 98 77 62 48 40 数据结构 10 4选择类排序 第10章内部排序 堆排序 例如 48 62 35 77 55 14 35 98 48 62 35 77 55 14 35 98 显然不是一个堆 调整 如何建初堆 41 数据结构 10 4选择类排序 第10章内部排序 堆排序 98 77 98 77 62 98 77 62 48 42 数据结构 10 4选择类排序 第10章内部排序 堆排序 98 48 98 77 62 48 77 35 77 62 55 35 62 62 14 55 48 14 55 55 35 48 35 48 48 14 35 14 35 35 35 35 35 14 14 43 时间复杂度分析 1 对深度为k的堆 筛选 所需进行的关键字比较的次数至多为2 k 1 3 调整 堆顶 n 1次 总共进行的关键字比较的次数不超过2 log2 n 1 log2 n 2 log22 2n log2n 因此 堆排序的时间复杂度为O nlogn 2 对n个关键字 建成深度为h log2n 1 的堆 所需进行的关键字比较的次数至多4n 数据结构 10 4选择类排序 第10章内部排序 堆排序 44 数据结构 10 5归并类排序 第10章内部排序 通过 归并 两个或两个以上的记录有序子序列 逐步增加记录有序序列的长度 在内部排序中 通常采用的是2 路归并排序 即 将两个位置相邻的记录有序子序列 归并为一个记录的有序序列 有序序列r l n 有序子序列r l m 有序子序列r m 1 n 45 数据结构 10 5归并类排序 第10章内部排序 例如 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 很少进行内排序 主要用于外排序 46 数据结构 10 6基数排序 第10章内部排序 主要利用分配和收集两种基本操作 典型的就是基数类排序 多关键字的排序 链式基数排序 47 数据结构 10 6基数排序 第10章内部排序 多关键字的排序 最低位优先LSD法 最高位优先MSD法 先对K0进行排序 并按K0的不同值将记录序列分成若干子序列之后 分别对K1进行排序 依次类推 直至最后对最次位关键字排序完成为止 先对Kd 1进行排序 然后对Kd 2进行排序 依次类推 直至对最主位关键字K0排序完成为止 排序过程中不需要根据 前一个 关键字的排序结果 将记录序列分割成若干个 前一个 关键字不同的 子序列 48 例如 学生记录含三个关键字 系别 班号和班内的序列号 其中以系别为最主位关键字 1 2 15 2 3 18 3 1 20 2 1 20 3 2 30 3 1 20 2 1 20 1 2 15 3 2 30 2 3 18 1 2 15 2 1 20 2 3 18 3 1 20 3 2 30 LSD的排序过程如下 数据结构 10 6基数排序 第10章内部排序 多关键字的排序 49 数据结构 10 6基数排序 第10章内部排序 链式基数排序 假如多关键字的记录序列中 每个关键字的取值范围相同 则按LSD法进行排序时 可以采用 分配 收集 的方法 其好处是不需要进行关键字间的比较 对于数字型或字符型的单关键字 可以看成是由多个数位或多个字符构成的多关键字 此时可以采用这种 分配 收集 的办法进行排序 称作基数排序法 50 例如 对下列这组关键字 209 386 768 185 247 606 230 834 539 首先按其 个位数 取值分别为0 1 9 分配 成10组 之后按从0至9的顺序将它们 收集 在一起 然后按其 十位数 取值分别为0 1 9 分配 成10组 之后再按从0至9的顺序将它们 收集 在一起 最后按其 百位数 重复一遍上述操作 数据结构 10 6基数排序 第10章内部排序 链式基数排序 51 在计算机上实现基数排序时 为减少所需辅助存储空间 应采用链表作存储结构 即链式基数排序 具体作法为 待排序记录以指针相链 构成一个链表 分配 时 按当前 关键字位 所取值 将记录分配到不同的 链队列 中 每个队列中记录的 关键字位