8.5.2 基数排序

教材导航 · 第8章

原书定位

印刷页P371起,对应PDF第383页。下文为目视整理的知识提要;完整内容见原书对照。

把关键字看作 dd 位、每位基数 rr 的复合关键字。LSD 从最低位到最高位逐趟稳定分配、收集;MSD 从高位分组,再分别处理各组的低位。

LSD 每一趟都必须稳定,才能保留前面已建立的低位次序。队列顺序入队并按桶序首尾收集可实现稳定性;十进制按位排序用 10 个桶,与位数或记录数无关。

时间 O(d(n+r))O(d(n+r))。链式实现若复用记录链接,额外桶头尾指针为 O(r)O(r);数组实现通常还需 O(n+r)O(n+r) 缓冲空间。数据位数不足时应按统一规则补位;负数和变长字符串需相应约定,不能直接机械套用非负定长整数流程。

第一趟按个位分配与收集

第一趟按个位分配与收集,原书P372。

第二趟按十位分配与收集

第二趟按十位分配与收集,原书P372。

第三趟按百位分配与收集

第三趟按百位分配与收集,原书P373。

对应练习

8.5 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P371,PDF第383页

原书对照,原书P372,PDF第384页

原书对照,原书P373,PDF第385页