type
status
date
slug
summary
tags
category
icon
password
整理定义
中文名称：桶排序
英文名称：bucket sort
出处 | 定义 |
中国大百科全书 | 一种简单的排序算法。算法将数组元素映射到有限数量个桶里，每个桶内各自进行排序 |
百度百科 | |
维基百科 | 桶排序（或 箱排序）是一种排序算法，其工作原理是将数组的元素分配到多个桶中。 然后使用不同的排序算法或递归地应用桶排序算法对每个桶进行单独排序。 它是一种分布排序，是鸽笼排序的推广，允许每个存储桶有多个键，并且是从最高到最低有效数字风格的基数排序的表亲。 桶排序可以通过比较来实现，因此也可以被认为是比较排序算法。 计算复杂度取决于用于对每个桶进行排序的算法、要使用的桶的数量以及输入是否均匀分布。 |
复述展开
桶排序，也叫做箱排序，先将数组分到有限的桶子里面，再对每个桶子分别排序。
工作原理如下：
- 设置一个最初为空的“桶”数组。
- 分散：遍历原始数组，将每个对象放入其存储桶中。
- 对每个非空桶进行排序。
- 聚集：按顺序访问桶，并将所有元素放回到原始数组中。
图片展示：
时间复杂度：
- 最佳情况：O(n+k)
- 最坏情况：O(n^2)
- 平均情况：O(n+k)
空间复杂度：O(nk)
理解体会
桶排序适用于以下场景：
- 待排序的元素分布均匀，且元素的范围已知。
- 待排序的元素是非负整数或浮点数。
- 对于每个桶中的元素，可以使用其他排序算法进行排序。
桶排序的优点：
- 桶排序是一种稳定的排序算法，可以保持相等元素的相对顺序。
- 当待排序元素分布均匀时，桶排序的平均时间复杂度较低，接近线性时间复杂度O(n)。
- 桶排序可以通过调整桶的数量和范围来平衡时间和空间的消耗。
桶排序的缺点：
- 当待排序元素分布不均匀时，可能导致某些桶中的元素过多，需要额外的排序操作，增加时间复杂度。【最极端，只有分布到一个桶，就是n^2】
- 桶排序的空间复杂度较高，需要额外的存储空间来存放桶。
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
.png?table=block&id=0af3d43f-8aae-4c4a-b6c8-7266fccd6991&width=800&t=0aa172ae-180c-4cc6-b47f-3ccb84e7c8d8&cache=v2)
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/industry-day25
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。