桶排序与基数排序
冒泡、选择、插入、归并、快速排序都是基于比较的排序,时间复杂度下界是 O(n log n)。但桶排序和基数排序走的是另一条路——不比较元素大小,直接按下标归位,在特定条件下能做到线性时间。二者在 NOI 大纲提高级(CSP-S)中明确列出。
桶排序
核心思想
把数据按值域划成若干桶,每个桶负责一个数值区间;先按桶的区间把元素丢进对应的桶,再对每个桶内部排序,最后按桶的顺序拼接。
数据: [ 78, 17, 39, 26, 72, 94, 21, 12, 23, 68 ]
分桶: 桶0(0-24) 桶1(25-49) 桶2(50-74) 桶3(75-99)
17,12,21 39,26,23 72,68 78,94
桶内排序后拼接: 12 17 21 23 26 39 68 72 78 94
代码实现
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
void bucketSort(vector<int>& a, int bucketCount) {
if (a.empty()) return;
int mn = *min_element(a.begin(), a.end());
int mx = *max_element(a.begin(), a.end());
// 每个桶的宽度
int width = (mx - mn) / bucketCount + 1;
vector<vector<int>> buckets(bucketCount);
// 分配到各个桶
for (int x : a) {
int idx = (x - mn) / width;
buckets[idx].push_back(x);
}
// 桶内排序并回填
int k = 0;
for (auto& b : buckets) {
sort(b.begin(), b.end()); // 桶内可用任意排序
for (int x : b) a[k++] = x;
}
}
时间复杂度
设 n 个元素、k 个桶、元素均匀分布:
- 分配到桶:O(n)
- 桶内排序:平均每个桶 n/k 个元素,排序 O((n/k) log(n/k)),k 个桶共 O(n log(n/k))
- 当 k ≈ n 时,复杂度接近 O(n)
但这是平均情况。如果所有元素都落进同一个桶,就退化成 O(n log n) 甚至 O(n²)——桶排序依赖数据均匀分布。
适用场景
- 数据范围不大(如分数 0~100)
- 数据分布较均匀
- 需要稳定排序时,桶内用稳定排序即可保证
计数排序(对比参照)
桶排序的极端特例:每个值一个桶,适合值域很小的整数:
void countingSort(vector<int>& a, int maxVal) {
vector<int> cnt(maxVal + 1, 0);
for (int x : a) cnt[x]++; // 统计每个值出现次数
int k = 0;
for (int v = 0; v <= maxVal; v++)
while (cnt[v]--) a[k++] = v; // 按值顺序回填
}
时间复杂度 O(n + V),其中 V 是值域。空间也是 O(V)。当 V 远大于 n 时非常浪费。
基数排序
核心思想
当数字很大(比如 10^9)时,没法直接当成下标。基数排序的做法是:按每一位分别做一轮计数排序,从最低位到最高位依次处理(LSD,Least Significant Digit)。
原始: 329 457 657 839 436 720 355
按个位: 720 355 436 457 657 329 839
按十位: 720 329 436 839 355 457 657
按百位: 329 355 436 457 657 720 839 ← 有序
关键性质:每一轮排序必须是稳定的,否则前面已经排好的低位顺序会被打乱。
代码实现
// 对某一位(exp = 1, 10, 100...)做稳定计数排序
void countingSortByDigit(int a[], int n, int exp) {
int output[n];
int cnt[10] = {0};
// 统计该位每个数字出现次数
for (int i = 0; i < n; i++)
cnt[(a[i] / exp) % 10]++;
// 前缀和:得到每个数字在输出中的结束位置
for (int i = 1; i < 10; i++)
cnt[i] += cnt[i - 1];
// 从后往前放,保证稳定性
for (int i = n - 1; i >= 0; i--) {
int d = (a[i] / exp) % 10;
output[--cnt[d]] = a[i];
}
for (int i = 0; i < n; i++)
a[i] = output[i];
}
void radixSort(int a[], int n) {
int mx = *max_element(a, a + n);
// 从个位开始,逐位排序
for (int exp = 1; mx / exp > 0; exp *= 10)
countingSortByDigit(a, n, exp);
}
时间复杂度
设最大数有 d 位,每轮计数排序 O(n + 10),共 d 轮:
O(d · (n + 10)) ≈ O(d · n)
当 d = 10(int 范围)时,大约 10n 次操作,是线性的。
为什么要从后往前放
这是保证稳定性的关键。看这个例子,按个位排序时:
数组: [12, 32],个位都是 2
正序放:先放 12 到位置 0,再放 32 到位置 1 → [12, 32] 顺序保持
其实正序也能保持这一轮的顺序,但从后往前更稳妥——因为前缀和给出的是"每个桶的末尾位置",从后往前填能保证同一桶内原有相对顺序不变。这样上一轮排好低位的结果才不会被打乱。
两种排序的对比
| 特性 | 桶排序 | 基数排序 |
|---|---|---|
| 思想 | 按值域分桶 | 按位分轮 |
| 时间 | 平均 O(n + k) | O(d·n) |
| 空间 | O(n + k) | O(n + 基数) |
| 稳定性 | 桶内稳定则整体稳定 | 必须稳定 |
| 限制 | 需均匀分布 | 只适用于整数(或可拆位的类型) |
| 适用 | 数据范围小、分布均匀 | 整数,位数不多 |
什么时候用
- 分数、年龄、成绩这类值域有限的整数 → 计数排序或桶排序
- 10^9 以内的整数、n 达到 10^7 → 基数排序(比
sort快数倍) - 需要线性时间且 n 很大 → 优先考虑基数排序
- 数据是浮点数或字符串 → 一般仍用
sort
常见错误
- 基数排序不稳定:从前往后填
output时若下标算错,会打乱低位顺序,结果错误。 - exp 溢出:
exp *= 10在mx接近INT_MAX时会溢出,用long long或改成exp > mx / 10判断。 - 桶排序桶数不合理:桶太少退化成普通排序,桶太多浪费空间。
- 负数没处理:基数排序取
(a[i]/exp)%10时负数会得到负下标,需先加偏移量转成非负。
小结
桶排序按值域分桶,基数排序按位分轮,两者的共同点是用空间换时间、不做比较。掌握它们的前提是理解"稳定排序"——基数排序的正确性完全依赖每轮排序的稳定性。在整数范围可控的题目里,它们能把 O(n log n) 压到 O(n)。