基数排序详解

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公里的臭气熏天的垃圾桶找“易拉罐桶”、“烟头桶”、“废电池桶”和“旧报纸桶”……不敢想象啊……

所以，我们对着现实垃圾桶来改造一下我们的【垃圾桶】，打个比方说每个【垃圾桶】可以装一百个数，第一个桶可以装0_{99，第二个同可以装100}199……这样相当于把能够装下的数的上限提高了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）很久以前写的（远古？大雾），不喜勿喷。