泛型算法（十八）之划分算法

1、nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)：对序列重排，使得指定的位置出现的元素就是有序情况下应该在该位置出现的那个元素，且在指定位置之前的元素都小于指定位置元素，在指定位置之后的元素都大于指定位置元素。

    std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    //使把序列c中的元素随机打乱顺序
    std::random_shuffle(c.begin(), c.end());

    //对序列重排
    std::nth_element(c.begin(), c.begin() + 5, c.end());

    //输出
    for (auto var : c)
    {
        std::cout << var << ",";
    }
    //打印结果：0,1,2,3,4,5,6,7,8,9,

2、nth_element(RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp)：重载版本。

自己实现comp，向算法定制操作。

3、is_partitioned(InputIterator first, InputIterator last, UnaryPredicate pred)：C11版，判断序列中满足谓词pred的元素是否都在头部。

    std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    //判断小于5的元素是否都在序列头部
    bool i = std::is_partitioned(c.begin(), c.end(), [](int element){
        return element < 5;
    });
    //输出
    std::cout << (int)i;
    //打印结果：1,

4、partition(ForwardIterator first, ForwardIterator last, UnaryPredicate pred)：对序列重排，使得满足谓词pred的元素位于最前，返回值为指向不满足谓词pred的第一个元素的迭代器。

    std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    //把序列中的偶数放在序列最前
    std::partition(c.begin(), c.end(), [](int element){
        return element % 2 == 0;
    });
    //输出
    for (auto var : c)
    {
        std::cout << var << ",";
    }
    //打印结果：0,8,2,6,4,5,3,7,1,9,

5、stable_partition(BidirectionalIterator first, BidirectionalIterator last, UnaryPredicate pred)：对序列重排，使得满足谓词pred的元素在前，不满足谓词pred的元素在后，且两组元素内部的相对顺序不变。一般是用临时缓冲区实现本函数。

6、partition_copy(InputIterator first, InputIterator last, OutputIterator1 result_true, OutputIterator2 result_false, UnaryPredicate pred)：C11版，输入序列中满足谓词pred的元素复制到result_true，其他元素复制到result_false

    std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    std::vector<int> odd;
    std::vector<int> even;
    odd.resize(5);
    even.resize(5);
    //把c中的奇数放在odd，偶数放在even中
    std::partition_copy(c.begin(), c.end(), odd.begin(), even.begin(), [](int element){
        return element % 2 == 0;
    });
    //输出
    for (auto var : odd)
    {
        std::cout << var << ",";
    }
    std::cout << std::endl;

    for (auto var : even)
    {
        std::cout << var << ",";
    }
    //打印结果：0,2,4,6,8,
           　　1,3,5,7,9,

7、partition_point(ForwardIterator first, ForwardIterator last, UnaryPredicate pred)：C11版，输入队列已经是partition，折半查找到分界点。

    std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    //把c中的偶数放在最前
    std::partition(c.begin(), c.end(), [](int element){
        return element % 2 == 0;
    });
    //找到偶数，奇数分界点
    auto iter = std::partition_point(c.begin(), c.end(), [](int element){
        return element % 2 == 0;
    });
    //输出序列
    for (auto var : c)
    {
        std::cout << var << ",";
    }
    //打印结果：0,8,2,6,4,5,3,7,1,9,

    std::cout << std::endl;
    
    //分界点
    std::cout << *iter;
    //打印结果：5