算法22内部排序基数排序.ppt

第9章内部排序 基数排序 2 10 6基数排序 RadixSort 问题 1 什么是 多关键字 排序 实现方法 2 单逻辑关键字怎样 按位值 排序 基本思想 借助多关键字排序的思想对单逻辑关键字进行排序 即 用关键字不同的位值进行排序 多关键字排序 例1 对一副扑克牌该如何排序 若规定花色和面值的顺序关系为 花色 面值 2 3 4 5 6 7 8 9 10 J Q K A则可以先按花色排序 花色相同者再按面值排序也可以先按面值排序 面值相同者再按花色排序 10 6基数排序 例2 职工分房该如何排序 规定 先以总分排序 职称分 工龄分 总分相同者 再按配偶总分排序 其次按配偶职称 工龄 人口 等等排序 例3 学生评奖学金如何排序 多关键字排序的实现方法通常有两种 最高位优先法MSD MostSignificantDigitfirst 最低位优先法LSD LeastSignificantDigitfirst 10 6基数排序 对一副扑克牌的排序若规定花色为第一关键字 高位 面值为第二关键字 低位 则使用MSD和LSD方法都可以达到排序目的 MSD方法的思路 先设立4个花色 箱 将全部牌按花色分别归入4个箱内 每个箱中有13张牌 然后对每个箱中的牌按面值进行插入排序 或其它稳定算法 LSD方法的思路 先按面值分成13堆 每堆4张牌 然后对每堆中的牌按花色进行排序 用插入排序等稳定的算法 用哪种方法更快些 单逻辑关键字 按位值 排序 设n个记录的序列为 V0 V1 Vn 1 可以把每个记录Vi的单关键码Ki看成是一个d元组 Ki1 Ki2 Kid 则其中的每一个分量Kij 1 j d 也可看成是一个关键字 注1 Ki1 最高位 Kid 最低位 Ki共有d位 可看成d元组 注2 每个分量Kij 1 j d 有radix种取值 则称radix为基数 思路 讨论 是借用MSD方式来排序呢 还是借用LSD方式 例 初始关键字序列T 32 19 27 32 13 30 请分别用MSD和LSD进行排序 并讨论其优缺点 法1 MSD 原始序列 32 19 27 32 13 30先按高位Ki1排序 19 13 27 32 32 30 再按低位Ki2排序 13 19 27 30 32 32 法2 LSD 原始序列 32 19 27 32 13 30先按低位Ki2排序 30 32 32 13 27 19再按高位Ki1排序 13 19 27 30 32 32 MSD存在递归效率受影响 LSD只需进行线性扫描 用链队列来实现基数排序 链式基数排序 实现思路 针对d元组中的每一位分量 把原始链表中的所有记录 按Kij的取值 让j d d 1 1 先 分配 到radix个链队列中去 然后再按各链队列的顺序 依次把记录从链队列中 收集 起来 分别用这种 分配 收集 的运算逐趟进行排序 在最后一趟 分配 收集 完成后 所有记录就按其关键码的值从小到大排好序了 实现以下关键字序列的链式基数排序 T 278 109 063 930 589 184 505 269 008 083 例 第一趟分配 e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 184 083 589 505 063 269 278 930 008 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 原始序列链表 r 0 从最低位i 3开始排序 f 是队首指针 e 为队尾指针 第一趟收集 r 0 109 2020 4 21 e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 063 278 269 083 184 505 109 930 589 008 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 第二趟分配 按次低位i 2 第一趟收集的结果 第二趟收集 r 0 r 0 2020 4 21 e 0 e 1 e 2 e 3 e 4 e 5 e 6 e 7 e 8 e 9 083 008 930 589 184 109 269 505 063 278 f 0 f 1 f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 第三趟分配 按最高位i 1 r 0 排序结束 r 0 第二趟收集的结果 第三趟收集 基数排序算法分析 假设有n个记录 每个记录的关键字有d位 每个关键字的取值有radix个 则需要radix个队列 进行d趟 分配 与 收集 因此时间复杂度 O d n radix 基数排序需要增加n 2radix个附加链接指针 空间效率低空间复杂度 O radix 稳定性 稳定 一直前后有序 用途 若基数radix相同 对于记录个数较多而关键码位数较少的情况 使用链式基数排序较好 特点 不用比较和移动 改用分配和收集 时间效率高 2020 4 21 链表基数排序的算法 voidRadixSort 选下一关键字 直到本趟分配完 2020 4 21 j 0 开始从0号队列 总共radix个队 开始收集while f j 0 j 若是空队列则跳过r 0 next p f j 建立本趟收集链表的头指针intlast e j 建立本趟收集链表的尾指针for k j 1 k radix k 逐个队列链接 收集 if f k 若队列非空r last next f k last e k 队尾指针链接 r last next 0 本趟收集链表之尾部应为0 RadixSort在此算法中 数组r n 被反复使用 用来存放原始序列和每趟收集的结果 记录从未移动 仅指针改变 2020 4 21 特点 不用比较和移动 改用分配和收集 时间效率高 假设有n个记录 每个记录的关键字有d位 每个关键字的取值有radix个 则需要radix个队列 进行d趟 分配 与 收集 因此时间复杂度 O d n radix 基数排序需要增加n 2radix个附加链接指针 空间效率低空间复杂度 O radix 稳定性 稳定 一直前后有序 用途 若基数radix相同 对于记录个数较多而关键码位数较少的情况 使用链式基数排序较好 1 平方阶 O n2 排序一般称为简单排序 例如直接插入 直接选择和冒泡排序 2 线性对数阶 O nlgn 排序如快速 堆和归并排序 3 O n1 阶排序 是介于0和1之间的常数 即0 1 如希尔排序 按平均时间将排序类 9 7内部排序方法的比较 17 1 各种方法的时 空优劣 判定树模型 如下图所示 说明对a b c进行分类的一棵判定树 当判断条件成立时 转向左 否则转向右 2 比较法分类的下界 O nlogn a b a b c a c b c a c b c a c b c a b c b a b a c b c a no yes yes yes yes yes no no no no 注意 树高代表比较的代价 因此只要知道了树高和结点数n的关系 就可以求出用比较法进行排序时的时间代价 另外 n个结点的分类序列 其叶子结点共有n 片 9 7内部排序方法的比较 18 n n2 0 n2 1 n n2 0 n2 1 nlog2n n2 0 n2 log2n n n2 0 n 1 nlog2n nlog2n 1 nlog2n nlog2n n dn n 9 7内部排序方法的比较 因为不同的排序方法适应不同的应用环境和要求 所以选择合适的排序方法应综合考虑下列因素 待排序的记录数目n 记录的大小 规模 关键字的结构及其初始状态 对稳定性的要求 语言工具的条件 存储结构 时间和辅助空间复杂度等 影响排序效果的因素 9 7内部排序方法的比较 1 若n较小 如n 50 可采用直接插入或直接选择排序 当记录规模较小时 直接插入排序较好 否则因为直接选择移动的记录数少于直接插人 应选直接选择排序为宜 2 若文件初始状态基本有序 指正序 则应选用直接插人 冒泡或随机的快速排序为宜 3 若n较大 则应采用时间复杂度为O nlgn 的排序方法 快速排序 堆排序或归并排序 快速排序是目前基于比较的内部排序中被认为是最好的方法 当待排序的关键字是随机分布时 快速排序的平均时间最短 堆排序所需的辅助空间少于快速排序 并且不会出现快速排序可能出现的最坏情况 这两种排序都是不稳定的 不同条件下排序方法的选择 2020 4 21 外部排序与文件 2020 4 21 1 外部排序 待排序的记录数量巨大 无法一次调入内存 只能驻留在外存上 磁带 磁盘 CD ROM 上 不能使用内部排序的方法进行排序 否则将引起频繁访问外存 外部排序主要的时间开销用在信息的内 外存交换上 所以减少I O时间成为要解决的主要问题 2020 4 21 1 外部排序的方法 外部排序的基本过程由相对独立的两个步骤组成 按可用内存大小 利用内部排序方法 构造若干个记录的有序子序列写入外存 通常称这些记录的有序子序列为 归并段 通过 归并 逐步扩大 记录的 有序子序列的长度 直至外存中整个记录序列按关键字有序为止 2020 4 21 例如 假设有一个含10 000个记录的磁盘文件 而当前所用的计算机一次只能对1 000个记录进行内部排序 则首先利用内部排序的方法得到10个初始归并段 然后进行逐趟归并 假设进行2 路归并 即两两归并 则第一趟由10个归并段得到5个归并段 第二趟由5个归并段得到3个归并段 第三趟由3个归并段得到2个归并段 最后一趟归并得到整个记录的有序序列 2020 4 21 假设 数据块 的大小为200 即每一次访问外存可以读 写200个记录 则对于10 000个记录 处理一遍需访问外存100次 读和写各50次 1 求得10个初始归并段需访问外存100次 2 每进行一趟归并需访问外存100次 3 总计访问外存100 4 100 500次若对上述例子采用5 路归并 则只需进行2趟归并 总的访问外存的次数为100 2 100 300次 2020 4 21 一般情况下 假设待排记录序列含m个初始归并段 外排时采用k 路归并 则归并趟数s logkm 显然 随着k的增大或m的减小 归并的趟数将减少 因此对外排而言 通常采用多路归并 k的大小可选 但需综合考虑各种因素 2020 4 21 2 多路平衡归并的实现 1 9 5 7 29 5 9 5 7 6 5 4 3 2 516495278 712258491 2938576671 922474859 5 输入缓冲区 4路平衡归并 胜者树及其使用 2020 4 21 胜者树及其使用 9 7 7 29 16 9 7 516495278 712258491 2938576671 922474859 7 6 5 4 3 2 1 输入缓冲区 输出缓冲区 7 7 9 16 7 29 9 7 6 5 4 3 2 1 57 2020 4 21 胜者树及其使用 9 12 12 29 16 9 9 516495278 712258491 2938576671 922474859 7 6 5 4 3 2 1 输入缓冲区 输出缓冲区 9 12 9 16 12 29 9 7 6 5 4 3 2 1 579 2020 4 21 改进 采用胜者树 从K个元素中选取最小元素之后 从根结点到它的相应的叶子结点路径上的结点都需要进行修改 为了加快程序运行的速度产生了败者树 2020 4 21 败者树及其使用 2 1 7 29 5 9 3 b 0 ls 1 输入缓冲区 输出缓冲区 9 7 29 5 7 29 9 7 6 5 4 3 2 1 注意 挑出冠军需要进行k 1次比较 此处需要比较3次 0 ls 0 0 5 ls 2 ls 3 b 1 b 2 b 3 516495278 712258491 2938576671 922474859 5 2020 4 21 2 0 7 29 16 9 3 516495278 712258491 2938576671 922474859 b 0 ls 1 输入缓冲区 输出缓冲区 57 注意 挑出冠军需要进行k 1次比较 此处需要比较3次 1 ls 2 ls 3 b 1 b 2 b 3 2020 4 21 多路平衡归并的实现 败者树 2 0 12 29 16 9 1 516495278 712258491 2938576671 922474859 b 0 ls 1 输入缓冲区 输出缓冲区 579 注意 挑出冠军需要进行k 1次比较 此处需要比较3次 3 ls 0 ls 2 ls 3 b 1 b 2 b 3 2020 4 21 3 文件 1 文件 大量性质相同的记录的集合 和 查找表 的差别在于 文件 指的是存储在外存储器中的记录的集合 记录是文件中可以存取的数据的基本单位 2020 4 21 2 文件可按其中记录的类型不同而分成两类 操作系统的文件 文件中的记录仅是一个字符组 由于操作系统中的文件仅是一维的连续字符序列 为了用户存取和加工的方便 将文件中的信息划分为若干组 其中每一组信息称作一个记录 数据库文件 文件中的记录带有结构 是数据项的集合 记录是文件中可以存取的数据基本单位 数据项是文件中可以使用的数据最小单位 还可分为定长记录文件和不