10.6&10.7 基数排序
时间：2025-04-19
数据结构第十章课件第6、7节
第10章 内部排序----基数排序
计算机科学技术学院 Email: lihua@http://www.77cn.com.cn
数据结构第十章课件第6、7节
10.6
基数排序 (Radix Sort)
基本思想： 借助多关键字排序的思想对单逻辑关键字进行排 序。即：用关键字不同的位值进行排序。
问题：1. 什么是“多关键字”排序？实现方法？
2. 单逻辑关键字怎样“按位值”排序？
数据结构第十章课件第6、7节
10.6
基数排序
多关键字排序例1:对一副扑克牌该如何排序？ 若规定花色和面值的顺序关系为： 花色： 面值：2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A 则可以先按花色排序，花色相同者再按面值排序 也可以先按面值排序，面值相同者再按花色排序。
数据结构第十章课件第6、7节
10.6
基数排序
例2:职工分房该如何排序？
规定：先以总分排序(职称分+工龄分);总分相同者，再按配偶总分排序，其次按配偶职 称、工龄、人口……等等排序。 例3:学生评奖学金如何排序？ 多关键字排序的实现方法通常有两种： 最高位优先法MSD(Most Significant Digit first) 最低位优先法LSD(Least Significant Digit first)
数据结构第十章课件第6、7节
对一副扑克牌的排序若规定花色为第一关键字(高位),面值为第二关键字 (低位),则使用MSD和LSD方法都可以达到排序目的。 MSD方法的思路：先设立4个花色“箱”,将全部牌按花 色分别归入4个箱内(每个箱中有13张牌);然后对每个 箱中的牌按面值进行插入排序(或其它稳定算法)。 LSD方法的思路：先按面值分成13堆(每堆4张牌),然 后对每堆中的牌按花色进行排序(用插入排序等稳定的 算法)。 用哪种方法更快些？
数据结构第十章课件第6、7节
单逻辑关键字“按位值”排序思路： 设n 个记录的序列为：{V0, V1, …, Vn-1 },可 以把每个记录Vi 的单关键码 Ki 看成是一个d元 组(Ki1, Ki2, …, Kid),则其中的每一个分量 Kij ( 1 j d ) 也可看成是一个关键字。注1: Ki1=最高位，Kid=最低位；Ki共有d位，可看成d
元组；注 2 : 每个分量 Kij (1 则称radix为基数。
j
d ) 有 radix 种取值，
数据结构第十章课件第6、7节
讨论：是借用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只需进行线性扫描
数据结构第十章课件第6、7节
例：T=(02,77,70,54,64,21,55,11),用LSD排序。 ①各关键字可视为2元组；②每位的取值范围是：0-9;即基数radix =10 。因此， 特设置10个队列，并编号为0-9。
原始序列1 2 3 4 5 6 7 80
2
10个队列70 21,11 02 54,64
出队后序列1 270 21
0 77 1 先对低位扫描 2 70 3 54 4 64 5 21 分配过 6 55 程 7 11 8 9 又称散列过程！
出队
55
收集过 程77
3 4 5 6 7 8
1102 54 64 55 77
下一步
数据结构第十章课件第6、7节
出队后序列1 2 3 4 5 6 7 870 21 11 02 54 64 55 77
再次入队0 102 11 21
再次出队后序列02 11
再对高位扫描
2 3 4 5 6 7 8 9
再次出队
21 54
再次分 配
54,55 64 70,77
55 64
再次收 集
70 77
小结：排序时经过了反复的“分配”和“收集”过程。 当对关键字所有的位进行扫描排序后，整个序列便 从无序变为有序了。 这种LSD排序方法称为:基数排序
数据结构第十章课件第6、7节
用链队列来实现基数排序— 链式基数排序 实现思路： 针对 d 元组中的每一位分量，把原始链表 中的所有记录, 按Kij的取值,让 j = d, d-1, …, 1 , ① 先“分配”到radix个链队列中去； ② 然后再按各链队列的顺序，依次把记录从链队列中 “收集”起来； ③ 分别用这种“分配”、“收集”的运算逐趟进行排 序； ④ 在最后一趟“分配”、“收集” 完成后，所有记 录就按其关键码的值从小到大排好序了。
数据结构第十章课件第6、7节
例
实现以下关键字序列的链式基数排序：738 921 485 637 101 215 530 790 306
T=(614,738,921,485,637, 101,215,530,790,306) 原始序列链表：
r[0]→ 614第一趟分配 e[0]
(从最低位 i = 3开始排序，f[ ] 是队首指针，e[ ] 为队尾指针)e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9]
e[1]
790 530 f[0]
101 921 f[1] f[2] f[3] 614 f[4]
215 485 f[5] 306 f[6] 637 f[7] 738 f[8] f[9]
第一趟收集(让队尾指针e[i] 链接到下一非空队首指针f[i+1 ]
即可)637 738
r[0]→ 530
790
921
101
614
485
215
306
数据结构第十章课件第6、7节
第一趟收集的结果：r[0]→ 530790 921 101 614 485 215 306 637 738
第二趟分配(按次低位 i = 2 ) e[0] e[1] e[2] e[3] 738 306 101 f[0] 215 614 f[1] 921 f[2] 637 e[4] e[5] e[6] e[7] e[8] e[9]
530f[3] f[4] f[5] f[6] f[7]
485 f[8] f[9]
790
第二趟收集(让队尾指针e[i] 链接到下一非空队首指针f[i+1 ]
)485 790
10.6&10.7 基数排序.doc
将本文的Word文档下载到电脑
