知识卡片
计数桶写入前验证键和容量
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:计数排序的实现