AcWing 785. 快速排序算法的证明与边界分析

更新:

2022.12.10

增加分析 6 和分析7, 修整了格式

2023.4.25

调整结构, 修改细节

2023.5.24

增加 python 版代码

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

快排属于分治算法，分治算法都有三步：

while 循环结束后，q[l..j] = x

q[l..j] = x, q[j] = j

正常情况下，按照循环不变式，我们应该会觉得结果已经显然了

因为i >= j，q[l..i] = x

所以按照j来划分的话，q[l..j] = x是显然的

可是，最后一轮循环有点特殊，因为最后一轮循环的if语句一定不会执行

因为最后一轮循环一定满足 i >= j,不然不会跳出while循环的，所以if语句一定不执行

正确分析：

由于最后一轮的if语句一定不执行

所以，只能保证:

q[l..i-1] = x

q[j+1..r] >= x, q[j] = j

由q[l..i-1] = j(i-1 >= j-1) 和 q[j] x) 中不能用q[i] = x

假设q[l..r]全相等

则执行完do i++; while(q[i] = 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); }

python版

有数组 q, 左端点 l, 右端点r

确定划分边界 x

将 q 分为 =x 的两个小数组

$i$ 的含义: $i$ 之前的元素都 $\leq x$, 即 $q[l..i-1]$ $\leq x$

$j$ 的含义: $j$ 之后的元素都 $\geq x$, 即 $q[j+1..r]$ $\geq x$

结论: $while$ 循环结束后, $q[l..j]$ $\leq x,q[j+1..r]$ $\geq x$

简单不严谨证明:

$while$ 循环结束时, $i \geq j$

若 $i > j$ , 显然成立

若 $i = j$

$\because$ 最后一轮循环中两个 $do-while$ 循环条件都不成立

$\therefore$ $q[i] \geq x, q[j] \leq x$

$\therefore$ $q[i] = q[j] = x$

$\therefore$ 结论成立

递归处理两个小数组