快速排序（acwing学习笔记）

基本思想

这是快速排序的一道模板题，主要思想是分治，通过在数组两边设置两个指针 l 和 r ， 然后设置一个 x ， x可以是l， 也可以是 (l + r) / 2, 也可以是r作为参照物。如果是由小到大排序，l 指针和 r 指针每次往后移动一位，当l > x 时, l 指针不动，当 r < x 时， r 不动， 此时 l 和 人交换位置，那么只要 x 左边的数是小于x的， x 右边的数是大于x的，往下递归，等到l >= r ,也就是，两个指针重和或穿插过去后，排序完成，程序结束。

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n;
void quick_sort(int q[], int l, int r)
{
	if(l >= r) return;	//排序结束
	//x可以取l，r， （l + r ) / 2
	//这里i和j要注意边界问题，i和j之所以要往两边移一位，是因为为了保证指针每次都是移动的，那么无论怎样，都要先往里移动一次
	int x = q[l], i = l - 1, j = r + 1;
	while(i < j)
	{
		//左边i指针往右移动，只要指针指向的数字是小于x的，否则停下
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		//等到两个指针都停下了，那么交换i和j指针，这样就能保证x左边小于x，x右边大于x
		if(i < j) swap(q[i], q[j]);
			
	}
	//把左右两边分开再次进行上面的操作，也就体现出来了分治思想。
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

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