我一直在寻找与3 way quicksort相关的许多问题,但找不到答案/解释(像这样和类似的 - 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时,它会递增:
else if (cmp > 0) exch(a, **i, gt--**);
如果有人可以解释这个分区方案,那就太棒了 .
1 回答
因为你应该再次检查
a[i]
元素(前a[gt]
) - 它还不知道 - 该元素是小还是大看一些中间情况:i不小于lt且不大于gt .
留给我的元素已被检查为不大于枢轴 .
如果我们用[lt]交换[i],我们知道a [i]很小并且必须继续,递增i .
如果我们用[gt]交换[i],我们没有a [i]的新值,必须再次检查它
附:请注意,链接的问题是关于具有两个透视值的3向分区,而Sedgewick算法用于具有一个枢轴的“荷兰旗”分区以及对于等于枢轴的值的特殊处理