在O（N）时间内使用布尔谓词函数对向量进行排序

Question

例如，假设我想对向量{1,2,3,4,5}进行排序，在左侧放置偶数，在右侧放置奇数。我可以设计一个在O（N）时间内执行此操作的算法（如下所示）。我的问题是，是否存在这样的东西的现有STL算法？

My (not very generic or pretty) solution

#include <iostream>
#include <vector>

/**
 Sort a vector of integers according to a boolean predicate function

 Reorders the elements of x such that elements satisfying some condition
 (i.e. f(x) = true) are arranged to the left and elements not satisfying the
 condition (f(x) = false) are arranged to the right
 (Note that this sort method is unstable)

 @param x vector of integers
 */
void sort_binary(std::vector<int>& x, bool (*func)(int)){
    // Strategy:
    // Simultaneously iterate over x from the left and right ends towards
    // the middle. When one finds {..., false, ..., ..., true, ....},
    // swap those elements

    std::vector<int>::iterator it1 = x.begin();
    std::vector<int>::iterator it2 = x.end();
    int temp;

    while(it1 != it2){
        while(func(*it1) && it1 < it2){
            ++it1;
        }
        while(!func(*it2) && it1 < it2){
            --it2;
        }
        if(it1 != it2){
            // Swap elements
            temp = *it1;
            *it1 = *it2;
            *it2 = temp;
        }
    }
}

int main() {
    // Sort a vector of ints so that even numbers are on the
    // left and odd numbers are on the right
    std::vector<int> foo {1, 2, 3, 4, 5};
    sort_binary(foo, [](int x) { return x % 2 == 0; } );
    for(auto &x : foo) std::cout << x << " ";
}

Answer 1

你可以使用std::partition()

重新排序[first，last]范围内的元素，使谓词p返回true的所有元素都位于谓词p返回false的元素之前。不保留元素的相对顺序。

复杂：

确切地说是谓词的N个应用程序。如果ForwardIt满足LegacyBidirectionalIterator的要求，则最多N / 2次交换，否则最多N次交换。

std::partition( foo.begin(), foo.end(), [](int x) { return x % 2 == 0; } );

live example

如果你想保留元素的顺序，你可以使用std::stable_partition()