基数排序

以前没学过，以为是个很难的算法（不然也不会这么快）。

然后今天要用到，就学了一下。最开始没看懂网上的题解，就自己琢磨了一下，然后有点理解了。

桶排序（在 OI-wiki 上称作计数排序，桶排序是另一种）的原理是开一个大小为值域的数组，把需要排序的数字都放在其值在桶里对应的下标处（可以用 vector，也可以用链表），最后从小到大扫一遍桶就是最终排序的结果。

但是可能值域很大，开不下桶：考虑多关键字桶排序。

若把一个数字 \(n\) 表示为 \(\sum_{i=0} a_ix^i\ (0\leq a_i<x)\) 的形式，十进制就是这样的一种形式，在十进制中 \(x\) 就是 \(9\)。然后多关键字排序：比较 \(2\) 个数字的大小，首先比较最高次项的大小，若最高次项相同，则比较最高次项系数 \(a_i\) 的大小，若相同再比较低一次的系数。

把这个过程倒着来，进行 \(\log_x n\) 次桶排序，每次都排当前次项的系数，最后一次排的是最高次项，决定大体关系，而细一点的关系就是前面的几次确定。

很妙的一个思想，跟光速幂所利用的根号分治差不多，利用了时空平衡的思想。

这就是基数排序。

当桶开成 \(\sqrt{n}\) 大小，要排 \(m\) 个数时（设 \(n\) 是最大值），时间复杂度为 \(O((\sqrt{n}+m)\log_{\sqrt{n}}n)\)，约为 \(O(\sqrt{n}+m)\)。在值域不大于 \(m^2\) 时很快。

当然，根据情况，比如给一堆 long long 大小的数排序，可以变成三次根号，或更多次根号。综合来看，在不考虑高精度的情况下，基数排序可以视为常数大的 \(O(m)\) 排序，吊打其它排序。

而且还是稳定排序！

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+50,P=(1<<15)-1; 
struct Edge
{
	int y,Next;
}e[MAXN<<1];
int elast[MAXN],tot;
void Add(int x,int y)
{
	tot++;
	e[tot].y=y;
	e[tot].Next=elast[x];
	elast[x]=tot;
}
int N;
int A[MAXN],B[MAXN];
int Max=0;
int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&B[i]);
		A[i]=B[i];
		Max=max(Max,B[i]);
	}
	int You=0;
	while(Max)
	{
		Max>>=15;
		for(int i=N;i>=1;i--)
		{
			Add((A[i]>>You)&P,i);
		}
		tot=0;
		N=0;
		for(int i=0;i<=P;i++)
		{
			for(int j=elast[i];j;j=e[j].Next)
			{
				B[++N]=A[e[j].y];
			}
			elast[i]=0;
		}
		for(int i=1;i<=N;i++)
		{
			A[i]=B[i];
		}
		You+=15;
	}
	for(int i=1;i<=N;i++)
	{
		printf("%d ",A[i]);
	}
}

代码用了链式前向星作桶，类似于把每个节点看做一个菊花的根，然后连着这个菊花的就是桶里的数。因为链式前向星正着存反着读，所以在代码里要反着加边。