【算法】基数排序
前面介绍的各类排序方法(快速排序,归并排序,插入排序等)都是建立在关键字比较的基础上,而分配类排序不需要比较关键字的大小。它是根据关键字中各位的值,通过对待排序记录进行若干趟“分配”与“收集”来实现排序的,是一种借助于多关键字排序的思想对单关键字排序的方法。
基数排序(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<iostream>
#include<cstdio>
#include<cmath> // 包含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;i<n;i++)
{
if(a[i]>max)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<n;i++)
{
bucket[(a[i]/exp)%10]++;
}
// 重置各个桶中的个数
for(int i=1;i<10;i++)
{
bucket[i]+=bucket[i-1];
}
// 将各个桶中对应的数放入临时存储数组temp中
for(int i=n-1;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<n;i++)
{
a[i]=temp[i];
}
}
//【基数排序】
// a -- 数组
// n -- 数组长度
void radixsort(int a[],int n)
{
int exp; // 指数。当对数组按各位进行排序时,exp=1;按十位进行排序时,exp=10;...
int max = get_max(a, n); // 数组a中的最大值
//【最低位优先法】【LSD】
// 从个位开始,对数组a按"指数"进行排序
for (exp = 1; max/exp > 0; exp *= 10)
countsort(a, n, exp);// 按照某位数(exp),对数组a进行排序
}
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
radixsort(a,n);//【基数排序】
for(int i=0;i<n-1;i++)
{
printf("%d ",a[i]);
}
printf("%d\n",a[n-1]);
}
运行结果:
LSD版MSD图文说明:【最高位优先法】
还是上面那个例子,还是那个待排序序列 {50,123,543,187,49,30,0,2,11,100},我们采用最高位优先法进行排序。
-
首先按照百位数的不同进行分配,得到的分配表如下图所示:
百位数分配表 由上图(百位数分配表)可知,整个待排序序列被分为3个子序列。
-
对这三个子序列(序列1、2、3)按照十位数的不同进行分配,其中,序列1和序列2中含有多个值(大于等于2个), 序列3中仅含有一个值。因此,我们仅需要对序列1和序列2进行再分配。(根据最高位优先法的完成排序标准)得到的分配表如下图所示:
十位数分配表 最高位优先法完成排序的标准为:直到每个子序列中只有一个关键字为止。(这也是程序中递归结束的条件)
-
完成十位数的分配后,我们需要对序列4(由序列1分配而形成),按照个位数的不同进行再分配。
个位数分配表
-
完成了上述三次分配过程(实际上进行了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<cstdio>
#include<iostream>
#include<cmath>// 含有pow函数
#include<cstring>// 含有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;i<n;i++)
{
if(arr[i]>max)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<n;i++)
{
//scanf("%d",&arr[i]);
arr[i]=read();// 输入优化
}
int d=getmax(arr);
radixsort(arr,0,n-1,d);
for(int i=0;i<n;i++)
{
// 输出优化
write(arr[i]);
putchar(' ');
//printf("%d ",arr[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 (输入输出优化)
整理不易,欢迎指正。喜欢的可以点点关注。
网友评论