【注】参考自教材「算法导论」。

1. 简介

计数排序属于非比较排序算法类，故其时间复杂度不受比较排序算法时间复杂度下界的限制，可以达到 O(n+k)O(n+k) 。其中，kk 为待排序序列的排序关键字的最大范围。
计数排序是稳定的、非原址的。

2. 思想

计数排序假设 nn 个输入元素中的每一个的排序关键字都是在 0 到 kk 区间（左闭右开）内的一个整数。对每一个输入元素 xx ，确定小于 xx 的元素个数，然后利用元素个数直接将序列按顺序排好放到输出序列中。

3. 实现

3.1 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
CountingSort(A, Key, k) {
    // 定义新数组 B & C
    define B[0..A.length] 
    define C[0..k]
    // 初始化数组 C
    for i = 0 to k 
        C[i] = 0
    // 统计每个关键字的元素数量
    for j = 1 to A.length
        C[Key[j]] = C[Key[j]] + 1
    // 统计关键字小于等于 i 的元素数量
    for i = 1 to k
        C[i] = C[i] + C[i-1]
    for j = A.length downto 1
        B[C[Key[j]]] = A[j]
        C[Key[j]] = C[Key[j]] - 1
    // 将已排好序的 B 数组拷贝给 A 数组
    A = B
}

3.2 模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

#ifndef _COUNTING_
#define _COUNTING_
#define ll int
#define MAXN 100005

// 计数排序
template < typename T >
struct Counting {
    
    ll C[MAXN];
    T B[MAXN];
    Counting() {}
    // 计数排序（关键字的值属于区间 [0,n)）
    //（关键字数组不会改变，待排序数组变为有序）
    void countingSort(T *bA, T *eA, ll *bK, ll *eK, ll n) {
        ll len_A = eA - bA;
        ll len_K = eK - bK;
        T *A = bA;
        ll *K = bK;
        // 判断关键字数组大小与元素数组大小是否吻合
        assert(len_A == len_K);
        // 初始化计数数组
        for(ll i = 0; i < n; ++i) {
            C[i] = 0;
        }
        // 统计关键字次数
        for(ll i = 0; i < len_K; ++i) {
            C[K[i]]++;
        }
        // 计算 <= i 的关键字次数
        for(ll i = 1; i < n; ++i) {
            C[i] = C[i] + C[i-1];
        }
        // 初始化排序数组
        for(ll i = len_A-1; ~i; --i) {
            B[C[K[i]]-1] = A[i];
            C[K[i]]--;
        }
        // 将排好序的数组赋值给原数组
        memcpy(A, B, sizeof(T)*len_A);
    }
};
#endif