桶排序 Bucket Sort

经典排序 · 非比较 · 分桶 + 桶内排序 + 合并

什么是桶排序

桶排序不直接两两比较全体，而是按值域把元素撒进若干「桶」：每个桶负责一段连续的取值范围。撒完后每个桶内部各自排序，最后按桶的先后顺序把各桶依次倒出拼接，整体就有序了。它和计数排序、基数排序同属非比较的线性排序。

桶排序怎么做

分三步，对应下面播放器里高亮的三段代码：

①分配（distribute）：遍历数组，按值算出该进哪个桶（这里取 ⌊v / 10⌋，每桶宽 10），把元素追加进去。②桶内排序（sortBucket）：对每个桶各自排序——桶内元素少，用插入排序很快；空桶直接跳过。③合并（concat）：按桶 0、1、2…的顺序，把每个桶里已排好的元素依次写回原数组。因为「桶之间已经按值域有序、桶内也各自有序」，拼起来自然全局有序。

下面固定 8 个数 [29, 25, 3, 49, 9, 37, 21, 43]，分成 5 个桶（0–9 / 10–19 / 20–29 / 30–39 / 40–49）。点「下一步」看它怎么把数撒进桶（留意 10–19 是个空桶）、桶 20–29 内部 [29, 25, 21] 怎么排成 [21, 25, 29]，再合并回主轨。

复杂度与适用

设 n 个元素分到 k 个桶。若数据大致均匀分布，每桶约 n/k 个，桶内排序总代价摊薄到接近线性，平均 O(n + k)；额外空间 O(n + k)，且是稳定排序。但分布若极不均匀——所有元素挤进同一个桶——就退化成「单个桶内排序」，最坏 O(n²)（或 O(n log n)，取决于桶内用什么排序）。所以桶排序的前提是对数据分布有把握。

桶排序在哪里用

最典型的是把 [0, 1) 上均匀分布的浮点数排序（按小数大小分桶）、或对成绩、年龄这类取值范围已知且分布较均匀的数据排序。它也是「先粗分、再细排」这一分治思想的直观范例——线性排序三件套（计数 ✓ 基数 ✓ 桶 ✓）至此补齐。