首页 文章

快速排序3方式 - 当元素大于数据透视时,为什么循环索引不会递增?

提问于
浏览
0

我一直在寻找与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 回答

  • 1

    因为你应该再次检查 a[i] 元素(前 a[gt] ) - 它还不知道 - 该元素是小还是大

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

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

    留给我的元素已被检查为不大于枢轴 .

    如果我们用[lt]交换[i],我们知道a [i]很小并且必须继续,递增i .

    如果我们用[gt]交换[i],我们没有a [i]的新值,必须再次检查它

    附:请注意,链接的问题是关于具有两个透视值的3向分区,而Sedgewick算法用于具有一个枢轴的“荷兰旗”分区以及对于等于枢轴的值的特殊处理

相关问题