我一直在与 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--**);
如果有人能解释一下这个分区方案就太好了。
最佳答案
因为你应该再次检查 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 算法是针对具有一个主元的“荷兰国旗”分区和对等于主元的值进行特殊处理
关于java - 快速排序 3 种方式 - 为什么当元素大于主元时循环索引不递增？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40923347/