知识卡片

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

计数排序成本取决于值域

理解等级:中级

为每个可能整数值准备计数槽,扫描输入累加次数,再按索引顺序还原值,就能利用值域顺序完成排序。成本为O(n+R),其中R是实际覆盖范围。

数据数量多但值域小才适合,范围极大时计数数组可能比比较排序更贵。原书非负版本还要求max+1不溢出,负数需明确保序偏移;偏移和范围计算本身也要在可表示范围。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      计数排序适用于数据量大但数据范围较小的情况。比如,在上述示例中 不能太大,否则会占用过多空间。 而当 时,计数排序使用 时间,可能比 log 的排序算法还要慢。 11.10 基数排序 上一节介绍了计数排序,它适用于数据量

    参考来源

    - 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[6189,6299)) - 结论依据:实际counter代码与严格值域限制,保留R而不省略为n。 - 原始内容:计数排序适用于数据量大但数据范围较小的情况。比如,在上述示例中 不能太大,否则会占用过多空间。 而当 时,计数排序使用 时间,可能比 log 的排序算法还要慢。 11.10 基数排序 上一节介绍了计数排序,它适用于数据量