基数排序

【简介】

    计数排序的时间复杂度是O(n+m)的，n为元素个数，m为桶的大小。

    从低位到高位的方法可以加快速度（卡常数）。

    分块分为3块最好了（利用CPU三级缓存的原理）

    这样1e的数据可以卡到2秒左右。

    WC2017 T2真是丧心病狂。

【代码】

#include <ctime>
#include <cstdio> 
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

#pragma GCC optimize(2)

using namespace std;

#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)

#define maxn 100000005 

int a[maxn+15],n;
const int base2=32767,base3=1023;
int top=0;
int hash[base2+15],res[maxn+15];
int hash2[base3+15],res2[maxn+15];
vector <int> v[base2+15];

int main()
{
	n=maxn;
	F(i,1,n) a[i]=(rand()%30000)*(rand()%30000);
//	int k1=clock(),k2;
	/*
	for (int i=1;i<=n;++i) v[a[i]&base2].push_back(a[i]);
	top=0;
	F(i,0,32767)
	{
		for (int j=0;j<v[i].size();++j) a[++top]=v[i][j];
		v[i].clear();
	}
	for (int i=1;i<=n;++i) v[(a[i]>>15)&base2].push_back(a[i]);
	top=0;
	F(i,0,32767) for (int j=0;j<v[i].size();++j) a[++top]=v[i][j];
	*/ //6s
	
	
	/*
	F(i,1,n) ++hash[a[i]&base2];
	F(i,1,base2) hash[i]+=hash[i-1];
	D(i,n,1)
	{
		res[hash[a[i]&base2]--]=a[i];
	}
	memcpy(a,res,(n+1)*sizeof (int));
	memset(hash,0,sizeof hash);
	F(i,1,n) ++hash[(a[i]>>15)&base2];
	F(i,1,base2) hash[i]+=hash[i-1];
	D(i,n,1) res[hash[(a[i]>>15)&base2]--]=a[i];
	memcpy(a,res,(n+1)*sizeof (int));
	k2=clock();
	printf("%d %d
",k1,k2);
	*/ //2.3s
	
	
	F(i,1,n) ++hash2[a[i]&base3];
	F(i,1,base3) hash2[i]+=hash2[i-1];
	D(i,n,1) res2[hash2[a[i]&base3]--]=a[i];
	memcpy(a,res2,(n+1)*sizeof (int));
	
	memset(hash2,0,sizeof hash2);
	F(i,1,n) ++hash2[(a[i]>>10)&base3];
	F(i,1,base3) hash2[i]+=hash2[i-1];
	D(i,n,1) res2[hash2[(a[i]>>10)&base3]--]=a[i];
	memcpy(a,res2,(n+1)*sizeof (int));
	
	memset(hash2,0,sizeof hash2);
	F(i,1,n) ++hash2[(a[i]>>20)&base3];
	F(i,1,base3) hash2[i]+=hash2[i-1];
	D(i,n,1) res2[hash2[(a[i]>>20)&base3]--]=a[i];
	memcpy(a,res2,(n+1)*sizeof (int));
	 //1.8s O2: 1.1s
	 
	 
//	k2=clock();
//	printf("%d %d
",k1,k2);
	F(i,1,n) printf("%d%c",a[i],i==n?'
':' ');
}