杂写 - 002快速排序 - 《算法学习》

快排与我在408中学的略有差异，有很多细节问题，最头痛的是边界问题。
以下的第一个是个人认为最好懂得，附上。但是为什么取这几个参数，就涉及到了边界问题的证明了。

void quick_sort(int q[], int l, int r) {
    if (l >= r) return;
    int x = q[l + r >> 1], i = l - 1, j = 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);
}
作者：Diamondz
链接：https://www.acwing.com/solution/content/2089/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

证明

算法证明
算法证明使用算法导论里的循环不变式方法

快排模板(以j为分界)
快排属于分治算法，分治算法都有三步：

分成子问题
递归处理子问题
子问题合并 ```cpp 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); //第三步：子问题合并.快排这一步不需要操作，但归并排序的核心在这一步骤 }

<a name="26kbO"></a>
#### 待证问题
while循环结束后，`q[l..j] <= x`,`q[j+1..r] >= x`<br />注:`q[l..j] <= x`意为`q[l],q[l+1]...q[j-1],q[j]`的所有元素都`<= x`
<a name="VZ9bn"></a>
#### 证明
循环不变式：`q[l..i] <= x q[j..r] >= x`
1. 初始化
循环开始之前`i = l - 1, j = r + 1`<br />则`q[l..i],q[j..r]`为空，循环不变式显然成立
2. 保持
假设某轮循环开始前循环不变式成立，即`q[l..i] <= x, q[j..r] >= x`<br />执行循环体

do i++; while(q[i] < x); 会使得 q[l..i-1] <= x, q[i] >= x

do j—; while(q[j] > x); 会使得 q[j+1..r] >= x, q[j] <= x

if(i < j) swap(q[i], q[j]); 会使得 q[l..i] <= x, q[j..r] >= x

复制代码

所以，i和j更新之后，下一次循环开始之前，循环不变式依然成立<br />注意:由于使用do-while循环,所以`i`和`j`一定会!!!自增!!!,使得循环会继续下去,但是如果采用while循环(`i`和`j`的初始化做出对应的变更),`i`和`j`在特殊情况下不自增的话,循环就会卡死<br />例如:

while(q[i] < x) i++; while(q[j] > x) j—; 当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环复制代码


3. 终止<br />循环结束时，`i >= j`<br />正常情况下，按照循环不变式，我们应该会觉得结果已经显然了<br />因为`i >= j，q[l..i] <= x, q[j..r] >= x`<br />所以按照`j`来划分的话，`q[l..j] <= x, q[j+1..r] >= x`是显然的<br />可是，最后一轮循环有点特殊，因为**最后一轮循环的if语句一定不会执行**<br />因为最后一轮循环一定满足 i >= j,不然不会跳出while循环的，所以if语句一定不执行<br />**正确分析**：<br />由于最后一轮的if语句一定不执行<br />所以，只能保证`i >= j`和`q[l..i-1] <= x, q[i] >= x`和`q[j+1..r] >= x, q[j] <= x`<br />由`q[l..i-1] <= x，i >= j(i-1 >= j-1)` 和 `q[j] <= x` 可以得到 `q[l..j] <= x`<br />又因为`q[j+1..r] >= x`所以，`q[l..j] <= x,q[j+1..r] >= x`,**问题得证**<br />**总结**:只有最后一轮循环结束时，循环不变式不成立，其余的循环都是成立的 但最终要求的问题还是解决了<br />**注意**:循环结束时要记得检查是否存在数组越界/无限递归的情况<br />所以还需要证明 `j` 最终的取值范围是`[l..r-1]`(即不存在`n`划分成`0`和`n`的无限递归情况),分析过程在分析`5`<br />
<a name="OdFG2"></a>
### 边界情况分析
<a name="3XzNM"></a>
#### 分析
快排属于**分治算法**，最怕的就是 `n分成0和n，或 n分成n和0`,这会造成**无限划分**

1. 以`j`为划分时，`x`不能选`q[r]` (若以`i`为划分,则`x`不能选`q[l]`)

假设 `x = q[r]`<br />关键句子`quick_sort(q, l, j), quick_sort(q, j + 1, r);`<br />由于`j`的最小值是`l`,所以`q[j+1..r]`不会造成无限划分<br />但`q[l..j]`(即quick_sort(q, l, j))却可能造成无限划分，因为j可能为r<br />举例来说，若`x`选为`q[r]`，数组中`q[l..r-1] < x`,<br />那么这一轮循环结束时`i = r, j = r`，显然会造成无限划分

2. `do i++; while(q[i] < x)`和`do j--; while(q[j] > x)`不能用`q[i] <= x` 和 `q[j] >= x`<br />假设`q[l..r]`全相等<br />则执行完`do i++; while(q[i] <= x);`之后，`i`会自增到`r+1`<br />然后继续执行`q[i] <= x` 判断条件，造成数组下标越界(但这貌似不会报错)<br />并且如果之后的`q[i] <= x (此时i > r)` 条件也不幸成立，<br />就会造成一直循环下去(亲身实验)，造成内存超限`(Memory Limit Exceeded)`<br />
2. `if(i < j) swap(q[i], q[j])`能否使用 `i <= j`<br />可以使用`if(i <= j) swap(q[i], q[j]);`<br />因为 `i = j` 时，交换一下`q[i],q[j]` 无影响，因为马上就会跳出循环了<br />
2. 最后一句能否改用`quick_sort(q, l, j-1), quick_sort(q, j, r)`作为划分(用`i`做划分时也是同样的道理,)<br />不能<br />根据之前的证明，最后一轮循环可以得到这些结论<br />`j <= i` 和 `q[l..i-1] <= x, q[i] >= x` 和 `q[j+1..r] >= x, q[j] <= x`<br />所以，`q[l..j-1] <= x` 是显然成立的，<br />但`quick_sort(q, j, r)`中的`q[j]` 却是 `q[j] <= x`，这不符合快排的要求<br />另外一点，注意`quick_sort(q, l, j-1), quick_sort(q, j, r)`可能会造成无线划分<br />当`x`选为`q[l]`时会造成无限划分，报错为(MLE),<br />如果手动改为 `x = q[r]`,可以避免无限划分<br />但是上面所说的`q[j] <= x` 的问题依然不能解决，这会造成 `WA (Wrong Answer)`<br />
2. `j`的取值范围为`[l..r-1]`<br />

证明:<br />假设 `j` 最终的值为 `r` ,说明只有一轮循环(两轮的话 `j` 至少会自减两次)<br />说明`q[r] <= x` (因为要跳出`do-while`循环)<br />说明 `i >= r `(while循环的结束条件), `i` 为 `r` 或 `r + 1`(必不可能成立)<br />说明 `i` 自增到了 `r` , 说明 `q[r] >= x 和 q[l..r-1] < x`,<br />得出 `q[r] = x 和 q[l..r-1] < x` 的结论,但这与 `x = q[l + r >> 1]`**矛盾**<br />**反证法**得出 `j < r`<br />假设 `j` 可能小于 `l` 说明 `q[l..r] > x` ,**矛盾**<br />**反证法**得出 `j >= l`<br />所以 `j`的取值范围为`[l..r-1]`,不会造成无限划分和数组越界

6. `while`循环的结束条件能不能改成 `i <= j`

顺带一提用`i`做划分时的模板

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 >> 1];//注意是向上取整,因为向下取整可能使得x取到q[l] 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, i - 1), quick_sort(q, i, r);//不用q[l..i],q[i+1..r]划分的道理和分析4中j的情况一样 } ```

作者：clear-life
链接：https://juejin.cn/post/6854573212832022536/
来源：掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。