快速排序

#include <iostream>

using namespace std;
const int N = 1e6 + 10;
int a[N], n;

void quick_sort(int a[], int l, int r)
{
	if (l >= r) return;
	
	int x = a[l + r + 1 >> 1], i = l - 1, j = r + 1;//防止r，l都为0而出错：l + r + 1 >> 1
	while (i < j)
	{
		do i ++; while (a[i] < x); //左指针，直到遇到不小于基准的数停
		do j --; while (a[j] > x); //右指针，直到遇到不大于基准的数停
		if (i < j) swap(a[i], a[j]); //若两指针未相遇则交换位置直到相遇
		
	}
	quick_sort(a, l, i-1); //j左边均为小于基准的数，进行递归
	quick_sort(a, i, r); //j右边均为大于基准的数，进行递归
}

int main()
{
	scanf("%d", &n);
	
	for (int i = 0;i < n;i ++) scanf("%d", &a[i]);
	
	quick_sort(a, 0, n - 1);
	
	for (int i = 0;i < n;i ++) printf("%d ", a[i]);
	
	return 0;
}