Quick Sort

quick sort体现了分治的思想。
平均情况下快速排序的时间复杂度是Θ(nlgn)，最坏情况是n^2。
由于递归调用，快排的空间复杂度是Θ(lgn)。
1.确定分界点：
Q[l]: Always pick the first element as pivot.
Q[r]: Always pick the last element as pivot (implemented below)
Q[random]: Pick a random element as pivot.
Q[l+r/2]: Pick median as pivot.
2.调整区间（划重点，这个leetcode要考的）
区间长度不一定相等，使得第一个区间所有的数字都小于等于x，第二个区间都大于等于x。
快排的重点就是如何划分左右两端的区间。

暴力解：
建立额外数组a和b，扫描Q[l]到Q[r]，小于x放入a，大于x放入b。
时间复杂度O(n) ，扫描了两遍。
使用了额外的空间。

双指针做法可以不使用额外空间：
两个指针i与j在左右两端同时向中间走。
当i指向的数大于等于x，停下i，移动j。如果j指向的数小于等于x。i与j指向的数字都错位了，i和j继续再向中间走，直到i和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);
//swap 交换两个数
if (i < j) swap(q[i], q[j]);
}
//递归处理左右两端
quick_sort(q, l, j), quick_sort(q, j + 1, r);
}