写在前面
基数排序
Redix Sort
,是为数不多不是基于比较的排序,至今此类我们学过的,也就只有基数排序和桶排不基于比较,桶排的效率自然快,但是对内存的消耗不容小视,基数排序则在空间和时间都有这不错的表现,在大多数情况基本于归并排序速度相近,如果你会一些高端的优化的话,他甚至能够吊打桶排
基数排序
时间复杂度: O( d ( r + n ) )
空间复杂度: O( rd + n )
相信你已经根据前文知道,基数排序,不是基于比较的排序,哪们我们如何排序呢?
我们知道桶排的思想是确定其有或没有,然后遍历
但是我们能不能简化?简化成将每一位桶排?
当然可以,这就是基数排序
我们在每一位上进行桶排,让后进行下一位,直到最所有数高位
听起来貌似是很简单的问题,不过现在有一个重要的问题,怎么分离位?
十进制分离法
我们的数字是十进制,而且十进制分离位在C++中依旧很方便 代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[10][110000];
int redix[10][110000];
inline int ws(int t,int n){
t--;
while(t--){
n/=10;
}
return n%10;
}
// ws 分离位数
bool x;// 判断最高位
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
tmp=ws(1,a[i]);
last_redix[tmp][++last_cnt[tmp]]=a[i];// 完成第一位的桶
}
for(int t=2;;t++){
x=false;
for(int i=0;i<=9;i++){
for(int j=1;j<=last_cnt[i];j++){// 按照上一位的顺序,不然排序顺序会乱
tmp=ws(t,last_redix[i][j]);
if(tmp!=0) x=true;
redix[tmp][++cnt[tmp]]=last_redix[i][j];// 桶排
//j++;
}
}
if(!x) break;
memcpy(last_redix,redix,sizeof(redix));// 复制当前到上一次
memcpy(last_cnt,cnt,sizeof(cnt));
memset(cnt,0,sizeof(cnt));
}
for(int i=0;i<=9;i++)// 输出
for(int j=1;j<=last_cnt[i];j++)
printf("%d ",last_redix[i][j]);
}
二进制分割法
但是显然这种位数分离法比较耗时,要是我们能够快一点…… 等一下,二进制时直接位运算就可分离二进制位了啊 代码:
#include <cstdio>
#include <cstring>
using namespace std;
int n;
int a[110000];
int tmp;
int cnt[10],last_cnt[10];;
int last_redix[2][1100];
int redix[2][1100];
inline int ws(int t,int n){
t--;
while(t--){
n/=10;
}
return n%10;
}
bool x;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
//tmp=ws(1,a[i]);
last_redix[(a[i])&1][++last_cnt[(a[i])&1]]=a[i];
}
for(int t=1;t<=31;t++){
//x=false;
for(int i=0;i<=1;i++){
for(int j=1;j<=last_cnt[i];j++){
//tmp=ws(t,last_redix[i][j]);
//if(tmp!=0) x=true;
redix[(last_redix[i][j]>>t)&1][++cnt[(last_redix[i][j]>>t)&1]]=last_redix[i][j];
//j++;
}
}
//if(!x) break;
memcpy(last_redix,redix,sizeof(redix));
memcpy(last_cnt,cnt,sizeof(cnt));
memset(cnt,0,sizeof(cnt));
}
for(int i=0;i<=1;i++)
for(int j=1;j<=last_cnt[i];j++)
printf("%d ",last_redix[i][j]);
}
原理和上面一样,分离位数请参考下一篇: 位运算