Quick Sort（快排）-- 分治

基本思路：

1. 确定分界点:q[l],q[(l+r)/2],q[r] ；
2. 调整区间；
3. 递归处理左右两段。

对于步骤2，有两种方法：

法1：暴力调整

1. 创建两个数组a[],b[]；
2. 扫描q[l~r],将<=x的数放进a[],将>=x的数放进b[]；
3. 先将a[]放进q[],再将b[]放进q[]。

法2：优美调整

1. 创建i（左）,j（右） 指针，i负责查找>=x的数，j负责查找<=x的数，两指针同时向中间移动；
2. 当i,j指针找到各自满足条件的值时，进行swap操作，然后向中间移动一位；
3. 重复上一步骤直至i,j相遇或穿过，此时区间被成功划分，即i的左边数满足<=x,j的右边数满足>=x.

C++代码实现：

void quick_sort(int q[], int l, int r)
{
	if(l >= r ) return;//递归出口
	int x = q[l], i = l - 1, j = r + 1;
	while(i < j)
	{
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j) swap(q[i], q[j]);	
	}

	quick_sort(q, l, j);//若使用i-1作为边界，则上面的x初始值不能使用l，否则会出现边界问题。（用1 2排序说明）
	quick_sort(q, j+1, r);
}

时间复杂度：O(nlogn)(最优情况下)。

快速排序优化：三数取中法选取枢轴。