本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie
partition
------------------------------------------------------------------------描写叙述：partition 会将区间[first,last) 中的元素又一次排列。全部被一元条件运算 pred 判定为 true 的元素，都会被放在区间的前段，
被判定为 false 的元素，都会被放在区间的后段。
partition 不稳定，不保证 partition 后元素保留在原始相对位置。 stable_partition 稳定
思路：
1.first往下查找，遇到"符合移动条件"(pred不成立)的就停下来
2.last往上查找，遇到"符合移动条件"(pred成立)的就停下来
3.交换 *first 和 *last, ++first, --last
复杂度：O(n)
源代码：
//全部被 pred 判定为 true 的元素，都被放到前段
//被 pred 判定为 false 的元素，都被放到后段
//不保证保留相对位置
template <class BidirectionalIterator, class Predicate>
BidirectionalIterator partition(BidirectionalIterator first,
BidirectionalIterator last, Predicate pred) {
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 (!pred(*last))
--last;
else
break;
iter_swap(first, last);
++first;
}
}
演示样例：
int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
const int N = sizeof(A)/sizeof(int);
partition(A, A + N,
compose1(bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)));
copy(A, A + N, ostream_iterator<int>(cout, " "));
// The output is "10 2 8 4 6 5 7 3 9 1".
本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5178345.html，如需转载请自行联系原作者
