面试官问：一万个 0 到 100 的成绩怎么排最快？答快速排序，他追问分数范围已知，还能不能再快。这就是引导题，答案是桶排序——范围已知、数据密集时，连元素两两比较都能省掉。

三步走完整个流程

桶排序就三步。第一步分桶：按取值范围开若干桶，成绩按每 10 分一桶，85 分进第 8 个桶，一万个成绩平均下来每桶千把个；第二步桶内排序：每桶数据量小，插入排序这种简单方法反而快；第三步拼接：按桶编号从小到大依次取出，结果天然有序。

for x in scores: bucket[x/10].append(x) for b in bucket: insertion_sort(b) 按编号顺序合并所有桶

复杂度和它的脾气

数据均匀分布时，n 个元素进 k 个桶，平均时间 O(n+k)，接近线性。脾气也在这：数据往一个桶里扎堆，桶内退化成插入排序，最坏 O(n^2)，这个平方是桶内比较贡献的，跟分桶本身没关系。桶开太少没效果，开太多浪费空间，空间开销是 O(n+k)。一般按数据量同数量级或按极差均分来定桶数，这个取舍面试里说清楚比背公式加分。

和亲戚们的关系

计数排序相当于每个值单独一个桶，只记次数不排桶内；基数排序是按位分桶、多轮分发。三个都是空间换时间，都不依赖元素两两比较。稳定性看桶内用的排序，桶内稳定则整体稳定。

回到实际写代码，业务里语言自带的 sort 够用，桶排序更多出现在笔试和嵌入式采集里。碰到范围已知的海量数据，先想想能不能分桶，这个思路比背模板值钱。