基数排序的主要思想是选择多位基数依次进行排序，利用每次排序后还是相对有序，也就是稳定排序性质，依次比较完所有基数后，完成整个数组排序。其中，每次比较基数比如对整数进行排序时可以采用计数排序，因为整数位数有限并且每个位上的数值范围是0-9，所以最适合采用优化后计数排序对每个基数进行排序。

时间复杂度为 O(n + m)，空间复杂度为 O(n + m)，其中n为数组个数，m为数组最大值位数。

基数排序跟数组规模有关，假如规模很大的话，不一定比快速排序更优，故需要就具体数据模块进行分析。

一、代码实现分析

下面举一个具体例子。

假如要对数组arr={ 2,0,1,6,8,10,5,99,87,333,2,0,1 }排序，则最大值为333，这个最大值有三位数，故只需要进行三次大循环对所有原始数组arr进行个位数，十位数，百位数分别进行计数排序即可完成整个排序。

为什么分别对个位、十位、百位数进行排序后，最后整个数组arr是有序的呢？这个就是刚刚说的计数排序是稳定排序算法，经过一轮个位数排序后，整个数组消除了个位数的逆序对；此时只剩下十位和百位数的逆序对，故只需要分别对十位数和百位数进行计数排序即可消除整个数组arr的逆序对完成排序。

1.1具体实现步骤

a1 先找出原始数组arr最大值，求出最大值有多少个位数digitLen

int max = *std::max_element(nums.begin(), nums.end()); // 找出数组最大值
int digitLen{ 0 };
int div{ 1 };
while (max)
{
    ++digitLen; // 计算最大值位数
    max /= 10;
}

a2 对原始数组每个位(个位、十位、百位、千位、...)分别进行计数排序，即digitLen次最外层循环

for (int i = 0; i < digitLen; i++) // 从最低位开始依次遍历所有基数
{
    // 进行计数排序
}

a3 每个位计数排序完成后，将结果复制到原始数组arr中，并且清除原始计数countArr数组后，再进行下一个位的计数排序，直到完成所有位的排序，则完成整个数组排序

for (int i = 0; i < digitLen; i++) // 从最低位开始依次遍历所有基数
{
    vector<int> countArr(10, 0);
    vector<int> result(nums.size());
    for (auto& it : nums) // 统计每个基数个数
        countArr[it / div % 10]++;
    for (int i = 1; i < countArr.size(); ++i) // 变化计数数组
        countArr[i] += countArr[i - 1];
    for (int i = nums.size() - 1; i >= 0; --i) // 逆序遍历原始数组nums，放入结果数组进行排序
    {
        result[countArr[nums[i] / div % 10] - 1] = nums[i];
        countArr[nums[i] / div % 10]--;
    }
    nums = result; // 赋值到原始数组nums后，进行下一个位遍历        
    div *= 10;
}

1.2完整代码

Sorts.h

#pragma once

#include <iostream>
#include <vector>

using namespace std;

struct Sorts {    
    void radix(vector<int>& nums);    
    void print(vector<int>& nums);
};

Sorts.cpp

#include "Sorts.h"
#include <algorithm>

void Sorts::radix(vector<int>& nums)
{
    int max = *std::max_element(nums.begin(), nums.end()); // 找出数组最大值
    int digitLen{ 0 };
    int div{ 1 };
    while (max)
    {
        ++digitLen; // 计算最大值位数
        max /= 10;
    }
    for (int i = 0; i < digitLen; i++) // 从最低位开始依次遍历所有基数
    {
        vector<int> countArr(10, 0);
        vector<int> result(nums.size());
        for (auto& it : nums) // 统计每个基数个数
            countArr[it / div % 10]++;        
        for (int i = 1; i < countArr.size(); ++i) // 变化计数数组
            countArr[i] += countArr[i - 1];
        for (int i = nums.size() - 1; i >= 0; --i) // 逆序遍历原始数组nums，放入结果数组进行排序
        {            
            result[countArr[ nums[i] / div % 10] - 1 ] = nums[i];
            countArr[nums[i] / div % 10]--;
        }
        nums = result; // 赋值到原始数组nums后，进行下一个位遍历        
        div *= 10;
    }
}

void Sorts::print(vector<int>& nums)
{
    for (const auto& it : nums)
        cout << it << ",";
    cout << endl;
}

main.cpp

 #include <vector>
#include "Sorts.h"

using namespace std;

int main()
{
    vector<int> nums = { 2,0,1,6,8,10,5,99,87,333,2,0,1 };
    Sorts sorts;
    sorts.print(nums);
    sorts.radix(nums);
    sorts.print(nums);
   
	return 1;
}

1.3输出结果

1.4总结

从上面代码可以看出，基数排序其本质就是对每个基数依次进行排序，并且排序前后的排序算法是稳定的，除了每次基数排序采用计数排序算法外，还可以采用其它稳定排序算法，比如插入排序，堆排序等，但常用的还是基数排序中嵌入计数排序。