知识卡片

普通读书笔记卡 · 5654.c.1.a.2.a.2.a.22 · 生成模型:未记录

计数桶写入前验证键和容量

理解等级:中级

03219–03220先calloc k 个int计数器,以输入值索引并累加,再逐桶重写整数。安全实现需验证 k 和 n 非负、每个键在 [0,k)、分配成功且计数类型足以容纳频次;还应明确空输入与错误返回。示例声明返回 int 却未返回值,不能可靠报告成功或失败。

直接重写值只适合无需保留附属记录的情况;若需稳定排序完整记录,可用前缀和确定位置并按合适顺序写入输出数组,其额外空间应计入。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      计数排序创建了k个桶用来存储输入数列中第k个元素值出现的次数。计数排序将对输入数列进行两次遍历。在第一次遍历中,计数排序增加桶的计数。在第二次遍历时,通过处理桶中得到的全序的计数值,计数排序重写原始的数列。例4-10是计数排序的一个实现,k的值是函数的一个参数。 例4-10:计数排序的实现

    参考来源

    - 位置:《算法技术手册》第4章《解决方案》(spine1520;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1483.html;u095-ch04-023)。 - 结论依据:95全文及03219–03220完整C实现实读;未编译或执行。 - 原始内容:计数排序创建了k个桶用来存储输入数列中第k个元素值出现的次数。计数排序将对输入数列进行两次遍历。在第一次遍历中,计数排序增加桶的计数。在第二次遍历时,通过处理桶中得到的全序的计数值,计数排序重写原始的数列。例4-10是计数排序的一个实现,k的值是函数的一个参数。 例4-10:计数排序的实现