3路分區算法

Question

3路分區將數組分割成3個子數組：元素< pivot，元素== pivot，元素> pivot。

我們可以使用E. Dijkstra的「荷蘭國旗問題」的知名解決方案要做到這一點，但Bentley and McIlroy提出另一個way（見＃22，「快三路劃分」）

不幸我不明白他們的算法如何更好（更快）。有人可以慢慢解釋嗎？

Answer 1

它平均使用較少的交換，至少在陣列中不會有太多不同的元素時。

「荷蘭標誌」算法使用每個元素不等於樞軸一個調劑，所以這是

n - multiplicity(pivot) 

互換。

另一種方法是將等於主元的元素首先交換到數組的末尾，然後將每個元素交換爲等於主元的兩次（一次到一端，最後到中間），然後交換a[i], a[j]和i < j和a[j] < pivot < a[i]，即

2*multiplicity(pivot) + count(bad_pairs) 

掉期。壞對的數量不能超過(n - multiplicity(pivot))/2，並且通常（隨機數組）較小，遠遠高於我的頭頂，平均而言我預計類似(n-multiplicity(pivot))/4或更少。因此，如果multiplicity(pivot) < n/5，替代品保證使用更少的掉期，並且如果我的估計是正確的，那麼如果multiplicity(pivot) < 3*n/11平均使用更少的掉期。因此，如果您知道數組中只有極少數（< = 5左右）不同元素，我認爲「荷蘭國旗」會更好，但通常情況下，替代方案將使用更少的交換，直到待分類的零件已變得相當小。