知识卡片

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

计数排序利用有限键域

理解等级:中级

对 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个元素中得到,计数排序的使用受到了限制。我们现在讨论桶排序,这个排序方法克服了这个限制,每个元素都能够映射到一个桶中。

    参考来源

    - 位置:《算法技术手册》第4章《计数排序》(spine1518;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1481.html;u092-ch04-022)。 - 结论依据:92全文及后续03218示意、03219–03220代码对照实读。 - 原始内容:计数排序 一个会计师负责对一个小饭店的账本进行审核。每天晚上饭店打烊时,饭店主人记录白天的总销售额,然后打印出有总额和日期的收据。这些收据存放在一个大盒子里面。每年年终,会计师审核盒子中的这些收据,检查是否有的已经丢失。你能想象,盒子中的收据都是无序状态的。 会计师可以按照日期降序地排列所有的收据, - 位置:《算法技术手册》第4章《使用环境》(spine1518;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1481.html;u093-ch04-022)。 - 结论依据:93说明使用有限全序的映射:对于正整数 p,1/p 随 p 增大而减小,若 p 在有效范围内,则可选择反向映射使桶序对应数值升序。实际使用应检查映射范围、重复键以及空间成本;该方法不是所有固定范围整数问题的无条件最佳选择。 - 原始内容:全序能够被决定以及每一个元素的值都是唯一的,这个算法也可用。例如,如果排序一系列形如1/p(p为整数)的小数,p的最大值为k,那么每个小数1/p能够被分配一个唯一的值k-p。 图 4-17 计数排序详解 - 位置:《算法技术手册》第4章《驱动因素》(spine1519;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1482.html;u094-ch04-022)。 - 结论依据:94进一步强调桶序需要与所需全序一致;映射只作为分组标签而不保序时,直接按桶序输出会得到错误排序。 - 原始内容:全序关系,所以计数排序能成功进行排序。 - 位置:《算法技术手册》第4章《分析》(spine1521;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1484.html;u096-ch04-022)。 - 结论依据:96正确指出输出写入总共 n 次,但遗漏 k 个桶的初始化与扫描,完整成本应为 O(n+k),而不是无条件 O(n)。 - 原始内容:2*n次,结果总的性能是O(n)的。 因为待排序的数组中的元素必须是从有限的k个元素中得到,计数排序的使用受到了限制。我们现在讨论桶排序,这个排序方法克服了这个限制,每个元素都能够映射到一个桶中。