目的：速写明确，好改易懂

void QuickSort(int a[], int left, int right)
{
	if (left >= right)
		return;
	int i = left, j = right;
	int b = rand()%(right - left + 1); // 快排优化，加上这俩句能写o(nlogn)
	swap(left,left + b); // 实际考试用伪代码：a中随机选择一个数放入a[left]
	while (j > i)
	{
		while (j > i && a[j] >= a[left]) // 注意这里必须先右指针后左指针
			j--;
		while (j > i && a[i] <= a[left])
			i++;
		swap(a[i],a[j]);  //i和j相遇则与枢轴元素交换，否则a[i]与a[j]交换
	}
	swap(a[i],a[left]);
	QuickSort(a, left, i-1);
	QuickSort(a, j+1, right);
}

原理

拿数组最左边的元素作为枢轴元素(即用来作比较的那个元素)，然后把右指针 j 移动到一个比枢轴元素小的数上（为了确保右边的数都比枢轴元素大，即这个数的位置是不合适的要换到左边去），把左指针移到比枢轴元素大的数上（为了确保左边的数都比枢轴元素小，即这个数的位置是不合适的要换到左边去），然后交换这两个不合适的位置的值（交换a[ i ],a[ j ])。经过多轮交换，i与j必定相遇（即相等），最终除了枢轴元素（它始终在最左边）外，i的左边肯定比枢轴元素小，右边肯定比枢轴元素大，且i与j所指的数一定比枢轴小

模拟

时间复杂度与空间复杂度

时间复杂度：o(nlogn)
空间复杂度：o(nlogn) (注意不是o(1), 因为使用了堆栈）

附能跑通的代码：

#include<iostream>
using namespace std;
void QuickSort(int a[], int left, int right)
{
	if (left >= right)
		return;
	int i = left, j = right;
	int b = rand()%(right - left + 1);
	swap(a[left],a[left + b]);
	while (i < j)
	{
		while (j > i && a[j] >= a[left])
			j--;
		while (j > i && a[i] <= a[left])
			i++;
		swap(a[i],a[j]);  //i和j相遇则与枢轴元素交换，否则a[i]与a[j]交换
	}
	swap(a[i],a[left]);
	QuickSort(a, left, i-1);
	QuickSort(a, j+1, right);
}
int a[12000];
int main()
{
	int n;
	cin>>n; // 先输入有多少个元素
	for(int i = 0;i < n;i++)
	{
		cin>>a[i];
	}
	QuickSort(a,0,n-1);
	for(int i=0;i< n;i++){
		cout<<a[i]<<' ';
	}
}