三路快排

算法标签：排序，随机化，分治。

我这个人很喜欢比较玄学但是优秀的算法和数据结构。

众所周知，我们考试的时候经常遇到毒瘤出题人卡算法。但是我们也知道：“如果我自己都不知道我在干什么，你就别想卡我啦。”

所以说 $mt19937$ 天下第一！(不是CCF准用 c++14了嘛)

浅谈mt19937

简单提一下 $mt19937$ ,给一个使用示例吧:

mt19937 RdOri(time(0));
#define rd(L,R) (int)((1.0*RdOri()/UINT_MAX)*(R-L+1))+L

这样就可以支持使用 $rd(l,r)$ 生成区间 $[l,r]$ 内的随机数了。

当然把宏定义里的类型 $int$ 改成其他类型也是可以的。

需要注意的是 $mt19937$ 的范围是 $usigned\ int$ (UINT_MAX) 但是可以用来生成负数，但是我们应当将绝对值小的作为 $L$。如果需要更大的随机数，我们使用 $mt19937_64$,范围为 $usigned\ long\ long$ (ULLONG_MAX)。

最后为了防止邪教出题人卡 $time(0)$,我们可以使用更好的种子: $chrono::system_clock::now.time_since_epoch().count()$

三路快排

算法思想是随机取一个键值 $key$，把序列分为三段：小于 $key$ 的，等于 $key$ 的，大于 $key$ 的。实现考虑分治。

我们在每一个子问题中，考虑枚举当前点下标 $i$,维护第一个等于 $key$ 的值的下标 $j$ 和第一个大于 $key$ 的下标 $k$。

对于当前点，如果它等于 $key$ 我们直接把当前点融入到二号段，当前点下标 $i$ 向后移一位。如果其小于 $key$ 把它与二段队首交换位置，二段队首下标 $j$ 向后移一位，当前点下标 $i$ 向后移一位。如果其大于 $key$，考虑把它与空白段的队尾也就是三段的队首的前一位交换位置，三段队首下标 $k$ 向前移动一位，由于当前点上的值是空白段交换来的，所以当前点下标 $i$ 不动。

递归边界就是当当前区间 $[l,r]$ 满足 $l>=r$。

最优复杂度为 $O(n)$，总之效率比普通快排高就是了，而且加上了随机化可防卡。

下面是代码:

#include<bits/stdc++.h>
using namespace std;
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout)
#define LL long long
#define N 100000+3
mt19937 RdOri(time(0));
#define rd(L,R) (int)((1.0*RdOri()/UINT_MAX)*(R-L+1))+L
inline int read(){
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||'9'<ch) {if(ch=='-') f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9') {s=s*10+(ch^48);ch=getchar();}
	return s*f;
}
inline void Swap(int &x,int &y){
	int tmp=x;x=y;y=tmp;
}
void ThreeSort(int *a,int l,int r){
	if(l>=r) return;
	int key=a[rd(l,r)];
	int i=l,j=l-1,k=r+1;
	while(i<k){
		if(a[i]<key){
            ++j;
			Swap(a[i],a[j]);
			++i;
		}else if(key<a[i]){
			--k;
			Swap(a[i],a[k]);
		}else ++i;
	}
	ThreeSort(a,l,j);
	ThreeSort(a,k,r);
}
int n;
int a[N];
int main(){
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
	}
	ThreeSort(a,1,n);
	for(int i=1;i<=n;++i){
		printf("%d ",a[i]);
	}
	return 0;
}