知识卡片
低位基数排序依赖逐轮稳定
先按最低位稳定排序,再逐位向高位处理。高位决定主要次序,而稳定性保留同一高位组内已经形成的低位次序,所以最终得到完整数值顺序。
成本为位数d乘O(n+b),b是基数。原书十进制非负整数例中exp*=10可能溢出,应先限定输入并防止越界;浮点也并非原则上完全不能基数排序,但需要保序位表示转换,原书未展开这种实现。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
依次对每一位进行排序,从而得到最终的排序结果。 11.10.1 算法流程 = 1 以学号数据为例,假设数字的最低位是第 位,最高位是第 位,基数排序的流程如图11‑18 所示。 1. 初始化位数 。 2. 对学号的第 位
参考来源
- 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[6465,6575))
- 结论依据:实际radix逐位稳定计数和成本/限制说明,纠正固定表示浮点一概不适用。
- 原始内容:依次对每一位进行排序,从而得到最终的排序结果。 11.10.1 算法流程 = 1 以学号数据为例,假设数字的最低位是第 位,最高位是第 位,基数排序的流程如图11‑18 所示。 1. 初始化位数 。 2. 对学号的第 位