基数排序

前言

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

算法思想

基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

算法步骤

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零（将所有数的长度调整为一样）
从最低位（个位）开始，依次进行一次排序
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

基数排序的方式可以采用 LSD（Least significant digital）或 MSD（Most significant digital），LSD 的排序方式由键值的最右边开始，而 MSD 则相反，由键值的最左边开始。
不妨通过一个具体的实例来展示一下基数排序是如何进行的。设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。
我们知道，任何一个阿拉伯数，它的各个位数上的基数都是以 0~9 来表示的，所以我们不妨把 0~9 视为 10 个桶。
我们先根据序列的个位数的数字来进行分类，将其分到指定的桶中。例如：R[0] = 50，个位数上是 0，将这个数存入编号为 0 的桶中。
分类后，我们在从各个桶中，将这些数按照从编号 0 到编号 9 的顺序依次将所有数取出来。这时，得到的序列就是个位数上呈递增趋势的序列。

动态图象理解

图源：cuijiahua

源代码

#include <iostream>
#include <vector>
 
using namespace std;
 
// 求出数组中最大数的位数的函数
int MaxBit(vector<int> input){
    // 数组最大值
    int max_data = input[0];
    for (int i = 1; i < input.size(); i++){
        if (input[i] > max_data){
            max_data = input[i];
        }
    }
 
    // 数组最大值的位数
    int bits_num = 0;
    while (max_data){
        bits_num++;
        max_data /= 10;
    }
 
    return bits_num;
}
 
// 取数xxx上的第d位数字
int digit(int num, int d){
    int pow = 1;
    while (--d > 0){
        pow *= 10;
    }
    return num / pow % 10;
}
 
// 基数排序
vector<int> RadixSort(vector<int> input, int n){
    // 临时数组，用来存放排序过程中的数据
    vector<int> bucket(n);                    
    // 位记数器，从第0个元素到第9个元素依次用来记录当前比较位是0的有多少个...是9的有多少个数
    vector<int> count(10);                
    // 从低位往高位循环
    for (int d = 1; d <= MaxBit(input); d++){
        // 计数器清0
        for (int i = 0; i < 10; i++){
            count[i] = 0;
        }
 
        // 统计各个桶中的个数
        for (int i = 0; i < n; i++){
            count[digit(input[i],d)]++;
        }

        for (int i = 1; i < 10; i++){
            count[i] += count[i - 1];
        }
 
        for (int i = n - 1; i >= 0; i--){
            int k = digit(input[i], d);
            bucket[count[k] - 1] = input[i];
            count[k]--;
        }
 
        // 临时数组复制到 input 中
        for (int i = 0; i < n; i++){
            input[i] = bucket[i];
        }
    }
 
    return input;
}
 
int main(){
    int arr[] = { 50, 123, 543, 187, 49, 30, 0, 2, 11, 100 };
    vector<int> result(arr, arr + sizeof(arr) / sizeof(arr[0]));
    result = RadixSort(result, result.size());

    for (int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
}

时空间复杂度

时间复杂度

该算法所花的时间基本是在把元素分配到桶里和把元素从桶里串起来；把元素分配到桶里：循环 length 次；
把元素从桶里串起来：这个计算有点麻烦，看似两个循环，其实第二循环是根据桶里面的元素而定的，可以表示为：k×buckerCount；其中 k 表示某个桶中的元素个数，buckerCount 则表示存放元素的桶个数；
有几种特殊情况：
第一、所有的元素都存放在一个桶内：k = length，buckerCount = 1；
第二、所有的元素平均分配到每个桶中：k = length/ bukerCount，buckerCount = 10；（这里已经固定了10个桶）
所以平均情况下收集部分所花的时间为：length （也就是元素长度 n）

综上所述：
时间复杂度为：$posCount (length + length) $；其中 $posCount$ 为数组中最大元素的最高位数；简化下得：$O( kn )$ ；其中 $k$ 为常数，$n$ 为元素个数；