知识卡片
计数排序利用有限键域
对 n 个整数且每个值属于 [0,k) 的输入,先分配 k 个计数桶并统计频次,再按桶序输出相应数量的值。时间 O(n+k),辅助空间 O(k);只有 k=O(n) 等条件下才能写成 O(n)。
若键域远大于数据量,初始化和扫描空桶的代价可能超过收益。比较排序下界只适用于比较模型;利用整数键直接索引使用了不同的信息和操作。
93说明使用有限全序的映射:对于正整数 p,1/p 随 p 增大而减小,若 p 在有效范围内,则可选择反向映射使桶序对应数值升序。实际使用应检查映射范围、重复键以及空间成本;该方法不是所有固定范围整数问题的无条件最佳选择。
94进一步强调桶序需要与所需全序一致;映射只作为分组标签而不保序时,直接按桶序输出会得到错误排序。
96正确指出输出写入总共 n 次,但遗漏 k 个桶的初始化与扫描,完整成本应为 O(n+k),而不是无条件 O(n)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 计数排序利用有限键域
- · 使用环境
- · 驱动因素
- · 分析
原书出处 · 4 处
- · 查看原书依据
计数排序 一个会计师负责对一个小饭店的账本进行审核。每天晚上饭店打烊时,饭店主人记录白天的总销售额,然后打印出有总额和日期的收据。这些收据存放在一个大盒子里面。每年年终,会计师审核盒子中的这些收据,检查是否有的已经丢失。你能想象,盒子中的收据都是无序状态的。 会计师可以按照日期降序地排列所有的收据,
- · 查看原书依据
全序能够被决定以及每一个元素的值都是唯一的,这个算法也可用。例如,如果排序一系列形如1/p(p为整数)的小数,p的最大值为k,那么每个小数1/p能够被分配一个唯一的值k-p。 图 4-17 计数排序详解
- · 查看原书依据
全序关系,所以计数排序能成功进行排序。
- · 查看原书依据
2*n次,结果总的性能是O(n)的。 因为待排序的数组中的元素必须是从有限的k个元素中得到,计数排序的使用受到了限制。我们现在讨论桶排序,这个排序方法克服了这个限制,每个元素都能够映射到一个桶中。