跳转至

# 计数排序

前置知识：前缀和

提醒

本页面要介绍的不是 基数排序．

本页面将简要介绍计数排序．

## 定义

计数排序（英语：Counting sort）是一种线性时间的排序算法．

## 过程

计数排序的工作原理是使用一个额外的数组 𝐶 C，其中第 𝑖 i 个元素是待排序数组 𝐴 A 中值等于 𝑖 i 的元素的个数，然后根据数组 𝐶 C 来将 𝐴 A 中的元素排到正确的位置．1

它的工作过程分为三个步骤：

1. 计算每个数出现了几次；
2. 求出每个数出现次数的 前缀和；
3. 利用出现次数的前缀和，从右至左计算每个数的排名．

### 计算前缀和的原因

直接将 𝐶 C 中正数对应的元素依次放入 𝐴 A 中不能解决元素重复的情形．

我们通过为额外数组 𝐶 C 中的每一项计算前缀和，结合每一项的数值，就可以为重复元素确定一个唯一排名：

额外数组 𝐶 C 中每一项的数值即是该 key 值下重复元素的个数，而该项的前缀和即是排在最后一个的重复元素的排名．

如果按照 𝐴 A 的逆序进行排列，那么显然排序后的数组将保持 𝐴 A 的原序（相同 key 值情况下），也即得到一种稳定的排序算法．

## 性质

### 稳定性

计数排序是一种稳定的排序算法．

### 时间复杂度

计数排序的时间复杂度为 𝑂(𝑛 +𝑤)O(n+w)，其中 𝑤 w 代表待排序数据的值域大小．

## 代码实现

### 伪代码

1 𝐈 𝐧 𝐩 𝐮 𝐭. A n a r r a y 𝐴 c o n s i s t i n g o f 𝑛 p o s i t i v e i n t e g e r s n o g r e a t e r t h a n 𝑤.2 𝐎 𝐮 𝐭 𝐩 𝐮 𝐭. A r r a y 𝐴 a f t e r s o r t i n g i n n o n d e c r e a s i n g o r d e r s t a b l y.3 𝐌 𝐞 𝐭 𝐡 𝐨 𝐝. 4 𝐟 𝐨 𝐫 𝑖←0 𝐭 𝐨 𝑤 5 𝑐 𝑛 𝑡[𝑖]←0 6 𝐟 𝐨 𝐫 𝑖←1 𝐭 𝐨 𝑛 7 𝑐 𝑛 𝑡[𝐴[𝑖]]←𝑐 𝑛 𝑡[𝐴[𝑖]]+1 8 𝐟 𝐨 𝐫 𝑖←1 𝐭 𝐨 𝑤 9 𝑐 𝑛 𝑡[𝑖]←𝑐 𝑛 𝑡[𝑖]+𝑐 𝑛 𝑡[𝑖−1]1 0 𝐟 𝐨 𝐫 𝑖←𝑛 𝐝 𝐨 𝐰 𝐧 𝐭 𝐨 1 1 1 𝐵[𝑐 𝑛 𝑡[𝐴[𝑖]]]←𝐴[𝑖]1 2 𝑐 𝑛 𝑡[𝐴[𝑖]]←𝑐 𝑛 𝑡[𝐴[𝑖]]−1 1 3 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 𝐵 1 Input. An array A consisting of n positive integers no greater than w.2 Output. Array A after sorting in nondecreasing order stably.3 Method. 4 for i←0 to w 5 cnt[i]←0 6 for i←1 to n 7 cnt[A[i]]←cnt[A[i]]+1 8 for i←1 to w 9 cnt[i]←cnt[i]+cnt[i−1]10 for i←n downto 1 11 B[cnt[A[i]]]←A[i]12 cnt[A[i]]←cnt[A[i]]−1 13 return B
C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    #include <cstring>
    constexpr int MAXN = 1010;
    constexpr int MAXW = 100010;

    int cnt[MAXW], b[MAXN];

    int* counting_sort(int* a, int n, int w) {
      memset(cnt, 0, sizeof(cnt));
      for (int i = 1; i <= n; ++i) ++cnt[a[i]];
      for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
      for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
      return b;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    def counting_sort(a, n, w):
        b = [0] * n
        cnt = [0] * (w + 1)
        for i in range(1, n + 1):
            cnt[a[i]] += 1
        for i in range(1, w + 1):
            cnt[i] += cnt[i - 1]
        for i in range(n, 0, -1):
            b[cnt[a[i]] - 1] = a[i]
            cnt[a[i]] -= 1
        return b

## 参考资料与注释

1. 计数排序 - 维基百科，自由的百科全书 ↩

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：NachtgeistW, Tiphereth-A, iamtwz, c-forrest, Enter-tainer, Junyan721113, ksyx, Xeonacid, Alisahhh, gi-b716, Great-designer, Konano, mcendu, Menci, minghu6, ouuan, shawlleyw, sun2snow, TrickEye
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用