课堂内容+个人思考，个人笔记，但是欢迎补充、批评、指正。
快速排序基于分治的思想
平均时间复杂度O（nlogn）
已知数组q[]
步骤：
1、确定分界点（x）：
（1）首元素q[l]; （2）尾元素q[r]; （3）中值q[(l+r)/2]; (4)随机;
2、调整区间
将区间通过x值划分为两部分（长度不一定相等），使得第一个区间所有数均小于等于x。第二个区间所有数均大于等于x。
注：若某数等于x，在左在右均可。
3、递归处理左右两端
左右重复步骤2。
方法（调整区间）：
暴力做法：
优美做法：
利用两个指针i，j。
1、i从首位向右扫描，数据<x时，i继续，数据>=x时停止；
2、j从末位向左扫描，数据>x时，j继续，数据<=x时停止；
3、交换i，j的值；
4、重复1~3，直到i、j相遇（穿过）。
注：数据并没有被抽离数组，分界点仍在数据中被排序；
若i/j仅一者停止，那么j/i会一直移动到i/j，此时左右区间满足条件。
有很多边界问题，最好背过模版。
写过几次就错了几次。
模板：
void quick_sort(int q[], int l, int r)
{
if (l >= r) return;//区间无数据（1/0个）时，结束
int i = l - 1, j = r + 1, x = q[l + r >> 1];
/*因为循环体i、j先++、--了一次*/
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);//迭代左右两区间
}
//说实话，这代码真好看。
对于最后迭代的部分取i还是取j：
取i是x不取左边界（l），取j时x不取右边界（r）。
所以我无脑取中值。