快排

//快速排序 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
int n;
int a[N];
void s(int l,int r){//快速排序函数 
	if(l>=r)	return ;//递归结束条件 
	int i=l;//将左指针给i 
	int j=r;//将右指针给j 
	int q=a[r];//q代表基数 
	while(i<j){ 
		while(a[i]<=q&&i<j){ //从左向右找比key大的值 
			i++;
		}
		a[j]=a[i];//不成立交换i,j对应的值
		while(a[j]>=q&&i<j){//从右向左找比key小的值 
			j--;
		}
		a[i]=a[j];//不成立交换i,j对应的值 
	}
	a[j]=q;//基数与j对应值交换 
	s(l,i-1);//进行递归左部分 左指针为l 右指针为i-1 
	s(i+1,r);//进行递归左部分 左指针为i+1 右指针为r 
} 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	s(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	return 0;
}