快速排序3種方式 - 爲什麼元素大於樞軸時，循環索引不會增加？

我一直在尋找這個與3路快速排序有關的許多問題，但找不到答案/解釋（像這樣和類似的 - Quicksort with 3-way partition）。快速排序3種方式 - 爲什麼元素大於樞軸時，循環索引不會增加？

以下是來自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，右側的元素大於pivot。等於支點的元素應該在中間。我已經試過每一步詳細地編寫上面的代碼，但我無法理解爲什麼當元素大於主元時我不會增加。當元素小於主元時，它會遞增：

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

如果有人能解釋這種分區方案，那將會很棒。

來源

2016-12-02 Stacky

因爲你應該檢查a[i]元（原a[gt]）再次 - 它是未知的，但 - 這個元素是小還是大

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

看一些中間的情況：我並不比LT小，不大於gt。

要留給我的元素已被檢查爲不大於數據透視表。

如果我們用[lt]交換[i]，我們知道a [i]很小，必須繼續，遞增i。

如果我們換一個[i]和必須重新進行檢查

P.S.的[I]與[GT]，我們沒有新的價值請注意，鏈接的問題是關於三個分區與兩個主鍵值，而Sedgewick算法是爲'荷蘭國旗'分區與一個主軸和特殊處理值相等的樞軸點

來源

2016-12-02 01:41:50 MBo

謝謝，但要充分理解這一點（和對不起，不能這樣做）：爲什麼它的增量小於大小寫？ exch（a，lt ++，i ++）; – Stacky

已更新的答案。 ...... – MBo

「如果我們用[lt]交換[i]，我們知道a [i]很小，必須繼續，遞增i。」 - 好吧，我[i] **比pivot **小，必須繼續。「如果我們將[i]與[gt]交換，我們並不是[i]的新值，並且必須再次檢查它。」 - 不是[i]，即較老的a [gt] **> **樞紐，即爲什麼它正在交換？ – Stacky

快速排序3種方式 - 爲什麼元素大於樞軸時，循環索引不會增加？

回答

相關問題