计数排序 vs. 桶排序 vs. 基数排序

1. 概述

在常见的排序算法中，我们通常将其分为两大类：基于比较的排序算法，和基于元素计数的排序算法。

本文将聚焦于后者，具体对比三种非比较排序算法：计数排序（Counting Sort）、桶排序（Bucket Sort）和基数排序（Radix Sort）。这类算法的时间复杂度通常为 O(n + k)，其中 n 是数组长度，k 是数组中最大值的大小。

它们适用于特定场景，尤其在处理整型数组或有限范围数据时表现优异。

---

2. 计数排序（Counting Sort）

计数排序的核心思想是：统计每个元素出现的次数，然后按顺序将元素写回原数组。它适用于已知范围的整数数组排序。

✅ 基本流程

1. 找出数组最大值 k
2. 创建大小为 k 的计数数组 C，初始化为 0
3. 遍历原数组 A，统计每个元素出现的次数，存入 C
4. 根据 C 中的计数信息，按顺序写回 A

📌 示例图解

✅ 示例代码（伪代码）

algorithm CountingSort(A, n):
    // INPUT
    //    A = an unsorted array of size n
    // OUTPUT
    //    Returns the sorted array A

    // find the maximum value k in A
    k <- A[1]

    for i <- 2 to n by 1:
        if A[i] > k:
            k <- A[i]

    C <- initialize the counting array containing k zeros

    // Fill the counting array
    for i <- 1 to n by 1:
        C[A[i]] <- C[A[i]] + 1

    // overwrite A using the values in C
    place <- 1

    for i <- 1 to k:
        if C[i] > 0:
            for j <- 1 to C[i]:
                A[place] <- i
                place <- place + 1

    return A

⚠️ 优缺点分析

• 优点

  • 时间复杂度低，为 O(n + k)
  • 实现简单、效率高

• 缺点

  • 只适用于整数数组
  • 当 k 很大时，空间消耗巨大（例如 [4, 5, 1, 7, 1000000] 需要长度为 1000000 的计数数组）
  • 不适用于数据范围广或非整型数据

---

3. 桶排序（Bucket Sort）

桶排序将数组元素分布到多个桶中，每个桶内部排序后再合并输出。它特别适合数据分布均匀的场景。

✅ 基本流程

1. 创建多个桶（bucket），每个桶负责一个数据范围
2. 遍历原数组，将元素放入对应的桶中
3. 对每个桶进行排序（通常使用插入排序）
4. 合并所有桶的元素，输出最终排序结果

📌 示例图解

✅ 示例代码（伪代码）

algorithm BucketSort(A, n, k, b):
    // INPUT
    //    A = Unsorted array
    //    n = size of the array A
    //    k = maximum value in A
    //    b = number of buckets
    // OUTPUT
    //    Returns the sorted array A

    B <- allocate bucket array B and set each element to empty

    // Insert elements of A into buckets
    for i <- 1 to n:
        InsertList(A[i] / b, A[i])

    // Sort the linked lists
    for i <- 1 to b:
        SortList(B[i])

    // Overwrite A using the linked lists from B
    Loc <- 1
    for i <- 1 to b:
        listPlace <- B[i]
        while listPlace != empty:
            A[Loc] <- Value(B[listPlace])
            listPlace <- Next(B[listPlace])
            Loc <- Loc + 1

    return A

⚠️ 优缺点分析

• 优点

  • 对均匀分布的数据效率高
  • 可并行化处理每个桶

• 缺点

  • 数据分布不均时性能下降严重（最坏情况退化为插入排序）
  • 需要额外空间存储桶和链表
  • 插入排序效率较低（无法使用更高效的排序算法）

---

4. 基数排序（Radix Sort）

基数排序是一种多关键字排序算法，它从低位到高位（或高位到低位）依次对每一位进行排序，通常使用计数排序作为子过程。

✅ 基本流程（以十进制为例）

1. 从最低位（个位）开始，对数组按当前位进行一次计数排序
2. 移动到更高位，重复上述过程
3. 直到最高位排序完成

📌 示例图解

✅ 示例代码（伪代码）

algorithm RadixSort(A, d):
    // INPUT
    //    A = unsorted array of integers with at most d digits each
    // OUTPUT
    //    Returns the sorted array A

    for i <- 1 to d:
        A <- CountingSort(A, d)

    return A

⚠️ 优缺点分析

• 优点

  • 稳定排序，适合多关键字排序
  • 时间复杂度为 O(n * d)，当 d 固定为常数时可视为线性时间排序
  • 可扩展用于处理二进制数字、十六进制等格式

• 缺点

  • 只适用于整数或可拆分为多个关键字的数据
  • 实现复杂度略高，需多次调用计数排序

---

5. 总结与对比

排序算法	时间复杂度	空间复杂度	是否稳定	适用场景	踩坑提示
计数排序	O(n + k)	O(k)	✅ 是	整数、范围小	k 大时内存爆炸
桶排序	O(n^2) 最坏	O(n + b)	✅ 是	数据均匀分布	分布不均性能暴跌
基数排序	O(n * d)	O(n + k)	✅ 是	整数、多关键字	实现较复杂

✅ 使用建议

• 若数据范围小且为整数，优先使用 计数排序
• 若数据分布较均匀，可尝试 桶排序
• 若需处理多关键字数据（如身份证号、手机号），使用 基数排序

💡 小贴士

• 基数排序常用于大数据处理，尤其适合处理二进制数据（如 IP 地址、哈希值）
• 桶排序适合分布式系统中并行处理
• 实际开发中，结合具体数据特征选择排序算法，才能获得最佳性能

---