基数排序 基数排序(radix sort)属于"分配式排序"(distribution sort)，又称"桶子法"(bucket sort)或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些"桶"中，藉以达到排序的作用，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
时间复杂度： O(m（n+r）)
空间复杂度 ： O(n+r) m：最大数字的位数
n：待排序的数组的数字个数
r：队列申请空间的大小
稳定性： 稳定 基数排序相较于其他排序算法来说，基数排序的最大特点就是数字之间不用比较，在其他排序方法中，大部分都会有数字比较的过程
基数排序如图所示
文章图片
从图中我们可以看出，基数排序是通过位来排序的，比如：个位、十位、百位。。。
每一个位上都有0–9的可能性，且在每一位存储的时候都需要一个先进先出的容器，所以，我们在排序的时候需要0–9个队列，队列的长度来自于待排序的数字个数，再通过位数从个位到最大位的比较来实现的排序
在这里举个例子：
例如：1、622、82、599、743、127进行排序 【算法|数据结构（基数排序）】我们在排序之前先要知道待排数字的最大数字的位数是多少
以及创建10个队列（分别存储某位置上是0–9之间数字）
第一趟排序 先排个位上的数字，第一个数字的个位是1，则就将该数字存到存储1的队列中，在看下一个数字个位是2，则就将该数字存到存储2的队列中，在继续看下一个数字个位是2，则就将该数字存到存储2的队列中，在继续看下一个数字个位是9，则就将该数字存到存储9的队列中，在继续看下一个数字个位是3，则就将该数字存到存储3的队列中，在继续看下一个数字个位是7，则就将该数字存到存储7的队列中，至此，队列内容为
队列
【0】NULL
【1】 1
【2】 622 、82
【3】743
【4】NULL
【5】NULL
【6】NULL
【7】127
【8】NULL
【9】599
在将队列里的数字按顺序，按0–9队列输出，至此第一趟结束
输出结果：1、622、82、743、127、599
这组数字乍一看并没有非常有序，但我们可以发现，个位已经有了顺序
第二趟排序 排十位上的数字，第一个数字的十位是0，则就将该数字存到存储0的队列中，在看下一个数字十位是2，则就将该数字存到存储2的队列中，在继续看下一个数字十位是8，则就将该数字存到存储8的队列中，在继续看下一个数字十位是4，则就将该数字存到存储4的队列中，在继续看下一个数字十位是2，则就将该数字存到存储2的队列中，在继续看下一个数字十位是9，则就将该数字存到存储9的队列中，至此，队列内容为
【0】 1
【1】 NULL
【2】 622、127
【3】NULL
【4】743
【5】NULL
【6】NULL
【7】NULL
【8】82
【9】599
在将队列里的数字按顺序，按0–9队列输出，至此第二趟结束
输出结果：1、622、127、743、82、599
我们这次可以发现，十位已经有了顺序
第三趟排序 排百位上的数字，第一个数字的百位是0，则就将该数字存到存储0的队列中，在看下一个数字百位是6，则就将该数字存到存储6的队列中，在继续看下一个数字百位是1，则就将该数字存到存储1的队列中，在继续看下一个数字百位是7，则就将该数字存到存储7的队列中，在继续看下一个数字百位是0，则就将该数字存到存储0的队列中，在继续看下一个数字百位是5，则就将该数字存到存储5的队列中，至此，队列内容为
【0】 1、82
【1】 127
【2】 NULL
【3】 NULL
【4】 NULL
【5】 599
【6】 622
【7】 743
【8】 NULL
【9】 NULL
在将队列里的数字按顺序，按0–9队列输出，至此第三趟结束
输出结果：1、82、127、599、622、743
我们这次可以发现，百位即最大为已经有了顺序
至此，基数排序完成
参考代码
#include
#include
#include #define LENGTH 15//待排序的数字个数typedef struct Que//定义队列
{
int *data;
int head;
int tail;
}Que;
int Getmax(int arr[],int len)//获得最大数字的位数
{
int max = arr[0];
for(int i=0;
i 推荐阅读
- 人工智能|干货！人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题（持续更新...)
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点（详细介绍 Python 中的 7 种交叉验证方法！）