记录编号	279976	评测结果	AAAAAAAAAA
题目名称	排序测试	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	3.874 s
提交时间	2016-07-09 19:23:34	内存使用	15.55 MiB

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<algorithm>
using namespace std;
const int maxn=2000100;
struct random{
	int a,b,c,x,MOD;
	random(){}
	void init(int m){
		srand(time(0));
		a=rand();
		b=rand();
		c=rand();
		x=rand();
		MOD=m;
	}
	int operator()(){
		x=abs((a*x*x+b*x+c))%MOD;
		return x;
	}
}rander;
void qsort(int,int);
void msort(int,int);
int n,a[maxn],c[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("sorttest.in","r",stdin);
	freopen("sorttest.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	rander.init(n);
	if(rand()&1)qsort(1,n);//快排归并混合排序大法好!!!
	else msort(1,n);
	for(int i=1;i<=n;i++)printf("%d ",a[i]);
	return 0;
}
inline void qsort(int l,int r){
	if(l>=r)return;
	int i=l,j=l+1;
	swap(a[l],a[(rander()%(r-l))+l+1]);
	while(j<=r){
		if(a[j]<a[l])swap(a[++i],a[j]);
		else if(a[j]==a[l]&&rand()&1)swap(a[++i],a[j]);
		j++;
	}
	swap(a[l],a[i]);
	msort(l,i-1);
	msort(i+1,r);
}
inline void msort(int s,int t){
	if(s>=t)return;
	int mid=(s+t)>>1;
	qsort(s,mid);
	qsort(mid+1,t);
	int i=s,j=mid+1,k=0;
	while(i<=mid&&j<=t){
		if(a[i]<a[j])c[k]=a[i++];
		else c[k]=a[j++];
		k++;
	}
	while(i<=mid)c[k++]=a[i++];
	while(j<=t)c[k++]=a[j++];
	for(int i=s,j=0;i<=t;i++,j++)a[i]=c[j];
}