java - 快速排序 3 种方式 - 为什么当元素大于主元时循环索引不递增？

Question

我一直在与 3 向快速排序相关的许多问题中搜索这个，但找不到答案/解释(像这样和类似的 - Quicksort with 3-way partition)。

以下是 Robert Sedgewick 和 Kevin Wayne 在“算法”一书中的 3 种快速排序代码。

private static void sort(Comparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int lt = lo, gt = hi;
    Comparable v = a[lo];
    int i = lo;
    while (i <= gt) {
        int cmp = a[i].compareTo(v);
        if      (cmp < 0) exch(a, lt++, i++);
        else if (cmp > 0) exch(a, i, gt--);
        else              i++;
    }

    sort(a, lo, lt-1);
    sort(a, gt+1, hi);
}

分区后，左边的元素应该小于枢轴，右边的元素应该大于枢轴。等于 pivot 的元素应该一起在中间。我已经尝试详细地每一步编写上面的代码，但是我无法理解为什么当元素大于枢轴时 i 没有递增。当元素小于枢轴时，它会递增:

else if (cmp > 0) exch(a, **i, gt--**);

如果有人能解释一下这个分区方案就太好了。

Answer 1

因为你应该再次检查 a[i] 元素(以前的 a[gt])——它是未知的——那个元素是小的还是大的

*  *  *  *  *  *  *  *
      ^     ^     ^
      lt    i     gt

看一些中间情况:i 不小于 lt 且不大于 gt。

留给 i 的元素已经被检查为不大于 pivot。

如果我们将 a[i] 与 a[lt] 交换，我们知道 a[i] 很小并且必须继续递增 i。

如果我们将 a[i] 与 a[gt] 交换，我们不会得到 a[i] 的新值并且必须再次检查它

附言请注意，链接的问题是关于具有两个主元值的三向分区，而 Sedgewick 算法是针对具有一个主元的“荷兰国旗”分区和对等于主元的值进行特殊处理