知识卡片
桶排序先划范围再桶内排序
用有序的数值范围把元素放入不同桶,每桶独立排序,再按桶序拼接;只要范围关系正确,桶之间无需再逐项比较。分桶让局部问题更小,但不保证它们均匀。
原书[0,1)浮点例还需排除NaN等非法值,并对n避免零桶。成本依分布和桶内算法,全部集中一桶并不必然平方;外部大数据还需明确文件与内存预算,不能只建全量内存桶就声称已解决放不下问题。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
每个桶对应一个数 据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按照桶的顺序将所有数据合 并。 11.8.1 算法流程 考虑一个长度为 的数组,其元素是范围[0,1) 内的浮点数。桶排序的流程如图
参考来源
- 位置:《Hello 算法--Go版本》第11章《排序》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;spine 5,归一字符[1773,1883))
- 结论依据:实际分桶/桶内sort.Float64s/合并与局限,按输入和实现明确成本。
- 原始内容:每个桶对应一个数 据范围,将数据平均分配到各个桶中;然后,在每个桶内部分别执行排序;最终按照桶的顺序将所有数据合 并。 11.8.1 算法流程 考虑一个长度为 的数组,其元素是范围[0,1) 内的浮点数。桶排序的流程如图