桶排序

https://zhuanlan.zhihu.com/p/126116878

排序算法系列目录说明

冒泡排序（Bubble Sort）
插入排序（Insertion Sort）
希尔排序（Shell Sort）
选择排序（Selection Sort）
快速排序（Quick Sort）
归并排序（Merge Sort）
堆排序（Heap Sort）
计数排序（Counting Sort）
桶排序（Bucket Sort）
基数排序（Radix Sort）

基数排序（RadixSort）

基数排序（Radix sort）是一种非比较型整数排序算法。

基本思想

原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序

实现逻辑
① 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
② 从最低位开始，依次进行一次排序。
③ 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
动图演示

基数排序动态演示
分步图示说明：设有数组 array = {53, 3, 542, 748, 14, 214, 154, 63, 616}，对其进行基数排序：

在上图中，首先将所有待比较数字统一为统一位数长度，接着从最低位开始，依次进行排序。

按照个位数进行排序。
按照十位数进行排序。
按照百位数进行排序。
排序后，数列就变成了一个有序序列。

复杂度分析

时间复杂度：$O(k*N)$

空间复杂度： $O(k + N)$

稳定性：稳定

设待排序的数组R[1..n]，数组中最大的数是d位数，基数为r（如基数为10，即10进制，最大有10种可能，即最多需要10个桶来映射数组元素）。

处理一位数，需要将数组元素映射到r个桶中，映射完成后还需要收集，相当于遍历数组一遍，最多元素数为n，则时间复杂度为$O(n+r)$。所以，总的时间复杂度为$O(d*(n+r))$。

基数排序过程中，用到一个计数器数组，长度为r，还用到一个rn的二位数组来做为桶，所以空间复杂度为$O(rn)$。

基数排序基于分别排序，分别收集，所以是稳定的。

代码实现

int maxbit(int data[], int n) //辅助函数，求数据的最大位数
{
    int maxData = data[0];      ///< 最大数
    /// 先求出最大数，再求其位数，这样有原先依次每个数判断其位数，稍微优化点。
    for (int i = 1; i < n; ++i)
    {
        if (maxData < data[i])
            maxData = data[i];
    }
    int d = 1;
    int p = 10;
    while (maxData >= p)
    {
        //p *= 10; // Maybe overflow
        maxData /= 10;
        ++d;
    }
    return d;
/*    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;*/
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}