stl partition演算法有兩種寫法，哪種效率高？

partition分別對於forward_iterator和bidirectional_iterator採取兩種不同的寫法，兩種演算法都是O(N)但哪種效率更好？

雙向迭代器

template&
_BidirectionalIterator
__partition(_BidirectionalIterator __first, _BidirectionalIterator __last,
_Predicate __pred, bidirectional_iterator_tag)
{
while (true)
{
while (true)
if (__first == __last)
return __first;
else if (__pred(*__first))
++__first;
else
break;
--__last;
while (true)
if (__first == __last)
return __first;
else if (!bool(__pred(*__last)))
--__last;
else
break;
std::iter_swap(__first, __last);
++__first;
}
}


單向迭代器

template&
_ForwardIterator
__partition(_ForwardIterator __first, _ForwardIterator __last,
_Predicate __pred, forward_iterator_tag)
{
if (__first == __last)
return __first;

while (__pred(*__first))
if (++__first == __last)
return __first;

_ForwardIterator __next = __first;

while (++__next != __last)
if (__pred(*__next))
{
std::iter_swap(__first, __next);
++__first;
}

return __first;
}


---

這兩種演算法是有名字的。單向迭代器使用的是Lomuto partition，雙向的那個叫做Hoare partition。

兩種方法都是O(n)，但Hoare演算法常數小，少做三倍的交換，且在所有值返回的結果都相等的時候更高效。

但是兩者都不能避免快排退化（

---

因為所有的雙向迭代器都一定可以被當成單項迭代器，那麼既然他還給雙向迭代器寫了一份，那當然只能是因為作者認為雙向迭代器有更好的做法。

---

如果 bidirectional iterator 效率跟 forward iterator 的一樣 他就沒必要專門為 bidirectional iterator 特化一份，所以肯定是 bidirectional iterator 的快。時間複雜度相同不代表速度相同啊 那個其實不叫O（n）啊 其實叫θ（n）啊 這個式子是省掉了低階項和常數因子的 所以雖然都是 θ（n）常數因子不同就實際時間就不一樣呀！ 具體差多少的話就自己多測試幾次

---

我來回答一下。

你看得很仔細。這兩種劃分策略的漸進時間複雜度都是線性的，但前者(bi版本)的效率略高，常數更小。這其實也不難想到——bi版本做一次操作可以解決兩個元素（頭上一個，尾上一個），但fw版本交換一次只能解決一個元素。比較一下最壞情況：

bi版本最壞有3/2n次元素移動

fw版本最壞有3n次元素移動

所以bi版本更好一點。

參考資料：https://kluedo.ub.uni-kl.de/files/3463/wild-master-thesis.pdf

看其中的3.4.2 Implementation of the Partitioning Step

（這篇碩士論文對快速排序寫得很深入，可以當做排序愛好者的深度文獻）

---

推薦閱讀：