软件技术基础-排序1

排序的目的是将一组任意的数据元素 或记录 序列 按照人们所需要的顺序 排列成有规律的按关键字有序的序列 如手机电话簿 目前的各种排行榜 第十四章排序 本章主要内容 1 排序的基本概念2 插入排序3 选择排序4 交换排序5 归并排序 第十四章排序 预备知识 关键字 key 通常数据对象有多个属性域 即多个数据成员组成 其中有一个属性域可用来区分对象 作为排序依据 该域即为关键字 如学生这个数据对象 关键字可以是学号或身份证号 每个数据表用哪个属性域作为关键码 要视具体的应用需要而定 1 排序的基本概念 1 排序的概念 就是整理文件中的记录 将它们按照关键字值的递增或递减的顺序排列起来 假设文件中含有n个记录 R1 R2 Rn 它们的关键字分别为k1 k2 kn 我们将这n个记录重排为Ri1 Ri2 Rin 使得ki1 ki2 kin 或ki1 ki2 kin 这就是排序 排序前 R1 R2 Rn k1 k2 kn 无序 排序后 Ri1 Ri2 Rin ki1 ki2 kin 或ki1 ki2 kin 有序 1 排序的基本概念 2 排序的稳定性 存在于文件中的记录 可能含有相同的关键字 对于关键字ki kj的记录Ri和Rj 如果在原始文件中 Ri排在Rj之前 而排序后的文件中Ri仍然排在Rj之前 就称排序是稳定的 反之 如果排序后变成Ri排在Rj之后 就称此排序是不稳定的 1 排序的基本概念 1 排序的基本概念 3 排序分类按待排序记录所在位置分 内部排序 整个排序过程都在内存中进行的排序 适用于记录文件个数不是很多的小文件 外部排序 当排序的文件很大时 以至内存不足以存放全部记录 需借助对外存进行访问的排序 适用于记录个数太多 不能一次将其全部放入内存的大文件 内部排序按排序所用策略分 插入排序 直接插入排序 希尔排序交换排序 冒泡排序 快速排序选择排序 简单选择排序归并排序 2 路归并排序 1 排序的基本概念 4 内部排序所用的存储结构 以一维数组作为存储结构排序过程是对记录本身进行物理重排 即通过比较和判定 把记录移动合适的位置 以链表作为存储结构排序过程中无须移动记录 仅需修改指针即可 通常把这类排序称为表排序 为排序文件建立辅助表有的排序方法难以在链表上实现 此时 若仍需要避免排序过程记录的移动 可以为文件记录一个辅助表 如索引表 这样 排序过程中只需对这个辅助的表进行物理重排 而不移动记录本身 1 排序的基本概念 5 排序方法的评价 执行算法所需要的时间执行算法所需要的附加空间算法本身的复杂程度排序是一种经常使用的一种运算 其所需的附加空间量一般都不大 所以排序的时间代价是衡量排序算法好坏的最重要的标志 6 排序的基本操作 比较两个关键字大小将记录从一个位置移动到另一个位置排序的时间代价主要是指执行算法中关键字的比较和记录的移动次数 因此在下面讨论的各种排序算法时 我们将给出各算法的比较次数和移动次数 1 排序的基本概念 7 本章排序方法所用的存储结构 本章中 假设记录数组作为文件的存储结构 关键字为整数 文件类型说明如下 typedefstruct 定义记录为结构类型 intkey 关键字域 datatypeother 记录的其它域 rectype rectypeR n R为记录类型的数组 其中 n为文件的记录总数 本章主要内容 1 排序的基本概念2 插入排序3 选择排序4 交换排序5 归并排序 第十四章排序 2 插入排序 插入排序 InsertionSort 将待排序的一组记录分为两个区 有序区和无序区 每次将无序区中的第一个记录按其关键字值的大小插入到有序区中的适当位置 直到无序区中的全部记录都插完为止 插入排序的分类 直接插入排序希尔排序 2 插入排序 直接插入排序 2 1直接插入排序1 基本思想直接插入排序是一种最简单的排序方法 具体做法是在插入第i个记录时 R1 R2 Ri 1已排好序 这时将Ri的关键字ki依次与关键字ki 1 ki 2 k1进行比较 从而找到应该插入的位置 然后将ki插入 R1 R2 Ri 1 Ri Ri 1 Rn 有序区 无序区 注意比较的方向 2 直接插入排序实例初始关键字 47 33618272112547 i 2 33 3347 618272112547 i 3 61 334761 8272112547 i 4 82 33476182 72112547 i 5 72 3347617282 112547 i 6 11 113347617282 2547 i 7 25 11253347617282 47 i 8 47 1125334747 617282 2 插入排序 直接插入排序 2 插入排序 直接插入排序 3 算法设计 R1 R2 Ri 1 Ri Ri 1 Rn 有序区 无序区 R0 监视哨 4 算法实现InsertSort R rectypeR n 1 R 0 备用 R 1 R n 为n个待排序记录 inti j for i 2 i n i 外层循环控制进行n 1趟排序 R 0 R i 将待插入记录存放在监视哨中j i 1 while R 0 key R j key 在当前有序区查找插入位置 R j 1 R j j 将关键字大于R j key的记录后移 R j 1 R 0 插入R i 2 插入排序 直接插入排序 为何没有j 0判断条件 会不会丢失R i 的值 为何计数器从2开始 5 算法说明算法采用的是查找比较操作和记录移动操作交替进行的方法 具体作法是将待插入记录R i 的关键字依次与有序区中的关键字R j j i 1 i 2 1 的关键字进行比较 若R j 的关键字大于R i 的关键字 则将R j 后移一个位置 若R j 的关键字小于或等于R i 的关键字 则查找过程结束 j 1即为R i 的插入位置 因为关键字比R i 大的记录已经后移 故只需将R i 插入该位置即可 2 插入排序 直接插入排序 6 监视哨算法引进了一个附加记录R 0 其作用有两个 1 进入查找循环之前 它保存了R i 的副本 使得不致于因记录的后移而丢失R i 中的内容 2 在while循环中 监视 下标变量j是否越界 以避免循环内每次都要检测j是否越界 因此将R 0 称为 监视哨 这使测试循环条件的时间大约减少一半 2 插入排序 直接插入排序 7 算法分析整个排序过程只有两种运算 即比较关键字和移动记录 算法有内外两层循环 外循环表示要进行n 1趟插入排序 内循环则表示每一趟排序所需进行的关键字的比较和记录的移动 在文件正序时 关键字的比较次数和记录移动次数均取得最小值 每趟排序的关键字比较次数为1 记录移动次数为2 即 总的比较次数为Cmin n 1 总的移动次数为Mmin 2 n 1 2 插入排序 直接插入排序 当文件逆序时 关键字的比较次数和记录移动次数均取得最大值 对于要插入的第i记录 均要和前i 1个记录及 监视哨 的关键字进行比较 即每趟要进行i次比较 从移动记录的次数来讲 每趟排序中除了上面的两次移动外 还需要将关键字大于R i 的i 1个记录后移一个位置 总的比较次数和记录的移动次数为 2 插入排序 直接插入排序 由以上分析可知 当记录关键字的分布情况不同时 算法在执行过程中的时间消耗是不同的 在记录分布随机情况下 即关键字可能出现的各种排列的概率相同 则可取上面两种情况的平均值作为比较和记录移动的平均次数 约为n2 4 因此直接插入排序的时间复杂度为O n2 空间复杂度为O 1 直接插入排序是稳定的排序方法 2 插入排序 直接插入排序 练习 初始化 99 17 23 45 60 38 47 83第1趟 17 99 23 45 60 38 47 83第2趟 17 23 99 45 60 38 47 83第3趟 17 23 45 99 60 38 47 83第4趟 17 23 45 60 99 38 47 83第5趟 17 23 38 45 60 99 47 83第6趟 17 23 38 45 47 60 99 83第7趟 17 23 38 45 47 60 83 99 已知待排序列为 99 17 23 45 60 38 47 83 请写出直接插入排序的基本思路 并写出直接插入排序每一趟的排序结果 2 2希尔排序该方法是由D L Shell在1959年提出的 又称缩小增量排序 Diminishing incrementsort 1 基本思想设待排序的数据对象有n个 先取一个整数d1 n作为第一个增量 将文件中的全部记录分为d1个组 所有距离为d1的记录放在同一个组中 在每一个组中分别进行直接插入排序 然后取第二个增量d2 d1 如取d2 d1 2 重复上述的分组和排序工作 直到最后取dl 1为止 此时 所有的记录放在同一组中进行直接插入排序 2 插入排序 希尔排序 2 排序实例设待排序的数据对象有8个 增量序列取值依次为4 2 1 最后结果为 1523366172788394 2 插入排序 希尔排序 3 希尔排序算法设计 带监视哨设某一趟希尔排序的增量为h 则整个文件被分成h组 R1 Rh 1 R2h 1 R2 Rh 2 R2h 2 Rh R2h R3h 因为各组记录的距离均为h 故第一组至第h组的监视哨的位置依次为1 h 2 h 0 如果像直接插入排序那样 将待插入记录Ri在查找插入位置之前保存到监视哨中 必须计算Ri属于哪一组 才能决定使用哪个监视哨来保存Ri 这样处理不太方便 R1 h R2 h R3 h R0 R1 R2 R3 Rh Rh 1 Rh 2 Rh 3 R2h 1 R2h Rn 2 插入排序 希尔排序 具体做法 R1 h R2 h R3 h R0 R1 R2 R3 Rh Rh 1 Rh 2 Rh 3 R2h 1 Rna 监视哨值的设定为了避免这种计算 我们可以将Ri保存到另一个辅助记录x中 而将所有监视哨R1 h R2 h R0的关键字设置为小于文件中任何果关键字即可 b 监视哨个数的设定因为增量是变化的 所以各趟排序中所需的监视哨数目也不同 所以按照最大增量d来设置监视哨 2 插入排序 希尔排序 3 希尔排序算法实现rectypeR n d R 0 R d 1 为d个监视哨intd t d 0 d t 1 为增量序列SHELLSORT rectypeR intd inti j k h rectypetemp 中间寄存变量intmaxint 32767 最大整数值for i 0 i d 0 i R i key maxint 所有哨兵的值置为最大负整数值k 0 设置增量序列的开始值do h d k 取出本趟增量for i h d 1 i n d i R h d R h d 1 插入到当前有序区 temp R i 保存待插入记录j i h 确定当前有序区的最后一个位置while temp key R j key 查找正确的插入位置 R j h R j 后移记录j j h 得到前一记录位置 R j h temp 插入R j 本趟排序完成k 取下一趟排序的增量 while h 1 增量为1排序后终止算法 为何从h d 1开始 为何在d 0 取值 为何是i 为何是j i h 2 插入排序 希尔排序 增量为何为h 4 希尔排序的特点本质上还是一种插入排序 其主要特点是 每一趟以不同的增量进行排序 希尔排序速度快的原因分析 a 大跨步踊跃式的插入排序在前面几趟希尔排序中 记录的比较是和同一组的前一个关键字进行比较 由于此时增量取值较大 所以关键字较小的记录在排序过程中就不是一步一步的向前移动 而是跳跃的移动 b 增量大时 每组记录少 插入排序快c 增量小时 基本有序的插入排序快随着增量的减小 每组中的记录最多 此时记录已基本有序 因此在进行最后一趟增量为1的插入排序时 只需进行少量的比较和移动便可完成排序 从而提高了排序速度 2 插入排序 希尔排序 5 希尔排序中增量di的取法 可有多种取法 至于如何选择di才能产生最好的排序效果 这涉及到许多数学问题 至今未得到完全解决 Shell本人提出 取 d1 n 2 d2 d1 2 di 1 平均比较次数和平均移动次数为n1 3左右 希尔排序的速度比直接插入排序快 但是不稳定的排序方法 2 插入排序 希尔排序 练习 已知待排序列为 99 17 23 45 60 38 47 83 请写出希尔排序的基本思路 并写出希尔排序在增量序列为4 2 1下每一趟的排序结果 99 17 23 45 60 38 47 83 d 4 60 17 23 45 99 38 47 83 d 2 23 17 47 38 60 45 99 83 d 1 17 23 38 45 47 60 83 99 本章主要内容 1 排序的基本概念2 插入排序3 选择排序4 交换排序5 归并排序 第十四章排序 1 选择排序的基本思想每一趟次从待排序的记录中选出关键字最小的记录 依次放在已有序的记录序列的最后面 直到全部数列有序 选择排序分为两种 直接选择排序堆排序 3 选择排序 2 直接选择排序的基本思想第一趟排序是在无序区R 0 R n 1 中选出最小的记录 将它与R 0 交换 形成有序区 R 0 无序区 R 1 R n 1 两部分 第二趟排序是在无序区R 1 R n 1 中选出最小的记录 将它与R 1 交换 形成有序区 R 0 R 1 无序区 R 2 R n 1 两部分 第i趟排序时 R 0 R i 2 已经是有序区 在无序区R i 1 R n 1 中选出最小的记录 将它与R i 1 交换 形成有序区 R 0 R i 1 无序区 R i R n 1 两部分 重复以上步骤 进行n 1趟排序后 整个文件全部递增有序 3 选择排序 3 直接选择排序实例初始关键字 4938659776132749 第一趟排序13 38659776492749 第二趟排序1327 659776493849 第三趟排序132738 9776496549 第四趟排序13273849 76976549 第五趟排序1327384949 976576 第六趟排序1327384949 65 9776 第七趟排序1327384949 6576 97 3 选择排序 找无序区的最小值 并与无序区的第一个记录交换 4 直接选择排序算法实现SEL