快速排序代码模板
void quick_sort(int l, int r, int[] q){ // l为数组左端点，r为数组右端点， q为数组
if (l > = r) return ; //递归出口
int i = l, j = r;
int x = q[i + j >> 1]; // 用于比较的值
//
while(i < j){
while(q[j] >= x) --j;
while(q[i] < x) ++i;
if (i < j) swap(q[i], q[j]);
}
// 处理子问题
quick_sort(l, j - 1, q), quick_sort(j, r, q);
// 子问题合并，快排不需要
}
快速排序属于分治算法，分治算法基本分为三个步骤：
1. 分成子问题
2. 递归处理子问题
3. 子问题合并
接下来，有几个问题待分析：
如何证明: while loop 之后 可以使得q[l ... j -1] < x, q[j...r] >= x
使用循环不变式， 假设在某一轮循环中q[l ... j -1] < x, q[j...r] >= x，成立
那么在下一轮循环中：
循环体while(q[i] < x), 会使得q[l... i-1] < x , q[i] >= x；
同理，while(q[j] >= x)， 会使得q[j+1 ... r] >= x , q[j] < x；
此时，存在q[i] >= x，q[j] < x， 使用swap函数，可以更新i和j，下次while循环中，循环不变式依然成立。
边界分析：在分治问题中，最容易导致死循环的就是边界问题，例如分成0份和n份，此时会导致无限划分，无法跳出递归
将j作为划分点时， x不可被选取为q[r]， 将i作为划分点时， x不可被选取为q[l];
假设x = q[r]时，会存在quick_sort(l, j - 1, q), quick_sort(j, r, q)；
假设j的最小值为1，若j = 1，此时，对于[j .. r] 有，j <= r，此时，必然存在跳出递归，或者再次拆分
而对于[l..j - 1], l <= j - 1, 此时有q[j - 1] < x,对所有的l和j-1之间的数均成立，所以循环结束时，i = r, j = r;
会导致无法拆分后续内容 ，进入边界问题中
以上为我的一点思考。