STL 源代码剖析 算法 stl_algo.h -- partition

partition

------------------------------------------------------------------------

描写叙述：partition 会将区间[first,last) 中的元素又一次排列。全部被一元条件运算 pred 判定为 true 的元素，都会被放在区间的前段，

被判定为 false 的元素，都会被放在区间的后段。

partition 不稳定，不保证 partition 后元素保留在原始相对位置。 stable_partition 稳定

思路：

1.first往下查找，遇到"符合移动条件"(pred不成立)的就停下来

2.last往上查找，遇到"符合移动条件"(pred成立)的就停下来

3.交换 *first 和 *last, ++first, --last

复杂度：O(n)

源代码：

演示样例：

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/5178345.html，如需转载请自行联系原作者