排序算法系列 10：桶排序——先分堆再各自整理
桶排序的思想特别朴素：一堆东西混在一起不好排，那就先按范围分成几堆，每堆数量少了就好办了。
你可以把它想象成快递分拣——全国快递不可能一件件从头排到尾，而是先按省份分堆，每个省内部再按城市排，最后顺序一拼就好了。
核心思想
- 把数据按值域范围分到若干个"桶"里
- 每个桶内部用其他排序算法（比如插入排序）排好
- 按桶的顺序把结果拼起来
桶排序的性能好不好，取决于一个关键因素：数据是不是均匀分布到各个桶里。
如果数据很均匀，每个桶里就几个元素，桶内排序很快，总体接近线性。如果数据全挤在一个桶里，那就退化成桶内排序本身的复杂度了。
走一遍过程
用 [0.78, 0.17, 0.39, 0.26, 0.72, 0.94] 举例，数据范围 0~1，分 5 个桶。
分桶：
text
桶 0 [0.0, 0.2)：0.17
桶 1 [0.2, 0.4)：0.39, 0.26
桶 2 [0.4, 0.6)：（空）
桶 3 [0.6, 0.8)：0.78, 0.72
桶 4 [0.8, 1.0]：0.94
桶内排序：
text
桶 0：0.17
桶 1：0.26, 0.39
桶 3：0.72, 0.78
桶 4：0.94
合并：
text
0.17, 0.26, 0.39, 0.72, 0.78, 0.94
搞定。每个桶里最多两个元素，排起来几乎不花时间。
代码实现
javascript
function bucketSort(arr, bucketCount = 5) {
if (arr.length <= 1) return [...arr];
const min = Math.min(...arr);
const max = Math.max(...arr);
if (min === max) return [...arr];
const buckets = Array.from({ length: bucketCount }, () => []);
const range = max - min;
// 分桶
for (const num of arr) {
const index = Math.min(
bucketCount - 1,
Math.floor(((num - min) / range) * bucketCount)
);
buckets[index].push(num);
}
// 桶内排序 + 合并
const result = [];
for (const bucket of buckets) {
insertionSort(bucket);
result.push(...bucket);
}
return result;
}
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
const current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}
console.log(bucketSort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94]));
// [0.17, 0.26, 0.39, 0.72, 0.78, 0.94]
桶内用插入排序是因为每个桶里元素通常很少，插入排序在这种小数据量下效率最高。
和计数排序什么关系？
计数排序其实可以看成桶排序的一种特殊情况：
| 计数排序 | 桶排序 | |
|---|---|---|
| 桶的粒度 | 每个值一个桶 | 一个范围一个桶 |
| 适用数据 | 整数，范围小 | 任意数值，分布均匀 |
| 桶内排序 | 不需要（每桶只有相同值） | 需要 |
桶排序更通用，可以处理小数、浮点数、甚至字符串——只要你能设计出合理的分桶规则。
桶的数量怎么定？
没有标准答案，通常有几种策略：
- 取数据量的平方根：
Math.sqrt(n) - 固定数量（比如 5、10、20）
- 根据业务含义分（比如分数段：0-59, 60-69, 70-79, 80-89, 90-100）
核心原则：让数据尽量均匀分布到各个桶里。桶太少，单桶数据太多；桶太多，空桶浪费空间。
复杂度
设 n 是数据量，k 是桶数量：
- 理想情况（数据均匀分布）：
O(n + k)，接近线性 - 最坏情况（数据全在一个桶里）：取决于桶内排序，用插入排序就是
O(n²)
空间复杂度 O(n + k)。
稳定性取决于桶内排序——用插入排序的话是稳定的。
适用场景
- 数据在某个范围内均匀分布
- 可以自然划分区间（分数段、价格区间、时间段）
- 数据量大但值域有限
不适合数据分布极度不均匀的场景——比如 99% 的数据集中在一个很小的范围内，那分桶基本没用。
下一篇来看基数排序——非比较排序的最后一个成员，它的思路更巧妙：按位排序。
系列导航