第八章-排序要点

第八章排序 内容提要 五类内部排序方法 插入排序 交换排序 选择排序 归并排序和基数排序 的基本思想 排序过程 实现的算法 算法的效率分析及排序的特点 各种排序方法的比较和选择 最后简单介绍外部排序 2 排序的功能是将一个数据元素 记录 的任意序列 重新排列成一个按关键字有序的序列 排序的定义 3 排序的分类 按待排序记录所在位置内部排序 待排序记录存放在内存外部排序 排序过程中需对外存进行访问的排序按排序依据原则插入排序 直接插入排序 折半插入排序 希尔排序交换排序 冒泡排序 快速排序选择排序 简单选择排序 堆排序归并排序 2 路归并排序 4 排序的基本操作 比较两个关键字大小将记录从一个位置移动到另一个位置 5 定义待排序的记录的数据类型为 typedefstruct intkey elemtypedata redtype redtyper n 排序对象的数据类型 基本思想 每步将一个待排序的记录 按其关键字值的大小插入到前面已经排序的文件中适当的位置上 直到全部插完为止 插入排序 基本思路是依次把待排序的记录逐一按其关键字的大小插入到一个已经排好序的有序序列中去 直到所有的记录插完为止 得到一个新的有序序列 插入排序 直接插入排序 8 例 49386597761327 i 238 3849 6597761327 i 365 384965 97761327 i 497 38496597 761327 i 576 3849657697 1327 i 613 133849657697 27 i 1 i 7 133849657697 27 27 97 76 65 49 38 27 比较次数移动次数 21 10 21 10 65 65 插入排序 直接插入排序 9 1 设置监视哨r 0 将待插入记录的值赋给r 0 2 设置开始查找的位置j 3 在数组中进行搜索 搜索中将第j个记录后移 直至r 0 key r j key为止 4 将r 0 插入在r j 1 的位置上 直接插入排序算法 10 按平均比较次数计算 将n个记录进行直接插入排序所需的平均比较次数为 直接插入排序算法分析 直接插入排序的时间复杂度为O n2 空间复杂度为O 1 直接插入排序是一种稳定的排序方法 11 插入排序 希尔排序 希尔排序的作法是 选定第一个增量d1 n 把全部记录按此值从第一个记录起进行分组 所有相距为d1的记录作为一组 先在各组内进行插入排序 然后减小间隔 取第二个增量d2 d1 重复上述分组和排序过程 直至增量值di 1为止 即所有的记录放在同一组内排序 12 13 1 外循环以各种不同的间隔距离d进行排序 直到d 1为止 2 第二重循环是在某一个d值下对各组进行排序 若在某个d值下发生了记录的交换 则需继续第三重循环循环 直至各组内均无记录的交换为止 即各组内已完成排序任务 3 第三重循环是从第一个记录开始 按某个d值为间距进行组内比较 若有逆序 则进行交换 插入排序 希尔排序算法 14 主要特点是每一趟以不同的增量进行插入排序 当d较大时 被移动的记录是跳跃式进行的 到最后一趟排序时 d 1 许多记录已经有序 不需要多少移动 所以能提高了排序的速度 希尔排序是不稳定的排序方法 希尔排序算法分析 15 交换排序 交换排序是通过两两比较待排序记录的关键值 交换不满足顺序的那些偶对 直到全部满足为止 交换排序 冒泡排序 将第一个记录的关键字与第二个记录的关键字进行比较 若为逆序r 1 key r 2 key 则交换 然后比较第二个记录与第三个记录 依次类推 直至第n 1个记录和第n个记录比较为止 第一趟冒泡排序 结果关键字最大的记录被安置在最后一个记录上 对前n 1个记录进行第二趟冒泡排序 结果使关键字次大的记录被安置在第n 1个记录位置 重复上述过程 直到 在一趟排序过程中没有进行过交换记录的操作 为止 17 例 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 交换排序 冒泡排序 18 由上述算法可见 当初始序列中记录已按关键字次序排好序 则只需要进行一趟排序 在排序过程中只需要进行n 1次比较 记录移动次数为0 反之 若初始序列中记录按逆序排列 若待排序的序列有n个记录 最多进行n 1趟排序 最大比较次数为 交换记录时移动记录的次数也约为3n2 2次 故总的时间复杂度为O n2 冒泡排序是稳定的 冒泡排序算法分析 交换排序 快速排序 基本思想 通过一趟排序 将待排序记录分割成独立的两部分 其中一部分记录的关键字均比另一部分记录的关键字小 则可分别对这两部分记录进行排序 以达到整个序列有序 20 对r s t 中记录进行一趟快速排序 附设两个指针i和j 设枢轴记录rp r s x rp key初始时令i s j t首先从j所指位置向前搜索第一个关键字小于x的记录 并和rp交换再从i所指位置起向后搜索 找到第一个关键字大于x的记录 和rp交换重复上述两步 直至i j为止再分别对两个子序列进行快速排序 直到每个子序列只含有一个记录为止 快速排序的排序过程 21 完成一趟排序 273813 49 76976550 分别进行快速排序 13 27 38 49 5065 76 97 快速排序结束 1327384950657697 49 27 49 65 13 49 49 97 快速排序的排序过程 22 1 确定第一个记录为基准记录r t 先从j所指示的位置起向前扫描 当r t key r j key时 交换r t key和r j key 使关键字值比基准记录的关键字值小的记录交换到前面 2 从i所指示的位置起向后扫描 直到r t key r i key 交换r t key和r i key 使关键字值比基准记录的关键字值大的记录交换到后面 3 重复 1 和 2 直至i j为止完成一趟排序 4 只要t w 重复 1 至 3 分别对基准记录两边的部分进行排序 快速排序的排序算法 23 快速排序平均时间复杂度为O nlog2n 最坏情况下时间复杂度为O n2 快速排序所需的比较次数反而最多 快速排序法不稳定 快速排序需要一个栈空间来实现递归 栈的最大深度为 log2n 1 所需栈空间为O log2n 最坏情况下 递归深度为n 所需栈空间为O n 快速排序的排序算法分析 24 选择排序 选择排序是指每次从待排序的记录中选出关键字值最小 或最大 的记录 顺序放在已排序的有序序列中 直到全部排完 选择排序主要包括简单选择排序和堆排序两种 25 选择排序 简单选择排序 首先通过n 1次关键字比较 从n个记录中找出关键字最小的记录 将它与第一个记录交换再通过n 2次比较 从剩余的n 1个记录中找出关键字次小的记录 将它与第二个记录交换重复上述操作 共进行n 1趟排序后 排序结束 26 例 初始 49386597761327 i 1 13 49 一趟 13 386597764927 i 2 27 38 六趟 132738496576 97 排序结束 13273849657697 27 1 查找待排序序列中最小的记录 并将它和该区间第一个记录交换 2 重复 1 到第n 1次排序后结束 简单选择排序算法 28 简单选择排序所需要的总的比较次数为O n2 当初始文件是有序时 最小移动记录次数等于0 而当初始文件是逆序时 每次都要交换记录 直接选择排序是不稳定的 简单选择排序算法分析 29 选择排序 堆排序的引入 堆排序是简单选择排序的改进 用直接选择排序从n个记录中选出关键字值最小的记录要做n 1次比较 然后从其余n 1个记录中选出最小者要作n 2次比较 显然 相邻两趟中某些比较是重复的 为了避免重复比较 可以采用树形选择排序比较 30 a 求出最小关键字3 b 求出次小关键字11图8 8树形选择排序 31 树形选择排序总的比较次数为O nlog2n 与直接选择排序比较 减少了比较次数 但需要增加额外的存储空间存放中间比较结果和排序结果 选择排序 堆排序的引入 32 n个元素的序列 k1 k2 kn 当且仅当满足下列关系时 称之为堆 例 96 83 27 38 11 9 例 13 38 27 50 76 65 49 97 可将堆序列看成完全二叉树 则堆顶元素 完全二叉树的根 必为序列中n个元素的最小值或最大值 堆的定义 33 堆排序的基本思路 对一组待排序的记录序列 先将其关键字按堆的定义排列 个序列 称初建堆 找到了最小 最大 关键字 将其取出 用剩余的n 1个元素再重建堆 便可得到次小 次大 值 如此反复执行 直到全部关键字排好序为止 堆排序的基本思路 34 例 35 36 37 堆排序的关键问题 堆排序需解决的两个问题 如何由一个无序序列建成一个堆 如何在输出堆顶元素之后 调整剩余元素 使之成为一个新的堆 38 堆排序的关键问题 第二个问题解决方法 筛选方法 输出堆顶元素之后 以堆中最后一个元素替代之 然后将根结点值与左 右子树的根结点值进行比较 并与其中小者进行交换 重复上述操作 直至叶子结点 将得到新的堆 称这个从堆顶至叶子的调整过程为 筛选 第一个问题解决方法 建堆方法 从无序序列的第 n 2 个元素 即此无序序列对应的完全二叉树的最后一个非终端结点 起 至第一个元素止 进行反复筛选 39 例 含8个元素的无序序列 49 38 65 97 76 13 27 50 建堆过程 40 堆排序只需要一个记录大小的辅助空间 堆排序算法的时间复杂度为O nlogn 堆排序是一种不稳定的排序方法 堆排序的算法及分析 41 归并排序 归并排序 把两个或多个有序表进行合并 得到一个新的有序表 将两个有序子文件合并成一个有序文件 称为二路归并 42 设初始序列含有n个记录 则可看成n个有序的子序列 每个子序列长度为1两两合并 得到 n 2 个长度为2或1的有序子序列再两两合并 如此重复 直至得到一个长度为n的有序序列为止 2 路归并排序过程 43 例 初始关键字 49 38 65 97 76 13 27 一趟归并后 3849 6597 1376 27 二趟归并后 38496597 132776 三趟归并后 13 27 38 49 65 76 97 2 路归并排序过程 44 2 路归并排序的关键问题 合并是归并排序的核心 即将两个首尾相连的有序子表合并成一个有序子表 在合并的基础上进行一趟排序 在一趟排序的基础上完成多趟排序 45 1 设数组r中第一个有序子表从第h个记录开始至第m个记录为止 即r h 到r m 第二个有序子表从第m 1个记录开始到第w个记录为止 即r m 1 到r w 最后形成的有序表为r h 到r w 2 设置I j k分别指向 1 中所指的三个有序表的第一个单元 3 比较r i 和r j 的关键字值的大小 若r i key r j key 则将第一个有序子表的记录r i 复制到数组a k 中 并使i k 4 否则 将第二个有序子表的记录r j 复制到a k 中 并使j k 依次类推 直到全部记录复制到r h 到r w 中 合并的算法 46 把数组r中的长度为s的相邻有序子表两两合并 归并成一个长度为2s的有序子表 存于t数组中 一趟归并的算法 47 思路是 第一趟有序子表长s为1 以后每趟s加倍 第一趟将r数组进行归并后存于t数组 第二趟将t数组归并后存于r数组 依次类推 若归并的趟数为奇数 需从t数组复制到r数组 多趟合并的算法 48 归并排序的总的时间复杂度为O nlog2n 归并排序需要的附加存储空间为O n 所需辅助空间较大 二路归并排序是稳定的 归并排序算法分析 49 基数排序 基数排序是和前面所述的各种排序方法完全不同的一种排序方法 前面介绍的几种排序方法 都是根据关键字之间的比较和移动记录来实现的 基数排序不需要进行记录关键字间的比较 而是根据组成关键字的各位值 即借助于多关键字排序的思想 用 分配 和 收集 的方法进行排序 50 多关键字的排序 假设有n个记录的序列 R1 R2 Rn 每个记录Ri中含有d个关键字 Ki0 Ki1 Kid 1 则称上述记录序列对关键字 Ki0 Ki1 Kid 1 有序是指 对于序列中任意两个记录Ri和Rj 1 i j n 都满足下列 词典 有序关系 Ki0 Ki1 Kid 1 Kj0 Kj1 Kjd 1 其中K0被称为 最主 位关键字 Kd 1被称为 最次 位关键字 51 实现多关键字排序通常有两种作法 最高位优先MSD法 先对K0进行排序 并按K0的不同值将记录序列分成若干子序列之后 分别对K1进行排序 依次类推 直至最后对最次位关键字排序完成为止 最低位优先LSD法 先对Kd 1进行排序 然后对Kd 2进行排序 依次类推 直至对最主位关键字K0排序完成为止 排序过程中不需要根据 前一个 关键字的排序结果 将记录序列分割成若干个 前一个 关键字不同的 子序列 52 例如 学生记录含三个关键字 系别 班号和班内的序列号 其中以系别为最主位关键字 LSD的排序过程如下 无序序列3 2 301 2 153 1 202 3 182 1 20对K2排序1 2 152 3 183 1 202 1 203 2 30对K1排序3 1 202 1 201 2 153 2 302 3 18对K0排序1 2 152 1 202 3 183 1 203 2 30 53 比较MSD法和LSD法 一般来讲 LSD法要比MSD法来得简单 因为LSD法是从头到尾进行若干次分配和收集 执行的次数取决于构成关键字值的成分为多少 而MSD法则要处理各序列与子序列的独立排序问题 就可能复杂一些 MSD法和LSD法的比较 54 链式基数排序 假如多关键字的记录序列中 每个关键字的取值范围相同 则按LSD法进行排序时 可以采用 分配 收集 的方法 其好处是不需要进行关键字间的比较 对于数字型或字符型的单关键字 可以看成是由多个数位或多个字符构成的多关键字 此时可以采用这种 分配 收集 的办法进行排序 称作基数排序法 55 链式基数排序 在计算机上实现基数排序时 应采用链表作存储结构 即链式基数排序 具体作法为 待排序记录以指针相链 构成一个链表 分配 时 按当前 关键字位 所取值 将记录分配到不同的 链队列 中 每个队列中记录的 关键字位 相同 收集 时 按当前关键字位取值从小到大将各队列首尾相链成一个链表 对每个关键字位均重复2 和3 两步 56 例如 p 369 367 167 239 237 138 230 139第一次分配得到f 0 230 r 0 f 7 367 167 237 r 7 f 8 138 r 8 f 9 369 239 139 r 9 第一次收集得到p 230 367 167 237 138 368 239 139 链式基数排序 57 第二次分配得到f 3 230 237 138 239 139 r 3 f 6 367 167 368 r 6 第二次收集得到p 230 237 138 239 139 367 167 368第三次分配得到f 1 138 139 167 r 1 f 2 230 237 239 r 2 f 3 367 368 r 3 第三次收集之后便得到记录的有序序列p 138 139 167 230 237 239 367 368 58 链式基数排序算法对数据进行d趟扫描 每趟需时间O n j 因此总的计算时间为O d n j 对于不同的基数j所用的时间是不同的 当n较大或d较小时 这种方法较为节省时间 基数排序适用于链式存储结构的记录的排序 它要求的附加存储量是j个队列的头 尾指针 所以 需要O n j 辅助空间 基数排序是一种稳定的排序方法 链式基数排序分析 59 各种内部排序方法性能比较 60 1 从平均时间而言 快速排序最佳 但在最坏情况下时间性能不如堆排序和归并排序 2 从算法简单性看 由于直接选择排序 直接插入排序和冒泡排序的算法比较简单 将其认为是简单算法 都包含在上图中的 简单排序 中 对于希尔排序 堆排序 快速排序和归并排序算法 其算法比较复杂 认为是复杂排序 3 从稳定性看 直接插入排序 冒泡排序和归并排序是稳定的 而希尔排序 直接选择排序 快速排序和堆排序是不稳定排序 4 从待排序的记录数n的大小看 n较小时 宜采用简单排序 而n较大时宜采用改进排序 各种内部排序方法性能比较 61 1 当待排序记录数n较大时 若要求排序稳定 则采用归并排序 2 当待排序记录数n较大 关键字分布随机 而且不要求稳定时 可采用快速排序 3 当待排序记录数n较大 关键字会出现正 逆序情形 可采用堆排序 或归并排序 4 当待排序记录数n较小 记录已接近有序或随机分布时 又要求排序稳定 可采用直接插入排序 5 当待排序记录数n较小 且对稳定性不作要求时 可采用直接选择排序 选择排序的方法 62 外部排序简介 在实际问题中 经常会遇到输入文件中记录的数量很大 计算机的内存不能容纳时 排序过程必须借助外部存储器才能完成 这时的排序就称为外部排序 63 外存信息的存取 磁带 磁带是涂上一层磁性材料的窄带 磁带卷在带盘上 带盘安装在磁带驱动器的转轴上 驱动器控制磁带盘转动 带动磁带移动 通过读 写磁头进行读 写信息的操作 64 磁盘存取信息时 首先要确定信息所在的柱面 再将磁头移动到所需磁道的位置上 移动磁头所需的时间称为磁头定位时间或称为寻道时间 然后等待磁道上的信息所在位置随着磁盘的转动而转到磁头下面 这段时间称为等待时间 由于磁盘高速运转 2400 3600转 分 所以 等待时间是极短的 磁盘的存取时间主要花在磁头定位时间上 外存信息的存取 磁盘 65 外部排序的基本方法 最常用的外部排序方法是归并排序法 这种方法由两个阶段组成 第一阶段是把磁盘文件逐段读入