partial_sort

例子:
找出10个随机数中最大的5个数字

#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <algorithm>

using namespace std;

int main()
{
    vector<int> values;
    std::srand(std::time(nullptr));

    // create 10 number which in [0, 100]
    for( int i = 0; i < 10; ++i )
    {
        values.push_back( int( 1.0 * rand() / RAND_MAX * 100+ 0.5 ) );
    }

    for( auto i: values )
    {
        cout << i << "\t";
    }
    cout << endl;

    // sort to get 5 greatest number
    partial_sort( values.begin(), values.begin() + 5, values.end(), [](int a, int b)->bool{ return a > b; } );

    for( auto i: values )
    {
        cout << i << "\t";
    }
    cout << endl;        
    return 0;
}

output:

44 73 61 3 86 79 72 53 75 17
86 79 75 73 72 3 44 53 61 17

nth_element

nth_element的特点:第n个(从begin()开始)位置出现的元素一定是排序后第n名。
在位置n之前的所有元素一定小于等于nth_element之后的所有元素。在位置n之前的所有元素不保证是排序好了的。
由此,该算法非常适合寻找“第几名”。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iostream>
using namespace std;

std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};

void Show()
{
    for( auto it: v )
    {
        cout << it << "\t";
    }
    cout << endl;
}

int main()
{
    std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
    std::cout << "The median is " << v[v.size()/2] << '\n';
    Show();

    std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());
    std::cout << "The second largest element is " << v[1] << '\n';
    Show();
}

输出:

The median is 5
2 3 3 4 5 6 6 7 9   
The second largest element is 7
9 7 6 6 5 4 3 3 2

partition

partition 可以帮助我们将满足某一条件的元素放在前面,返回的迭代器指向第一个不满足的元素。
但是元素的相对位置可能被破坏。

int main()
{
    std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
    std::cout << "Original vector:\n ";
    for(auto it : v) std::cout << it << ' ';

    auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});

    std::cout << "\nPartitioned vector:\n ";
    std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
    std::cout << " * ";
    std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
}

输出:

Original vector:
    0 1 2 3 4 5 6 7 8 9 
Partitioned vector:
    0 8 2 6 4 * 5 3 7 1 9

分类: C plus plus

发表评论

电子邮件地址不会被公开。 必填项已用*标注