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

1. 简介

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

2. 思想

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

3. 实现

3.1 伪代码

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 模板

#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