计数排序

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
}

#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