目录
前言
基数排序算法是必须掌握的一种基础算法，在一些比较出名的竞赛acm、蓝桥杯，并且在一些公司面试题中都可能会出现，而且作为简单题我们必须要拿下，所以我们要引起重视，下面让我们来深入了解基数排序算法。
一、什么是基数排序
基数排序（Radix Sort）是一种非比较型整数排序算法，通常用于对数字进行排序。它的基本思想是将数字按位（从最低有效位到最高有效位，或从最高有效位到最低有效位）进行排序，通常使用计数排序或桶排序作为子排序算法。基数排序的时间复杂度为 O(nk)，其中 n 是待排序的数字个数，k 是数字的最大位数。
二、算法思想
基数排序的算法思想可以概括为以下步骤：
第一步、获取待排序元素的最大值，并确定其位数。
第二步、从最低位开始，依次对所有元素进行“分配“和“收集“操作。
第三步、在每一位上，根据该位上数字的值将元素分配到相应的桶中。
第四步、对每个桶中的元素进行顺序收集，得到排序后的部分结果，
重复上述步骤，直到对所有位都进行了排序。
三、算法分析
1、时间复杂度
它的时间复杂度为 O(d(n+r)),其中 d是数字的位数，n 是待排序元素的数量，r 是基数(radix)
基数排序的时间复杂度主要取决干数字的位数和待排序元素的数量。对干位数较少的情况，基数排序的效率较高，因为它不需要进行元素间的比较。然而，当数字的位数较多时，可能需要较多的“分配”和“收集”操作，导致时
间复杂度增加。
2、空间复杂度
在空间复杂度方面，基数排序需要额外的存储空间来存储桶。具体的空间复杂度取决于使用的桶的数量和存储桶的方式。
四、算法的优点
1.基数排序不需要进行元素间的比较，因此对于一些特殊情况(如排序范围有限、元素具有特定的顺序等)
它可能比比较型排序算法更有效。
2.基数排序可以很容易地用于排序具有固定宽度的数字序列，如电话号码、身份证号码等。
五、算法的缺点
1.基数排序需要额外的空间来存储桶，对于大型数据集可能会消耗较多的内存。
2.对于复杂的数据类型或非整数类型，可能需要进行额外的处理来实现基数排序。
六、优化方案
1.对于数字位数较多的情况，可以考虑使用其他排序算法，如快速排序、归并排序等
2.在实际应用中，可以根据数据的特点和排序要求，选择合适的排序算法组合，以达到更好的排序效果。
七、动态图解
八、经典例题
1.排序数组
代码题解
class Solution {
const int maxn=50005;//数组长度
const int base=10;//进制数
const int maxt=7;//位数个数
void radixSort(vector<int>&a){
int n=a.size();
int powOfbase[maxt];//存放1 10 100 ... 1000000 的数用于遍历元素每一位
powOfbase[0]=1;
for(int i=1;i<maxt;i++){
powOfbase[i]=powOfbase[i-1]*base;
}
int radixBucket[base][maxn];//二位数组用于顺序存放位数大小的值
int radixBucketTop[base];//代表每位该数字有几个
for(int i=0;i<n;i++){
a[i]+=powOfbase[maxt-1];//因为有负数所以将所有数加上范围最大值，变为正数
}
int pos=0;
while(pos<maxt){
memset(radixBucketTop,0,sizeof(radixBucketTop));
for(int i=0;i<n;i++){
int rdx=a[i]/powOfbase[pos]%base;
radixBucket[rdx][radixBucketTop[rdx]++]=a[i];//将每一位数塞进顺序塞进桶里
}
int top=0;
for(int i=0;i<base;i++){
for(int j=0;j<radixBucketTop[i];j++){
a[top++]=radixBucket[i][j];//在重新小到大将桶里的值赋给结果数组
}
}
pos++;
}
for(int i=0;i<n;i++){
a[i]-=powOfbase[maxt-1];//再将排好序的数减回最大值
}
}
public:
vector<int> sortArray(vector<int>& a) {
radixSort(a);
return a;
}
};
九、结语
学习算法是一个很艰难，漫长的过程，我们要克服一切困难，学习算法本就是由易到难，我相信通过我们坚持不懈的努力一定能理解并熟练掌握其中细节，加油，你一定能行。
关注我让我们一起学习编程，希望大家能点赞关注支持一下，让我有持续更新的动力，谢谢大家