排序|排序 | 基数排序 Radix Sort 排序|基数排序RadixSort

【算法】基数排序前面介绍的各类排序方法(快速排序，归并排序，插入排序等)都是建立在关键字比较的基础上，而分配类排序不需要比较关键字的大小。它是根据关键字中各位的值，通过对待排序记录进行若干趟“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。
基数排序（Radix Sorting）就是典型的分配类排序。
基本思想：
基数排序(Radix Sorting)是桶排序的扩展。
它的基本思想是：将整数（十进制）按位数切割成不同的数字，然后按每个位数分别进行比较。
具体做法是：找出所有待比较的整数中的最大值，求出最大的数位长度，将所有待比较的整数统一成同样的数位长度，数位较短的数前面补零，然后按每个位数分别进行比较。
分类：
按照位数比较顺序的不同，将其分为LSD（Least significant digital）和MSD（Most significant digital）两类。

最低位优先法(LSD)
从最低位（个位）开始，依次进行一次排序，直到到达最高位。这样从最低位排序，一直到最高位排序完成以后, 数列就变成一个有序序列。
最高位优先法(MSD)
从最高位开始，依次进行一次排序，直到到达最低位（个位）。
MSD与LSD在分配收集过程中的不同
MSD：当待排序序列按照位数不同进行分配后，相当于进入了多个子序列，后续的排序工作分别在各个子序列中进行。
LSD：每次分配和收集都是相对于整个序列而言的。

LSD图文说明：【最低位优先法】
假设对一待排序序列 {50，123，543，187，49，30，0，2，11，100} 进行基数排序（最低位优先法），该序列的最大数位是3(即百位)，每个数位的范围为[0,9]。

首先将各个整数按照其个位数字的不同进行分配，分配表如下图所示：

文章图片
个位数分配表借助个位数分配表，按照先后顺序，收集后得到的序列为 {50，30，0，100，11，2，123，543，187，49}。
在该序列的基础上，按照十位数字的不同进行分配，分配表如下图所示：

文章图片
十位数分配表借助十位数分配表，按照先后顺序，收集后得到的序列为 {0，100，2，11，123，30，543，49，50，187}。
在该序列的基础上，按照百位数字的不同进行分配，分配表如下图所示：

文章图片
百位数分配表借助百位数分配表，按照先后顺序，收集后得到的序列为 {0，2，11，30，49，50，100，123，187，543}。

通过上述三次分配和收集，我们最终得到了一个排序好的有序序列：{0，2，11，30，49，50，100，123，187，543}。
实现代码：【C++ & LSD版】

//【基数排序】 #include #include #include // 包含pow函数 using namespace std; int n; int a[200010]; // 获取数组a中最大的数 // a -- 数组 // n -- 数组长度 int get_max(int a[],int n) { int max=a[0]; for(int i=1; imax)max=a[i]; } return max; }//对数组按照"某个位数"进行排序(桶排序) // a -- 数组 // n -- 数组长度 // exp -- 指数。对数组a按照该指数进行排序 // 当exp=1，表示按照"个位"对数组a进行排序 // 当exp=10，表示按照"十位"对数组a进行排序 void countsort(int a[],int n,int exp) { int temp[n]; int bucket[10]={0}; // 将exp对应的位数放入对应的桶中 for(int i=0; i=0; i--)//这里要从右向左扫描，保证排序稳定性 { temp[bucket[(a[i]/exp)%10]-1]=a[i]; // 注意temp数组下标要减一，因为数组temp下标是从0开始的 bucket[(a[i]/exp)%10]--; // 每放入一个数据，对应的bucket[]数组的值应减一 } // 将排序好的数据(保存在数组temp中)赋值给数组a for(int i=0; i 0; exp *= 10) countsort(a, n, exp); // 按照某位数(exp)，对数组a进行排序 }int main() { scanf("%d",&n); for(int i=0; i



 
 运行结果：  

文章图片 

 LSD版  MSD图文说明：【最高位优先法】

 
 还是上面那个例子，还是那个待排序序列 {50，123，543，187，49，30，0，2，11，100}，我们采用最高位优先法进行排序。

 
  
 首先按照百位数的不同进行分配，得到的分配表如下图所示：


  

文章图片 

 百位数分配表 由上图（百位数分配表）可知，整个待排序序列被分为3个子序列。

  
 对这三个子序列（序列1、2、3）按照十位数的不同进行分配，其中，序列1和序列2中含有多个值（大于等于2个）， 序列3中仅含有一个值。因此，我们仅需要对序列1和序列2进行再分配。（根据最高位优先法的完成排序标准）得到的分配表如下图所示：


  

文章图片 

 十位数分配表 最高位优先法完成排序的标准为：直到每个子序列中只有一个关键字为止。（这也是程序中递归结束的条件）

  
 完成十位数的分配后，我们需要对序列4（由序列1分配而形成），按照个位数的不同进行再分配。


  

文章图片 

 个位数分配表 

  
【排序|排序 | 基数排序 Radix Sort】完成了上述三次分配过程（实际上进行了4次，按照十位数分配的过程进行了两次），我们还需要根据递归的顺序，进行**收集。

 
  
 我们最终得到了一个排序好的有序序列：{0，2，11，30，49，50，100，123，187，543}。

 
 在这里我手写了一个简单的排序过程，配合下面的实现代码，可以帮助理解。


  

文章图片 

  

 
 上图没有递归弹回的过程，这里简述一下。

 
 从子序列｛0，2｝开始弹回，到最终的子序列｛543｝：
 ｛0，2｝-> ｛11，30，49，50｝-> ｛100，123，187｝->｛543｝。

 
 最终再根据各个值在数组中的位置，进行收集，即可得到最终的有序序列。

 
 实现代码：【C++ & MSD版】 
 #include
#include
#include// 含有pow函数 
#include// 含有memset、memcpy函数 
using namespace std;
int n;

int arr[100010];
//输入优化【适用于正负整数】 
inline int read() 
{ 
int X=0,w=0;
 
char ch=0;
 
while(!isdigit(ch)) 
{
w|=ch=='-';

ch=getchar();

} 
while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
 
return w?-X:X;
 
}//输出优化【适用于正负整数】 
inline void write(int x) 
{
if(x<0) putchar('-'),x=-x;

if(x>9) write(x/10);

putchar(x%10+'0');
 
}// 获取数组所有整数中的最高位数 
int getmax(int arr[])
{
// 获取数组中的最大整数 
int max=arr[0];

for(int i=1;
imax)max=arr[i];

}
// 获取最大整数max的位数 
int count=1;
// count：位数，初始为1 
while(max/10>=1)
{
count++;
// 位数+1 
max/=10;
// 即 max=max/10;
 
}
return count;
// 返回最高位数count 
}//获取整数x第d位的值 
// 例如，当x==1450，d==4，此时getdigit函数返回1(位于千位上的数)
//当x==1450，d==3，此时getdigit函数返回4(位于百位上的数)
int getdigit(int x,int d)
{
if(d>1)
{
int exp=pow(10,d-1);
//【坑点：注意是10^(d-1)，这个坑卡了我好长时间】 
return (x/exp)%10;

}
else return x%10;

}//【基数排序】
// 根据第d位的原则，对数组arr[begin...end]的值进行一趟基数排序
// 当d==4，表示对千位进行基数排序 
void radixsort(int arr[],int begin,int end,int d)
{
// 数组count,flag,temp初始化，均数组中的值初始化为0 
int count[10]={0};
//
// 等价于 memset(count,0,sizeof(count));
 
int flag[10]={0};
// 统计数组arr[begin...end]所有值中，第d位对应值(0~9)的个数。当个数小于2时(flag[i]<2)，不需要再进行基数排序 
int temp[10]={0};
// cout的一个拷贝，因为后面有操作count[i]--,破坏了count本来的值，所以需要有一个拷贝 
int *bucket=new int[end-begin+1];
// 动态申请数组bucket，用于暂时存储数组arr[begin...end]的值 
//int *bucket = (int *) malloc((end-begin+1) * sizeof(int));
for(int i=begin;
i<=end;
i++)// 
{
count[getdigit(arr[i],d)]++;
// 统计数组arr[begin...end]所有值中，第d位对应值(0~9)的个数。
//flag[getdigit(arr[i],d)]++;

//temp[getdigit(arr[i],d)]++;

}memcpy(flag,count,10*sizeof(int));
// 将数组count复制(拷贝)给数组flag【memcpy函数】 for(int i=1;
i<10;
i++)// 注意i从1开始，因为第d位对应值为0的数量上限为count[0]，不需要进行操作 
{
count[i]+=count[i-1];
// count[i]表示：第d位对应值为i的数量上限 
//temp[i]+=temp[i-1];

}memcpy(temp,count,10*sizeof(int));
// 将数组count拷贝给数组temp【memcpy函数】 //这里要从右向左扫描，保证排序稳定性 
for(int i=end;
i>=begin;
i--)
{
int j=getdigit(arr[i],d);
// 获取整数arr[i]第d位对应的值 
bucket[count[j]-1]=arr[i];
// 将arr[i]放入对应的临时存储数组bucket中
// 注意bucket数组下标要减一，因为数组bucket下标是从0开始的
count[j]--;
// 每放入一个数据，对应的数组count的值应减一
// 也正是这个操作，使得数组count原来的值发生改变。 
}//将排序好的数据(保存在数组bucket中)赋值给数组a
int index=0;
// 数组bucket的下标，从0开始 
for(int i=begin;
i<=end;
i++)
{
arr[i]=bucket[index];

index++;

}delete []bucket;
// 释放数组bucket的内存 
//free(bucket);
 int p1=0;
// 第d位对应值为i的桶顶索引(数量下限)
int p2=0;
// 第d位对应值为i的桶底索引(数量上限)
int front;
// 记录第i-1个桶的值temp[i-1]。
// if(i==0) front=0；else front=temp[i-1] 
for (int i = 0;
 i < 10;
 ++i)
{
// 当桶的元素数量大于等于2时，即桶中至少有两个元素，才进行一趟基数排序 
if(flag[i]>=2)
{
// 计算出数量下限
if(i==0) front=0;

else front=temp[i-1];

p1=begin+front;
 // 计算出数量上限 
if(i<9) p2=begin+temp[i]-1;

else p2=end;
if (p1 < p2 && d > 1)// 当数量上限大于数量下限 且 位数d大于1 时，对数组arr[p1...p2]进行基数排序【递归】 
{
radixsort(arr, p1, p2, d - 1);
// 递归调用，进行基数排序，数位降1(d-1)
}
}
}
}int main()
{
scanf("%d",&n);

int t;

for(int i=0;
i


 
 运行结果：  

文章图片 

 MSD版  算法特点：

 
  
是稳定排序。 
可用于链式结构，也可用于顺序结构。 
时间复杂度可以突破基于关键字比较一类方法的下界O(n*)，达到O(n)。  
基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。（如在对整数进行排序的过程中，每个位数的值都在0~9的范围内） 
LSD的基数排序适用于位数少的数列；如果位数多的话，使用MSD的效率会比较好。 
  
 写在最后：

 
 参考资料：

 
  
《数据结构(C语言版) (第2版)》严蔚敏 
博客：https://www.cnblogs.com/skywang12345/p/3603669.html  
博客：http://www.cnblogs.com/Braveliu/archive/2013/01/21/2870201.html (基数排序的稳定性分析) 
CSDN博客：https://blog.csdn.net/double_happiness/article/details/72452243  
CSDN博客：https://blog.csdn.net/liupeifeng3514/article/details/83412176 && https://blog.csdn.net/liupeifeng3514/article/details/83383429#_139 (部分示例图片来源) 
CSDN博客：https://blog.csdn.net/liyizhixl/article/details/54412459 (输入输出优化) 
  
 整理不易，欢迎指正。喜欢的可以点点关注。



		  	

    
    




    
    
    


推荐阅读

           
                  
              
                  脚趾甲砸了一个月可以洗澡吗 
                
                   
                
              
            

                  
              
                  C++|C++ std::shared_mutex读写锁的使用 
                
                   
                
              
            

                  
              
                  轮胎怎么看正反面 
                
                   
                
              
            

                  
              
                  介绍予盾是什么意思 
                
                   
                
              
            

                  
              
                  京津冀拼音 京津冀怎么读 
                
                   
                
              
            

                  
              
                  m三款高配低价的手机，既好看又实用，坚持几年没问题 
                
                   
                
              
            

                  
              
                  回避的方式及法定事由有哪些？ 
                
                   
                
              
            

                  
              
                  黑啤是黑色的吗为什么？黑啤与普通啤酒的区别？ 
                
                   
                
              
            

                  
              
                  芦荟掰下来怎么生根 芦荟小芽没根还能活不 
                
                   
                
              
            

                  
              
                  炕羊排的制作方法 
                
                   
                
              
            

                  
              
                  三车追尾最后一辆车有没有责任 
                
                   
                
              
            

                  
              
                  四川大学华西医院|以色列舍巴医学中心与华西医院签署谅解备忘录，将建姊妹医院 
                
                   
                
              
            

                  
              
                  历史上孙策厉害吗，东汉诸侯孙策的简介生平介绍 
                
                   
                
              
            

                  
              
                  打底衫和毛衣的区别是什么 
                
                   
                
              
            

                  
              
                  年假一般什么时候放 拼多多电商什么时候放年假，电商公司年假一般是几天 
                
                   
                
              
            

                  
              
                  最新发布的5G旗舰手机荣耀V30值不值得买？ 
                
                   
                
              
            

                  
              
                  左手中指戴戒指啥意思呢 左手中指戴戒指啥意思呢男 
                
                   
                
              
            

                  
              
                  违反诫命者的刑罚(三) 
                
                   
                
              
            

                  
              
                  火焰山取暖炉售后电话,火焰山取暖炉售后电话是多少 
                
                   
                
              
            

                  
              
                  DD13是什么材质 dd13是什么材质 
                
                   
                
              
            

          

一个选择排序算法 
 排序（归并排序） 
 【图解】9张图彻底搞懂堆排序 
 vue|vue 上移 下移 删除 排序 
 必须掌握的八种基本排序算法 
 【排序】插入排序算法 
 排序之冒泡和选择 
 2019-03-02|2019-03-02 排序 
 Java数据结构与算法（十）排序算法01 
 不为人知的排序和筛选用法