整理定义

中文名称：桶排序

英文名称：bucket sort

复述展开

桶排序，也叫做箱排序，先将数组分到有限的桶子里面，再对每个桶子分别排序。

工作原理如下：

1. 设置一个最初为空的“桶”数组。

2. 分散：遍历原始数组，将每个对象放入其存储桶中。

3. 对每个非空桶进行排序。

4. 聚集：按顺序访问桶，并将所有元素放回到原始数组中。

图片展示：

时间复杂度：

• 最佳情况：O(n+k)

• 最坏情况：O(n^2)

• 平均情况：O(n+k)

空间复杂度：O(nk)

理解体会

桶排序适用于以下场景：

• 待排序的元素分布均匀，且元素的范围已知。

• 待排序的元素是非负整数或浮点数。

• 对于每个桶中的元素，可以使用其他排序算法进行排序。

桶排序的优点：

• 桶排序是一种稳定的排序算法，可以保持相等元素的相对顺序。

• 当待排序元素分布均匀时，桶排序的平均时间复杂度较低，接近线性时间复杂度O(n)。

• 桶排序可以通过调整桶的数量和范围来平衡时间和空间的消耗。

桶排序的缺点：

• 当待排序元素分布不均匀时，可能导致某些桶中的元素过多，需要额外的排序操作，增加时间复杂度。【最极端，只有分布到一个桶，就是n^2】

• 桶排序的空间复杂度较高，需要额外的存储空间来存放桶。