课堂内容+个人思考，个人笔记，但是欢迎补充、批评、指正。
快速排序基于分治的思想
平均时间复杂度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）。
所以我无脑取中值。