计数排序(Counting Sort)、桶排序、基数排序三个已经有不少很好的博客文章介绍，但不自己尝试描述一遍就难以熟悉，权当记录。

参考了 计数排序，基数排序和桶排序 和 三种线性排序算法 计数排序、桶排序与基数排序

计数排序

首先是主要的步骤

1. 准备线性表字典 Dict[], 其长度 m 是待排序元素的范围, 换言之每个待排序的元素都能在这个字典找到对应的位置
2. 扫描长度为 n 的待排序表 Unordered[], 把每个元素的出现次数记录在 Dict 里
3. 现在 Dict 记录着每个元素的的出现次数, 而 Dict 本身是有序的
4. 给 Dict 做累加, Dict[i] += Dict[i - 1] for i in 1 to m,
5. 累加后字典的值指定了元素排序后的位置，反向遍历待排序的A, 结合指定了元素位置的字典C 则可生成有序结果, 而反向遍历的元素会放在更后的位置, 这特性确保这是稳定排序

C 语言例子

void PrintArray(int *A, int n)
{
    for (int i = 0; i < n; ++i)
        printf("%d\t", A[i]);
    printf("\n");
}

void CountingSort(int *A, int n, int *C, int m, int *Order)
{
    printf("Original Data: \n");
    PrintArray(A, n);

    // initialize Dict
    // memset(C, 0, m * sizeof(m)); 这行居然导致代码着色失效, 不用括号包着 m 则问题解决，着实诡异。
    memset(C, 0, m * sizeof m);

    // counting element of A
    for (int i = 0; i < n; ++i)
        C[A[i]]++;

    printf("Dict: Before Accumulate\n");
    PrintArray(C, m);

    // scan C, accumulate,
    // 累加后, C 字典里的值就是 元素有序后的位置, 因为每次取得和占用位置后应该减一, 使用字典C 逆遍历A 就可以保持稳定而有序
    for (int i = 1; i < m; ++i)
        C[i] += C[i - 1];

    printf("Dict: After Accumulate\n");
    PrintArray(C, m);

    // reverse filling result, stable sort
    for (int i = n - 1; i >= 0; i--)
    {
        Order[C[A[i]]] = A[i]; // 根据字典 C 得知 A[i] 的位置（累加后的C 的值x : 前面有x个值比我小 )
        C[A[i]]--;
    }

    printf("Sorted Array:\n");
    PrintArray(Order, n);

}

int main()
{
    const int K = 10; // maximum in range, size of C
    const int N = 20; // size of A

    int A[N] = {0};
    int C[K + 1];
    int Order[N]; // result

    for (int i = 0; i < N; ++i)
        A[i] = rand() % K;

    CountingSort(A, N, C, K, Order);
    return 0;
}

桶排序 (Bucket Sort)

观看 BucketSort Visualization 后, 感觉桶排序就像散列表，然后加入了顺序的想法。

1. 过程与计数排序的部分步骤相近, 建立 Dict 字典用以储存元素的出现情况, Dict 其实可以是线性表或者散列表, 看需求; 而本来在计数排序中的计数步骤这里则类似是散列表的 Chaining
2. 对字典项的 Chaining 进行排序, 字典是有序的, Chaining 也变成有序, 扫描一次把元素读出来就完成排序了

基数排序 (Radix Sort)

假设是10 进制数 主要思想是, 把整数按数位分割, 然后就可以对一列个位数 key 进行稳定排序, from least significant to most significant digit.

一列个位数的排序就当然是使用上面的非基于比较的排序方式啦, 按十进制数来说, 每次计数排序就需要10个坑来计数

inline int extract_digit(int i, int place, const int base = 10)
{
    return i / (int)pow(base, place) % base;
}

void CountingSort(vector<int> &v, vector<int> &tmp, int place)
{
    const int BASE = 10;
    int C[BASE] = {0};

    for (int i = 0; i < v.size(); ++i)
    {
        int d = extract_digit(v[i], place);
        C[d]++;
    }

    for (int i = 1; i < BASE; ++i)
        C[i] += C[i - 1];

    for (int i = v.size() - 1; i >= 0; i--)
    {
        int d = extract_digit(v[i], place);
        tmp[C[d] - 1] = v[i];
        C[d]--;
    }

    v.swap(tmp);
}


void RadixSort(std::vector<int> &v, int element_max_width = 11)
{
    std::vector<int> tmp (v.size());

    for (int place = 0; place < element_max_width; ++place)
        CountingSort(v, tmp, place);
}