在 Quicksort 中，为什么分区步骤从低 - 1 和高 + 1 开始？

Question

考虑 Hoare 的分区方案...（来自 wikiepdia）

algorithm partition(A, lo, hi) is
    pivot := A[lo]
    i := lo – 1
    j := hi + 1
    loop forever
        do
            i := i + 1
        while A[i] < pivot

        do
            j := j – 1
        while A[j] > pivot

        if i >= j then
            return j

为什么最初是 i = lo - 1 而不是 lo 和 j = hi + 1 而不是 hi？这不包括之前已经在最终位置的支点吗？

我想首先了解这一点，因为我已经看到一些优化情况并非如此。

Answer 1

因为 do-while 循环中的第一步是

i := i +1

因此它与第一次迭代中的 lo 具有相同的值。之后算法检查是否 A[i] < pivot

与 j 和 hi 相同

也可以这样做：

i := lo
j := hi

但是循环必须是面向头部的：

while A[i] < pivot
    i := i +1
endWhile

Answer 2

因为使用do while先增加i，然后减少j。

所以我会很高兴，而 j 会很高兴。

如果要让i等于lo，j等于hi，可以参考here

Answer 3

（其他人已经解释了初始 left/right 指针在数组外部的原因是这个版本的算法首先做的是递增和递减，分别将这些索引带入范围。）

Isn't this including previous pivots which are already in the final position?

好吧，除了记录它之外，这个特殊的变体不会对枢轴值做任何事情。

一些（大多数？）变体实际上将选定的枢轴元素移动到最左边或最右边（当它还不是其中之一时），然后从剩余的分区逻辑中排除该槽，最后将其交换到将（中间位置）放在循环的末尾。

但是，这个特定的变体仅依赖于分区循环来完成它的工作，因此所选的枢轴元素可能会在数组中移动多次，但最终会在正确的区域结束。

在 Quicksort 中，为什么分区步骤从低 - 1 和高 + 1 开始？

In Quicksort why does the partitioning step start at low - 1 and high + 1?

algorithm

quicksort