困难C++4 分钟1,469 字

桶排序与基数排序

冒泡、选择、插入、归并、快速排序都是基于比较​的排序,时间复杂度下界是 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

代码实现

cpp
#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)
  • 数据分布较均匀
  • 需要稳定排序时,桶内用稳定排序即可保证

计数排序(对比参照)

桶排序的极端特例:​每个值一个桶​​,适合值域很小的整数:

cpp
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  ← 有序

关键性质:​每一轮排序必须是稳定的​​,否则前面已经排好的低位顺序会被打乱。

代码实现

cpp
// 对某一位(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)。

同类知识点