快速排序

#include<bits/stdc++.h>
using namespace std;
int a[1000001],n;
void quick_sort(int left,int right){
	if(left>=right) return;//递归边界
	//1.找到基准值：（中间）
	int mid = (left+right)/2;
	//2.基准值和最右边的值进行交换
	swap(a[mid],a[right]);
	//3.设置双指针(下标)  i，j
	int i = left,j = right-1;
	while(i<=j){
		//4.当i位置上的值小于基准值，一直向右走、
		while(a[i]<=a[right] && i<=j) i++;
		//5.当j位置上的值大于基准值，一直向左走、
		while(a[j]>=a[right] && i<=j) j--;
		//6.区间没有交错，那么交换i,j的值
		if(i<=j) swap(a[i],a[j]);
	}
	swap(a[i],a[right]);//
	quick_sort(left,i-1);//左边快速排序
	quick_sort(i+1,right);//右边快速排序
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	//快速排序
	quick_sort(1,n);
	for(int i=1;i<=n;i++){
		cout<<a[i]<<" ";
	}
	
	return 0;
}