一种快速排序的模板

#include<cstdio>
int a[100005],t[100005],n;
void quicksort(int l,int r);				//l,r是排序的下界和上界
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	quicksort(1,n);
	for(int i=1;i<=n;i++)
		printf("%d ",a[i]);
	return 0;
}
void quicksort(int l,int r)
{
	int flag=a[(l+r)/2];
	if(l>=r) return;
	int p=l,q=r;
	for(int i=l;i<=r;i++)
	{
		if(a[i]<flag) t[p++]=a[i];		//若a[i]<flag，那么把a[i]放在前面
		if(a[i]>flag) t[q--]=a[i];		//若a[i]>flag，那么把a[i]放在后面
	}
	for(int i=l;i<p;i++)
		a[i]=t[i];
	for(int i=r;i>q;i--)
		a[i]=t[i];
	for(int i=p;i<=q;i++)
		a[i]=flag;						//中间部分放入flag，这样就把要排序的部分分为了三部分
	quicksort(l,p-1);					//再对前后两部分进行快速排序
	quicksort(q+1,r);
}

基于比较的排序算法，时间复杂度最快为O(nlogn)，而快速排序时间复杂度为O(nlogn)