大学教程零起点数据结构-排序.ppt

1 18 01 2020 1 2 第7章排序 7 1基本概念7 2插入排序7 3交换排序7 4选择排序7 5归并排序7 6分配排序7 7各种内部排序比较 3 7 1基本概念 假设含有n个记录的序列为 R1 R2 Rn 其对应的关键字序列为 K1 K2 Kn 根据Ki的值对这组序列重新排列 使对应关键字有序Ri为一条记录Ki为记录的关键字可能存在多条记录具有相同的关键字 4 若具有相同关键字的记录经过排序后记录的相对位置仍保持不变则该排序算法是稳定的 否则为不稳定的排序时只在内存中进行 为内排序 需要读取外存设备中数据的为外排序内部排序方法有 插入排序 交换排序 选择排序 归并排序评价排序算法优劣的标准 时间复杂度和空间复杂度 5 待排序记录存储结构 typedefstruct intkey antypeotheritem records typedefrecordslist n 1 list为定义待排序记录的数据类型 并规定待排序记录中0元素不存数据 6 7 2插入排序 直接插入排序 基于顺序查找 表插入排序 基于链表存储 折半插入排序 基于折半查找 希尔排序 基于逐趟缩小增量 7 7 2插入排序 直接插入排序 基于顺序查找 直接插入排序思想 依次将待排序记录中的第i个记录插入到有序序列中 初始情况 将r1作为有序序列 将r2 rn逐个插入 通过顺序查找方式找到ri在有序表中的位置 找位置的同时移动有序序列中元素的位置 找位置时从后向前找 在一个已排好序的记录子集的基础上 每一步将下一个待排序的记录有序地插入到已排好序的记录子集中 直到将所有待排记录全部插入为止 8 直接插入排序 基于顺序查找 初始关键字 35 48 35 18 45 12 68 33 48 35 第一趟排序 48 35 18 45 12 68 33 步骤 i 2ri存入r0位置将r0关键字与rj关键字比较 j从i 1开始到1 若r0 rj则rj存入rj 1位置 j减1r0存入rj 1位置 r0为监视哨 9 直接插入排序 基于顺序查找 初始关键字 35 18 45 12 68 33 48 35 第二趟排序 48 35 18 45 12 68 33 步骤 i 3ri存入r0位置将r0关键字与rj关键字比较 j从i 1开始到1 若r0 rj则rj存入ri 1位置 j减1r0存入rj 1位置 18 48 35 18 r0为监视哨 10 直接插入排序 基于顺序查找 初始关键字 45 12 68 33 第三趟排序 48 35 18 45 12 68 33 步骤 i 4ri存入r0位置将r0关键字与rj关键字比较 j从i 1开始到1 若r0 rj则rj存入rj 1位置 j减1r0存入rj 1位置 18 48 35 18 45 48 45 r0为监视哨 11 直接插入排序 基于顺序查找 初始关键字 12 68 33 第四趟排序 48 35 18 45 12 68 33 步骤 i 5ri存入r0位置将r0关键字与rj关键字比较 j从i 1开始到1 若r0 rj则rj存入rj 1位置 j减1r0存入rj 1位置 35 18 45 48 45 12 48 45 35 18 12 r0为监视哨 12 直接插入排序 基于顺序查找 初始关键字 48 351845126833 3548 1845126833 183548 45126833 18354548 126833 1218354548 6833 121835454868 33 12183335454868 13 例 打扑克牌时的抓牌就是插入排序一个很好的例子 每抓一张牌 插入到合适位置 直到抓完牌为止 即可得到一个有序序列 14 已知一组键值序列 22 24 26 25 27 29 21 28 试给出采用直接插入排序法对该组序列作升序排序的每一趟结果 试写出直接插入排序算法 设顺序表va中的数据元素递增有序 试编写算法实现将x插入到顺序表的适当位置上 以保持该表的有序性 用插入排序算法对数据序列 47 33 61 82 72 11 25 57 进行排序 写出整个插入排序的每一趟过程 15 7 2插入排序 直接插入排序 基于顺序查找 VoidStraightSort listr intn for i 2 i n i r 0 r i j i 1 while r 0 key r j key r j 1 r j j r j 1 r 0 r0为监视哨 该算法时间复杂度为O n2 该算法空间复杂度为O 1 该算法是稳定的排序算法 16 设顺序表va中的数据元素递增有序 试编写算法实现将x插入到顺序表的适当位置上 以保持该表的有序性 Va类型定义typedefstruct intkey anytypeothers record definemaxsize100typedefstruct recorditem maxsize 1 记录数组 从1到nintn 记录条数 list 17 VoidSort listva recordx i va n while r i 1 r i i r i 1 x x key r i key i 1 18 实现排序的基本操作有两个 1 比较 序列中两个关键字的大小 2 移动 记录 最好的情况 关键字在记录序列中顺序有序 最坏的情况 关键字在记录序列中逆序有序 时间复杂度为O n2 直接插入排序算法评价 18 01 2020 18 19 7 2插入排序 折半插入排序 基于折半查找 折半插入排序思想 依次将待排序记录中的第i个记录插入到有序序列中初始情况 将r1作为有序序列 将r2 rn逐个插入通过折半查找方式找到ri在有序表中的位置找位置后 移动有序序列中元素的位置 20 7 2插入排序 希尔排序 分组插入排序 排序过程 先取一个正整数d1 n 把所有相隔d1的记录放一组 组内进行直接插入排序 然后取d2 d1 重复上述分组和排序操作 直至di 1 即所有记录放进一个组中排序为止 21 希尔排序应用实例 18 01 2020 21 22 7 3交换排序 所谓交换排序就是将待排序序列中的两个键值比较 根据比较结果 交换两个记录的位置 冒泡排序快速排序 23 7 3交换排序 冒泡排序 冒泡排序是最简单的交换排序算法算法思想 将第一个记录键值与第二个比较 若符合条件则交换将第二个记录键值与第三个比较 若符合条件则交换将第三个记录键值与第四个比较 若符合条件则交换冒泡排序需要进行多少趟排序 若某趟排序未进行交换 则算法停止 24 冒泡排序 37 18 64 14 96 48 42 96 j从1开始到n将第j个记录键值与第j 1个比较若符合条件则交换 18 37 64 14 96 48 96 42 这是第一趟排序过程 交换条件是 第j个大于第j 1个记录则交换 第一趟排序后最后一个记录已排至合适位置 第二趟排序对1到n 1条记录排序即可 25 冒泡排序 37 96 18 64 14 48 96 42 第二趟排序后 交换条件是 第j个大于第j 1个记录则交换 j从1开始到n 1将第j个记录键值与第j 1个比较若符合条件则交换 37 96 18 64 14 48 96 42 要进行多少趟排序 26 冒泡排序算法时间复杂度为O n2 稳定的 VoidbubbleSort intn listr for i 1 i n 1 i flag 1 for j 1 j n i j if r j 1 key r j key flag 0 p r j r j r j 1 r j 1 p if flag 1 return 27 起泡排序的实现和演示 18 01 2020 27 voidBubbleSort inta intn 将a中整数序列重新排列成自小至大有序的整数序列 for i n 1 i 1 i for j 0 ja j 1 swap a j a j 1 4938659776132730 初始 3849657613273097 第一趟 38496513273076 第二趟 384913273065 第三趟 3813273049 第四趟 13273038 第五趟 132730 第六趟 38 49 76 97 13 97 27 97 30 97 13 76 76 76 27 30 13 65 27 65 30 65 13 13 49 49 30 49 27 38 27 38 30 38 voidBubbleSort inta intn 将a中整数序列重新排列成自小至大有序的整数序列 for i n 1 change TRUE i 1 重复上述过程 直到 在一趟排序过程中没有进行过交换记录的操作 为止 28 快速排序 又称划分交换排序 交换排序的一种基本思想任取一个记录为基准 通过比较关键字 交换记录 将待排序列分成两组 使得一组所有记录的关键字小于基准记录的关键字 另一组所有记录的关键字大于等于基准记录的关键字 然后对这两部分记录继续快速排序 以达到整个序列按关键字有序 29 快速排序 1 设置两个搜索指针 i是向后搜索指针初值为1j是向前搜索指针初值为n且把r 1 存入r 0 中 r 1 为基准记录 2 j逐渐减小 进行r j key和r 0 key比较直到满足r j keyr 0 key时将r i 移动至r j 位置4 重复2 3步骤直至i j为止 一趟快速排序完成 30 快速排序过程 初始关键字 48 35 18 49 12 68 33 48 1 将r 1 存入r 0 第1趟排序将r 1 key为基准将r 1 排至最终位置 2 r j key与r 0 key比较 r j key r 0 key时将r j 移动至r i 位置 33 3 i 1开始逐渐增大 比较r i key和r 0 key r i key r 0 key时将r i 移动至r j 位置 4 j j 1 重复2 3步骤 直到i j时将r 0 存入r i 位置 49 12 48 第一趟排序完成 31 快速排序过程 一趟排序后关键字 35 18 68 48 分别对一趟排序后的两部分进行快速排序即可 33 49 12 48 33 12 35 18 33 32 已知序列503 87 512 61 908 170 897 275 653 462请给出采用快速排序法作升序排序时的每一趟的结果 503 87 512 61 908 170 897 275 653 462 503 503 87 512 61 908 170 897 275 653 462 462 512 275 908 170 503 第一趟排序结果 33 34 35 low到high之间记录进行快速排序Voidquick listr intlow inthigh i low j high r 0 r i if i j return while i r 0 key j if i j r i r j i while i jquick r i 1 high 36 用快速排序法对数据序列 49 38 65 97 16 53 134 27 39 进行排序 写出其第一趟排序的全过程 49 38 65 97 16 53 134 27 39 49 37 快速排序时间复杂度 O nlogn 该算法不稳定若数据序列本身有序 则算法执行效率最低 近似O n2 38 7 4选择排序 直接 简单 选择排序算法思想首先从待排序序列中选取最小记录 把它与第一个记录交换 然后在剩余的记录中选择最小记录与第二个记录进行交换 直至排序完成 直接 简单 选择排序 堆排序 39 初始关键字 5133629687172851第一趟排序 17 33629687512851第二趟排序 1728 629687513351第三趟排序 172833 9687516251第四趟排序 17283351 87966251第五趟排序 1728335151 966287第六趟排序 172833515162 9687第七趟排序 1728335151628796 N个数据需要多少趟排序 40 直接选择排序算法Voidselect listr 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 swap r k r i 时间复杂度 O n2 直接选择排序是不稳定的 41 7 4选择排序 基本思想 对n个待排序记录的关键字进行两两比较 从中选出n 2个较小者再两两比较 直到选出关键字最小的记录为止 此为一趟排序 一趟选出的关键字最小的记录称为 冠军 而 亚军 是从与 冠军 比较失败的记录中找出 输出 冠军 后 将 冠军 叶子结点关键字改为最大 继续进行锦标赛排序 直到选出关键字次小的记录为止 如此循环直到输出全部有序序列 树形选择排序 锦标赛排序 42 树形选择排序 锦标赛排序 对关键字序列72 73 71 23 94 16 05 68进行树形选择排序 05 23 05 72 23 16 05 72 73 71 23 94 16 05 68 冠军 72 23 1605 43 亚军 是从与 冠军 比较失败的记录中找出的 72 73 71 23 94 16 68 05 16 23 16 72 23 16 68 72 73 71 23 94 16 68 冠军 16 44 堆排序是一种改进的树形排序 堆是满足下列性质的数列 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 1234567891011 45 12 36 27 65 40 34 98 81 73 55 49 是小顶堆 12 36 27 65 81 73 55 40 98 49 34 46 12 36 27 65 40 14 98 81 73 55 49 不是堆 12 36 27 65 81 73 55 40 98 49 14 47 堆排序的基本思想是 首先将待排序的记录序列构造一个堆 此时 选出了堆中所有记录的最小者或最大者 然后将它从堆中移走 并将剩余的记录再调整成堆 这样又找出了次小 或次大 的记录 以此类推 直到堆中只有一个记录为止 每个记录出堆的顺序就是一个有序序列 两个问题 1 输出堆顶后 如何调整堆2 如何建立一个堆 48 14 80 75 46 18 6 36 18 1 输出堆顶元素 调整堆 调整方法为 n个结点的堆 输出堆顶 剩n 1个结点将堆尾结点送入堆顶 堆可能被破坏 将根结点与左 右孩子中较小的进行交换 交换后 子树堆被破坏 继续对不满足堆性质的子树进行上述交换操作 直到叶子结点 堆被建成 46 46 14 6 14 49 80 75 6 36 18 46 46 14 6 14 36 18 36 18 75 36 75 36 80 46 80 46 75 1 输出堆顶元素 调整堆 调整方法为 n个结点的堆 输出堆顶 剩n 1个结点将堆尾结点送入堆顶 堆可能被破坏 将根结点与左 右孩子中较小的进行交换 交换后 子树堆被破坏 继续对不满足堆性质的子树进行上述交换操作 直到叶子结点 堆被建成 50 2 初建堆 给定序列建立堆先取i n 2 将以i结点为根的子树调整成为堆 然后令i i 1 再将以i结点为根的子树调整成为堆 此时可能会反复调整某些结点 直到i 1为止 初建堆完成 例如 36 14 18 80 75 6 46 36 14 18 80 75 6 46 6 18 36 6 36 18 51 已知一组键值序列 32 44 38 65 53 42 29 57 试采用堆排序法对该组序列作升序排序 给出建立的初始堆以及第一次输出堆元素后筛选调整的堆 32 44 38 65 53 42 29 57 52 已知一组键值序列 32 44 38 65 53 42 29 57 试采用堆排序法对该组序列作升序排序 给出建立的初始堆以及第一次输出堆元素后筛选调整的堆 32 44 38 65 53 42 29 57 57 65 29 38 29 32 53 已知一组键值序列 32 44 38 65 53 42 29 57 试采用堆排序法对该组序列作升序排序 给出建立的初始堆以及第一次输出堆元素后筛选调整的堆 32 44 38 65 53 42 29 57 57 65 29 38 29 32 29 65 65 32 38 65 54 已知一组键值序列 33 37 26 43 55 67 42 38 试采用堆排序法对该组序列作升序排序 给出建立的初始堆 以及第一次输出堆元素后筛选调整的堆 画出对应于序列 10 20 7 75 41 67 3 9 30 45 的初始堆 堆顶元素取最小值 55 设要将序列 Q H C Y P A M S R 按字母升序排序 请分别画出采用堆排序方法时建立的初始堆 以及第一次输出堆顶元素后经过筛选调整的堆形态 什么是堆 写出对应于序列 10 20 7 75 41 67 3 9 30 45 的初始堆 堆顶元素取最小值 56 7 5归并排序 基本思想 将多个有序序列合并成一个有序序列 将两个有序子序列合并为一个有序序列称为2路归并排序 将具有n个记录的序列看成是n个长度为1的有序序列然后进行两两归并 得到多个长度为2的有序序列 继续两两归并 如此重复 直至得到一个长度为n的有序序列为止 57 写出键值83 40 63 13 84 35 96 57 39 79 61 15应用二路归并排序算法从小到大排序后各趟的结果 83 40 63 13 84 35 96 57 39 79 61 15 40 83 13 63 35 84 57 96 39 79 15 61 13 40 63 83 35 57 84 96 15 39 61 79 13 35 40 57 63 83 84 96 15 39 61 79 13 15 35 39 40 57 61 63 79 83 84 96 58 两个有序序列A B如何合并成一个有序序列 13 35 40 57 63 83 84 15 39 61 79 合并至A序列 合并形成新序列C 59 两个有序序列如何合并成一个有序序列 设i j是两个有序序列中的记录下标 m n是两个序列长度 R 是新的合并后的序列 下表从k开始 1 im或j n时 将对应序列中的剩余部分存入R中 13 35 40 57 63 83 84 96 15 39 61 79 i j k 13 15 35 39 40 57 61 63 79 83 84 96 60 有序序列的合并算法 Voidmerge lista listb listc i 1 j 1 k 1 while i an 循环结束后是否所有记录已存入c中 61 有序序列的合并算法 Voidmerge lista listb listc 循环结束后是否所有记录已存入c中 while i an c k a i i k while j bn c k b j j k 62 写出键值83 40 63 13 84 35 96 57 39 79 61 15应用二路归并排序算法从小到大排序后各趟的结果 已知一组键值序列 13 12 16 17 15 14 11 试采用二路归并排序法对该组序列作升序排序并给出每一趟的排序结果 已知一组键值序列 26 21 32 56 78 89 90 试采用二路归并排序法对该组序列作升序排序 并给出每一趟的排序结果 63 7 6分配排序 箱 桶 排序 箱排序也称桶排序算法思想 设置若干个箱子 依次扫描待排序记录 把关键字等于K的记录全部装入第k个箱子 分配过程 然后依次将各个非空的箱子首尾连接起来 收集过程 64 7 6分配排序 箱 桶 排序 78 17 39 26 72 94 21 12 23 68 B 0 B 1 B 2 B 3 B 4 B 5 B 6 B 7 B 8 B 9 26 39 94 78 21 72 17 桶 0 10 20 30 40 50 60 70 80 90 12 23 68 每个桶首尾相连 收集即可得到有序序列 65 基数排序是一种借助 多关键字排序 的思想来实现 单关键字排序 的内部排序算法 多关键字的排序 链式基数排序 最低位优先LSD法 最高位优先MSD法 7 6分配排序 基数排序 66 无序序列 对K2排序 对K1排序 对