快速排序不变式 具有循环不变式的 3 个条件

Question

在使用 Cormen、Leiserson、Rivest 和 Stein 所著的《算法导论》一书研究快速排序时，他们描述了为了证明正确性，循环的 3 个阶段（循环的初始化、维护和终止）必须保持不变式。

基于以下算法，我不理解下面的属性1和2：

这是我引用的算法：

有人可以帮助我了解情况吗

1）如果 $p \leq k \leq i$ 然后 $A[k] \leq x$

在算法中，例如， $p$ 是 $1$, 不会 $i$ 是 $0$....这如何成立，因为在 for 循环之前我们有 i = p-1

2）如果 $i + 1 \leq k \leq j - 1 $ 然后 $A[k] > x$

以算法为例，当我们第一次进入for循环，并且j = 1时，那么 $i$ 将会是 0....我不明白这是如何运作的。

谢谢

Answer 1

如果 $p \leq k \leq i$ 然后 $A[k] \leq x.$在算法中，例如， $p$ 是 $1$, 不会 $i$ 是 $0$....这如何成立，因为在 for 循环之前我们有 i = p-1

虽然，正如你所观察到的， $i$ 总是小于 $p$ 在循环开始时，它可能会变得更大，因为语句“$i=i+1$" 可以在循环中执行。一次 $i$ 已经增加了，至少 $k=p$, ， 我们有 $p\le k\le i$.

请注意，当 $p\le i$ 不成立，即当没有 $k$ 这样 $p\le k\le i$, ，条件“如果 $p \leq k \leq i$ 然后 $A[k] \leq x$" 自动保持。（回想一下，“如果为假，那么任何事情都可能发生”这个命题总是正确的。）为了证伪这个条件，我们必须找到一个实例 $(p,k,i)$ 这样 $p \leq k \leq i$ 但 $A[k]\gt x$.

您现在应该能够弄清楚第二个循环不变式的情况。

Answer 2

我现在没有心情跟踪代码，但请理解您以 A[r] =X 开头并以 A[i] =X 结尾

（枢轴，似乎被选为最后一个元素 $r$ 在给定的代码中，到达其正确位置，列表的其余部分被分区）

- 乍一看可能代码有些错误，then括号里的交换不需要，另一个交换应该是在then里面下注A[r] & A[j] $其他$