8.5.2 基数排序
原书定位
印刷页P371起,对应PDF第383页。下文为目视整理的知识提要;完整内容见原书对照。
把关键字看作 位、每位基数 的复合关键字。LSD 从最低位到最高位逐趟稳定分配、收集;MSD 从高位分组,再分别处理各组的低位。
LSD 每一趟都必须稳定,才能保留前面已建立的低位次序。队列顺序入队并按桶序首尾收集可实现稳定性;十进制按位排序用 10 个桶,与位数或记录数无关。
时间 。链式实现若复用记录链接,额外桶头尾指针为 ;数组实现通常还需 缓冲空间。数据位数不足时应按统一规则补位;负数和变长字符串需相应约定,不能直接机械套用非负定长整数流程。

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

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

第三趟按百位分配与收集,原书P373。
对应练习
关联知识
原书对照
展开原书对照截图


