数据结构基数排序（Radix Sort）详解附C++代码实现：

灰太狼 2024-02-19 18:11 48阅读 0赞

**目录**

简介：

图解：

C++代码实现：

总结：

--------------------

## 简介： ##

基数排序的发明可以追溯到1887年赫尔曼何乐礼在打孔卡片制表机上的贡献。  
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。

按低位优先级排序或按高位优先级排序取决于自己兴趣，下面的代码按低位优先。

## 算法简述： ##

1.取得数组中最大的数的位数max\_bit

2.分散：将数组的所有数按照第i位（初始时，i=1，以后i++）的大小，填充到队列数组里（大小为10）

3.收集：将不为空的队列中首尾相连的填充到数组中，i++。

4.直到i>max\_bit,否则，循环执行2、3

## 图解： ##

![849589-20171015232453668-1397662527.gif][]

## C++代码实现： ##

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #include<time.h>
    #include<queue>
    using namespace std;
    #define range 100000     // 控制数组的大小 
    int myrandom(int a[])    //随机填充数组 
    {
    	int max=0;
    	srand((unsigned)time(NULL));
    	for(int i=0;i<range;i++)
    	{
    		a[i]=rand()%range+1;
    		if(a[i]>max)
    		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<int> temp[10];
    	int mod=10;
    	int div=1;
    	int j=0;
    	int num=0;
    	for(int i=0;i<max_bit;i++,mod*=10,div*=10)
    	{
    		
    		for(j=0;j<range;j++)
    		{
    			num=(a[j]%mod)/div;
    			temp[num].push(a[j]);
    		}
    		int pos=0;
    		for(j=0;j<10;j++)
    		{
    			
    			while(!temp[j].empty())
    			{
    				
    				a[pos++]=temp[j].front();
    				temp[j].pop();
    			}
    		}
    	}
    }
    int main()
    {
    	clock_t start,end;           // 用于测试 用时 
    	start=clock();
    	freopen("out基数排序.txt","w",stdout); // 重定向 
    	int a[range];
    	
    	int max=myrandom(a);
    	int bit_max=Max_bit(max);
    	
    	RadixSort(a,bit_max);
    	for(int i=0;i<range;i++)
    	{
    		printf("%5d ",a[i]);
    		if((i+1)%50==0)
    		printf("\n");
    	}
    	end=clock();
    	cout<<range<<"个数据通过基数排序耗时："<<(float)(end-start)*1000.0/CLOCKS_PER_SEC<<"ms"<<endl; 
    	return 0;
    }

差点忘了给测试结果了，(\#^.^\#)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1][]

## 总结： ##

它是稳定的，是非比较类排序算法。

时间复杂度分析：

如果最大数的位数为k，每一次分配与收集都为o（2\*range），（range为测试数据的大小）

所以，总的时间复杂度为o（k\*2\*range）

当k远小于range时，可以看做是线性的。

小伙伴们，如果还看不懂，在评论区留言。

（上学期我老师的一句话：一个人自己懂了，不见的是真懂，只有给别人讲明白了，才算真的懂。ps：我老师是菊厂毕业的O(∩\_∩)O哈哈~）

[849589-20171015232453668-1397662527.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/c4fa75c519544c51bb1799cf26e36db3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/78dcf03ad1254ac98f747314437a21b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzI1Njk4_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/710e9eb71efa4f1f93d6ca41f68f05ea.png