目录
简介：
图解：
C++代码实现：
总结：
简介： 基数排序的发明可以追溯到1887年赫尔曼何乐礼在打孔卡片制表机上的贡献。
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
按低位优先级排序或按高位优先级排序取决于自己兴趣，下面的代码按低位优先。
算法简述： 1.取得数组中最大的数的位数max_bit
2.分散：将数组的所有数按照第i位（初始时，i=1，以后i++）的大小，填充到队列数组里（大小为10）
3.收集：将不为空的队列中首尾相连的填充到数组中，i++。
4.直到i>max_bit,否则，循环执行2、3
图解： 
文章图片
C++代码实现：
#include
#include
#include
#include
#include
using namespace std;
#define range 100000// 控制数组的大小
int myrandom(int a[])//随机填充数组
{
int max=0;
srand((unsigned)time(NULL));
for(int i=0;
imax)
max=a[i];
}
return max;
}
int Max_bit(int a)//求最大数的位数
{
return a<10?1:1+Max_bit(a/10);
}
void RadixSort(int a[],int max_bit)//基数排序
{
queue temp[10];
int mod=10;
int div=1;
int j=0;
int num=0;
for(int i=0;
i 差点忘了给测试结果了，(#^.^#)
文章图片
文章图片
总结： 它是稳定的，是非比较类排序算法。
时间复杂度分析：
如果最大数的位数为k，每一次分配与收集都为o（2*range），（range为测试数据的大小）
所以，总的时间复杂度为o（k*2*range）
当k远小于range时，可以看做是线性的。
小伙伴们，如果还看不懂，在评论区留言。
（上学期我老师的一句话：一个人自己懂了，不见的是真懂，只有给别人讲明白了，才算真的懂。ps：我老师是菊厂毕业的O(∩_∩)O哈哈~）
【数据结构|数据结构 基数排序（Radix Sort） 详解 附C++代码实现（）】
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 数据结构|C++技巧（用class类实现链表）
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- 算法|算法-二分查找
- 数据结构学习指导|数据结构初阶（线性表）
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- java|ObjectOrientedProgramming - 面向对象的编程（多态、抽象类、接口）- Java - 细节狂魔