基数排序详解
1）前言：计数排序
要学基数排序，掌握计数排序非常重要。
计数排序的原理十分的简单。举个例子，排序5 2 4 1 3，你打算怎么办？很简单是不是，冒泡排序、选择排序、归并排序……这些都足以解决。但如果你有100000000个数要排序，你可能就要束手就擒了。
那如归这时候我告诉你：这100000000个数都不超过100000，你会怎么想？（假设没有负数）
你肯定会拍手说：开个100000的数组，把100000000个数里有几个1、几个2、几个3……给记下来不就完了！
没错，这就是计数排序。只要把一个个数给扔到自己相应的【垃圾桶】里不就好了吗？
这是后，有人问了：这个排序算法……好像不怎么稳定啊。
确实，每个【垃圾桶】都可以看做一个【栈】，统统丢进去后再拿出来，顺序就反了。这时候，聪明的人就会说了：最后倒着来一遍不就行啦！
怎么倒着来，请看这里：
#include<iostream>
#define N 5
using namespace std;
int a[N],i;
int b[N];
int d[100001];
int main() {
for(i=0;i<N;i++) cin>>a[i],d[a[i]]++;
for(i=1;i<=100000;i++) d[i]+=d[i-1];
for(int i=N-1;i>=0;i--)
if(d[a[i]])
b[--d[a[i]]]=a[i];
for(int i=0;i<N;i++) cout<<b[i]<<" ";
return 0;
}
这样，就可以高效（前提是a数组的值不能太大）且稳定的排序了。关于它是如何进化成桶排序的，请看下一段——进化！桶排序。
2）进化！桶排序
现在，让我们先来看一下垃圾分类问题：
众所知周（确信），垃圾桶有四种：可回收，厨余，有害，和其他。可回收垃圾桶能放易拉罐、塑料制品、布制品、纸制品等，厨余垃圾桶可以放多岁的猪头，狗舔过的……
就此打住！来看一下刚才我们做了什么蠢事：哦卖糕的，我们一个“垃圾桶”只能放一种“垃圾”！想象一下你没为题啊去倒垃圾，得分别拿着易拉罐、烟头、废电池和旧报纸绕着一排长达3公里的臭气熏天的垃圾桶找“易拉罐桶”、“烟头桶”、“废电池桶”和“旧报纸桶”……不敢想象啊……
所以，我们对着现实垃圾桶来改造一下我们的【垃圾桶】，打个比方说每个【垃圾桶】可以装一百个数，第一个桶可以装099，第二个同可以装100199……这样相当于把能够装下的数的上限提高了99倍。
这时候，有人会问了——那放到某个【垃圾桶】里，这些还是没有排好序的呀，怎么办？
上一段讲了什么？计数排序！就100个数，计数排序一下不就好了吗！
想到这一步的人，已经很好了——究极进化，即将到来！
顺便提一句，几百年前有个哥们儿想到了这玩意，给【垃圾桶】去了个名字——对了！就叫【桶】
究极进化！基数排序
接上一段，我们讲到了桶排序之后再用计数排序。这时候，聪明的人就会说了：怎么一个桶只能装100种数啊？
好的呢！马上到你家门口一个桶装65536个数不JO好了吗？
65536——这就是unsigned short的范围呀！用1个桶就可以把unsigned short范围里的数都给装下来了……但这还不到最后！如果我们在桶里面再套桶呢？
65536再乘上65535……计算器拿来：4294967296！这么多数！都是unsigned int的范围了！
恭喜你那成成就：【俄罗斯套桶】！如果我们把这些桶套三遍、四遍，脸unsigned long long 的范围都不在话下！要知道每次时间复杂度只是O(65536),那么4遍就只是O(262144)!考虑上每次把桶里面的数据放回去，时间复杂度也只是O(262144+4n)近乎O(n)的时间复杂度！还是在unsigned long long的范围之下！
感谢你看到了最后！最后，没看懂的也没关系，代码奉上：
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<iostream>
using namespace std;
int n,m,a[10000005],b[10000005];
int happy[65536];
int getin() {
int res=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
void putout(int x,bool is) {
if(x==0) {
if(is) putchar('0');
return ;
}
putout(x/10,false);
putchar(x%10+'0');
return ;
}
int main() {
//happy sort 快乐排序：线性排序
n=getin();
int p=(1<<16)-1,x;
for(int i=1;i<=n;i++) {
a[i]=getin();
happy[a[i]&p]++;
}
for(int i=1;i<=p;i++) happy[i]+=happy[i-1];
for(int i=n;i>=1;i--) b[happy[a[i]&p]--]=a[i];
p>>=1;
for(int i=0;i<=p;i++) happy[i]=0;
for(int i=1;i<=n;i++) happy[b[i]>>16]++;
for(int i=1;i<=p;i++) happy[i]+=happy[i-1];
for(int i=n;i>=1;i--) a[happy[b[i]>>16]--]=b[i];
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
改一下，就可以变成R92371848的答案了（奇怪，一个bfprt为什么会和基数排序搞上关系？）
#include<iostream>
using namespace std;
int n,m,a[10000005],b[10000005];
int happy[65536];
int getin() {
int res=0;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res;
}
void putout(int x,bool is) {
if(x==0) {
if(is) putchar('0');
return ;
}
putout(x/10,false);
putchar(x%10+'0');
return ;
}
int main() {
//happy sort 快乐排序：线性排序
n=getin();m=getin();
int p=(1<<16)-1,x;
for(int i=1;i<=n;i++) {
a[i]=getin();
happy[a[i]&p]++;
}
for(int i=1;i<=p;i++) happy[i]+=happy[i-1];
for(int i=n;i>=1;i--) b[happy[a[i]&p]--]=a[i];
p>>=1;
for(int i=0;i<=p;i++) happy[i]=0;
for(int i=1;i<=n;i++) happy[b[i]>>16]++;
for(int i=1;i<=p;i++) happy[i]+=happy[i-1];
for(int i=n;i>=1;i--) a[happy[b[i]>>16]--]=b[i];
putout(a[m+1],true);
return 0;
}
感谢君读到这儿！本文由TimelessWelkin原创，转载不用注明（bushi
转载自洛谷博客（2023.8.5）
\(P.S.\) 本文是 TimelessWelkin（那时还叫 caxx_shaozenan）很久以前写的（远古？大雾），不喜勿喷。