知识卡片

普通读书笔记卡 · 5654.d.1.a.6.a.1

低位基数排序依赖逐轮稳定

理解等级:中级

先按最低位稳定排序,再逐位向高位处理。高位决定主要次序,而稳定性保留同一高位组内已经形成的低位次序,所以最终得到完整数值顺序。

成本为位数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. 对学号的第 位