快速排序

1. 基本思想

先分完，再递归两边

流程：

确定分界点
调整区间（最重要且最难的部分）
递归处理左右两段

2. 第二步调整区间的方法

2.1 暴力做法

平均时间复杂度仍为o(n)

优点：思想简单
缺点：耗时为2n，不够快捷不够优美

2.2 快排

最左端、最右端分别确定一个指针i、j（目标：指针i左边的值全都小于等于分界点，指针j右边的值全都大于等于分界点）
指针i,j分别往中间走；当i遇到一个大于等于分界点的点，则停下；当j遇到一个小于等于分界点的点，则停下；
当i,j都停下后，交换双方互相所指的值，然后继续往中间走，直至相遇。

代码图例如下：

2	5	1	9	2	3
假定中间值取末尾值3
则：
2(i)	5	1	9	2	3(j)	
2	5(i)	1	9	2	3(j)	//3<=3，j不动
2	3(i)	1	9	2	5(j)	//交换i、j所指的值
2	3	1(i)	9	2(j)	5	
2	3	1	9(i)	2(j)	5	//2<=3，j不动
2	3	1	2(i)	9(j)	5	//交换i、j所指的值
//则现在i左边的值全都小于等于3，j右边的值全都大于等于3
//再分别对左右两边递归排序

代码如下:

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + 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), quick_sort(q, j + 1, r);
}