锐客网

  1. 首页 > it技术 > >

算法|数据结构（基数排序）

算法数据结构排序算法

基数排序 基数排序(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

    推荐阅读


    上一篇：都在这里了！5个最好的AI平台

    下一篇：Center os安装MySQL8.0启动失败的解决办法