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

Question

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

下面是 Robert Sedgewick 和 Kevin Wayne 的书 "Algorithms" 中的 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] 的新值并且必须再次检查它

P.S。请注意，链接的问题是关于具有两个枢轴值的 3 向分区，而 Sedgewick 算法是针对 'dutch flag' 具有一个枢轴的分区和对等于枢轴

的值的特殊处理

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

Quick sort 3 way - why loop index is not incremented when element is greater than pivot?

java

sorting

algorithm

pseudocode

quicksort