Loading... ### 算法证明 算法证明使用**算法导论** 里的**循环不变式** 方法 #### 快排模板(以j为分界) 快排属于分治算法,分治算法都有三步: 1. 分成子问题 2. 递归处理子问题 3. 子问题合并 ```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); //第三步:子问题合并.快排这一步不需要操作,但归并排序的核心在这一步骤 } ``` #### 待证问题 while循环结束后,`q[l..j] <= x`,`q[j+1..r] >= x` 注:`q[l..j] <= x`意为`q[l],q[l+1]...q[j-1],q[j]`的所有元素都`<= x` #### 证明 循环不变式:`q[l..i] <= x q[j..r] >= x` 1. 初始化 循环开始之前`i = l - 1, j = r + 1` 则`q[l..i],q[j..r]`为空,循环不变式显然成立 2. 保持 假设某轮循环开始前循环不变式成立,即`q[l..i] <= x, q[j..r] >= x` 执行循环体 ```cpp 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更新之后,下一次循环开始之前,循环不变式依然成立 注意:由于使用do-while循环,所以`i`和`j`一定会!!!自增!!!,使得循环会继续下去,但是如果采用while循环(`i`和`j`的初始化做出对应的变更),`i`和`j`在特殊情况下不自增的话,循环就会卡死 例如: ```cpp while(q[i] < x) i++; while(q[j] > x) j--; 当q[i]和q[j]都为 x 时, i 和 j 都不会更新,导致 while 陷入死循环 ``` 3. 终止 循环结束时,`i >= j` 正常情况下,按照循环不变式,我们应该会觉得结果已经显然了 因为`i >= j,q[l..i] <= x, q[j..r] >= x` 所以按照`j`来划分的话,`q[l..j] <= x, q[j+1..r] >= x`是显然的 可是,最后一轮循环有点特殊,因为**最后一轮循环的if语句一定不会执行** 因为最后一轮循环一定满足 i >= j,不然不会跳出while循环的,所以if语句一定不执行 **正确分析** : 由于最后一轮的if语句一定不执行 所以,只能保证`i >= j`和`q[l..i-1] <= x, q[i] >= x`和`q[j+1..r] >= x, q[j] <= x` 由`q[l..i-1] <= x,i >= j(i-1 >= j-1)` 和 `q[j] <= x` 可以得到 `q[l..j] <= x` 又因为`q[j+1..r] >= x` 所以,`q[l..j] <= x,q[j+1..r] >= x`,**问题得证** **总结** :只有最后一轮循环结束时,循环不变式不成立,其余的循环都是成立的 但最终要求的问题还是解决了 **注意** :循环结束时要记得检查是否存在数组越界/无限递归的情况 所以还需要证明 `j` 最终的取值范围是`[l..r-1]`(即不存在`n`划分成`0`和`n`的无限递归情况),分析过程在分析`5` ### 边界情况分析 #### 分析 快排属于**分治算法** ,最怕的就是 `n分成0和n,或 n分成n和0`,这会造成**无限划分** 1. 以`j`为划分时,`x`不能选`q[r]` (若以`i`为划分,则`x`不能选`q[l]`) 假设 `x = q[r]` 关键句子`quick_sort(q, l, j), quick_sort(q, j + 1, r);` 由于`j`的最小值是`l`,所以`q[j+1..r]`不会造成无限划分 但`q[l..j]`(即quick_sort(q, l, j))却可能造成无限划分,因为j可能为r 举例来说,若`x`选为`q[r]`,数组中`q[l..r-1] < x`, 那么这一轮循环结束时`i = r, j = r`,显然会造成无限划分 2. `do i++; while(q[i] < x)`和`do j--; while(q[j] > x)`不能用`q[i] <= x` 和 `q[j] >= x` 假设`q[l..r]`全相等 则执行完`do i++; while(q[i] <= x);`之后,`i`会自增到`r+1` 然后继续执行`q[i] <= x` 判断条件,造成数组下标越界(但这貌似不会报错) 并且如果之后的`q[i] <= x (此时i > r)` 条件也不幸成立, 就会造成一直循环下去(亲身实验),造成内存超限`(Memory Limit Exceeded)` 3. `if(i < j) swap(q[i], q[j])`能否使用 `i <= j` 可以使用`if(i <= j) swap(q[i], q[j]);` 因为 `i = j` 时,交换一下`q[i],q[j]` 无影响,因为马上就会跳出循环了 4. 最后一句能否改用`quick_sort(q, l, j-1), quick_sort(q, j, r)`作为划分(用`i`做划分时也是同样的道理,) 不能 根据之前的证明,最后一轮循环可以得到这些结论 `j <= i` 和 `q[l..i-1] <= x, q[i] >= x` 和 `q[j+1..r] >= x, q[j] <= x` 所以,`q[l..j-1] <= x` 是显然成立的, 但`quick_sort(q, j, r)`中的`q[j]` 却是 `q[j] <= x`,这不符合快排的要求 另外一点,注意`quick_sort(q, l, j-1), quick_sort(q, j, r)`可能会造成无线划分 当`x`选为`q[l]`时会造成无限划分,报错为(MLE), 如果手动改为 `x = q[r]`,可以避免无限划分 但是上面所说的`q[j] <= x` 的问题依然不能解决,这会造成 `WA (Wrong Answer)` 5. `j`的取值范围为`[l..r-1]` 证明: 假设 `j` 最终的值为 `r` ,说明只有一轮循环(两轮的话 `j` 至少会自减两次) 说明`q[r] <= x` (因为要跳出`do-while`循环) 说明 `i >= r `(while循环的结束条件), `i` 为 `r` 或 `r + 1`(必不可能成立) 说明 `i` 自增到了 `r` , 说明 `q[r] >= x 和 q[l..r-1] < x`, 得出 `q[r] = x 和 q[l..r-1] < x` 的结论,但这与 `x = q[l + r >> 1]`**矛盾** **反证法** 得出 `j < r` 假设 `j` 可能小于 `l` 说明 `q[l..r] > x` ,**矛盾** **反证法** 得出 `j >= l` 所以 `j`的取值范围为`[l..r-1]`,不会造成无限划分和数组越界 6. `while`循环的结束条件能不能改成`i <= j` 顺带一提用`i`做划分时的模板 ```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 >> 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的情况一样 } ``` <div class="tip inlineBlock share"> 作者:醉生梦死 链接:https://www.acwing.com/solution/content/16777/ 来源:AcWing </div> 最后修改:2021 年 12 月 06 日 © 转载自他站 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏