博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[学习笔记]基数排序
阅读量:6238 次
发布时间:2019-06-22

本文共 1488 字,大约阅读时间需要 4 分钟。

考试现场yy

和SA的基数排序一样啦。甚至更简单的多。

从低到高按位处理。

每次重新更新。

也可以写成SA的形式:甚至我直接用的SA数组名

luogu【模板】快速排序

// luogu-judger-enable-o2#include
#define reg register int#define il inline#define numb (ch^'0')using namespace std;typedef long long ll;il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x);}namespace Miracle{const int N=100002;int a[N];int b[N];int buc[N],m;int x[N],y[N];int sa[N],rk[N];void ji(int n){ m=10; ll tmp=10; int num; for(reg i=1;i<=n;++i) ++buc[x[i]=a[i]%10]; for(reg i=0;i<=m;++i) buc[i]+=buc[i-1]; for(reg i=1;i<=n;++i) sa[buc[x[i]]--]=i; for(reg k=2;k<=10;++k){ //cout<<" kk "<
<
=1;--i) sa[buc[x[y[i]]]--]=y[i]; num=1; for(reg i=2;i<=n;++i){ if(a[sa[i]]%tmp!=a[sa[i-1]]%tmp) ++num; } //if(num==n) break; m=num; } for(reg i=1;i<=n;++i) b[i]=a[sa[i]];}int main(){ int n; cin>>n; for(reg i=1;i<=n;++i) rd(a[i]); ji(n); for(reg i=1;i<=n;++i){ printf("%d ",b[i]); }return 0;}}signed main(){// freopen("data.in","r",stdin);// freopen("my.out","w",stdout); Miracle::main(); return 0;}/* Author: *Miracle* Date: 2019/1/14 9:24:07*/

复杂度O(nlogmax)log是以10为底的。值域小的时候理论比sort快。

 

 

当然不必这么拘束

基数排序就是分块的桶排

所以可以以2^8为基数,也就是2^8的桶

4次就搞定了

(2^8对缓存有利,,,有利于卡常)

转载于:https://www.cnblogs.com/Miracevin/p/10267854.html

你可能感兴趣的文章
Darwin Streaming Server 核心代码分析
查看>>
Linux系统安装
查看>>
WordPress 后台禁用Google Open Sans字体,加速网站
查看>>
如何获取好链接??(下)
查看>>
Javascript与Ajax
查看>>
X11转发图形界面的问题处理方式
查看>>
Django 过滤器
查看>>
linux 中建立HTTPS访问
查看>>
Environment variable ORACLE_UNQNAME not defined
查看>>
Exchange各版本号收集
查看>>
NAS与SAN存储
查看>>
【Case分享】Exchange 2013EMS命令无法加载
查看>>
nrm切换npm源利器
查看>>
[C编程在Linux上]用 printf做彩色日志记录
查看>>
O365结合ADFS限制用户登录地址 (二) - 安装AAD Connect
查看>>
Lync 2013 配合 Sonus SBC 1000/2000 配置呼叫转接和同时拨打
查看>>
工作流引擎Synchro Flow的流程度量
查看>>
asp.net 使用ffmpeg.exe获取视频信息并截图方法类
查看>>
Go36-31-sync.WaitGroup和sync.Once
查看>>
input设置为disabled提交后获取不到该值的解决方法
查看>>