现实里有一类棘手问题：数据量极大（百万、千万级），值域却只有几十、几百——比如年龄、考分、星级。在这类场景下，传统的 n log n 比较排序为什么撑不住？

左侧进入原始数据，右侧输出有序序列。映射函数 f 是核心，把大范围 v 压缩为小范围索引 k。

上一页我们把数据映射到了0-100的小范围。映射之后怎么排最自然？按值分桶，桶内排好，再按桶顺序串起来——这就是桶排序的核心三步。

桶排序分五步：先把数据按值域散入桶，再让每桶内部有序，最后按桶序串回原数组。

沿箭头方向读：从原数组出发，经分桶、桶内排序、最终拼接成有序数组。

看一段 Python 实现桶排序的核心五步：建桶、入桶、桶内排序、拼接输出。

五步对应核心思路：找范围→建桶→按比例映射→桶内小排序→顺序拼接。每桶内元素少，整体复杂度近 O(n)。

代码写完了，但它到底跑得多快？占多少内存？什么场景才值得用？这一页我们把时间和空间复杂度算清楚，并说清它的适用边界。

桶排序把元素分到若干桶再分别排序。但桶内还是要排。如果值域足够小，让每个取值独占一个桶呢？那连比较都不用——数一数就够了。

计数排序四步走：建表→计数→定位→落位，把「值→次数→位置→有序」的转换拆开看。

看图路径：左侧一列是公共准备，到频次数组C之后分出两条生成有序输出的路线。

稳定版计数排序的 Python 实现，三步走：计数→前缀和→反向填位。

高亮行串起稳定版计数排序的三大动作：计数累加→前缀和转位置→反向填位。稳定性关键在 reversed(arr)：相同值的元素保持原相对顺序。

从计数排序的代码看，两层循环一眼就能数出来。但「快」的背后其实有代价——你为速度放弃了空间，还要牺牲一个叫「稳定性」的东西。这个牺牲值不值？这一页讲清楚。

两者都'按值分桶'，但桶的含义截然不同——一个装区间，一个装具体值，这是最容易混淆的地方。

• ✓范围紧凑且n较大→优先计数排序
• ✓数据近似均匀分布→桶排序更快
• ✓计数排序可视为桶尺寸为1的特例
• ✓分布严重倾斜时桶排序退化为O(n²)
• ✓两者均以O(n+k)空间换取线性时间

先自己想想，再对照参考答案——重点关注思路，不必追求完整。