C++ STL nth_element 和 partial_so

说明

nth_element(first, nth, last)
nth_element是把第n个元素放在第n个位置，不保证前面区间和后面区间的元素顺序，但是前面区间的元素会"小于等于"后面区间的元素。(排序函数可自定义)

partial_sort(first, middle, last)
partial_sort是部分排序，对 [first, middle)内是顺序的，后面区间的顺序就不保证了

头文件

#include <algorithm>

nth_element 例子

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    std::vector<int> nums{ 6, 2, 7, 3, 1, 8, 5, 4 };

    std::cout << std::endl << "before nth_element() : " << std::endl;
    for (auto i : nums) {
        std::cout << i << "\t";
    }

    std::nth_element(nums.begin(), nums.begin() + 4, nums.end());

    std::cout << std::endl << "after nth_element() : " << std::endl;
    for (auto i : nums) {
        std::cout << i << "\t";
    }

    system("pause");
    return 0;
}

结果：

before nth_element() :
6       2       7       3       1       8       5       4
after nth_element() :
1       2       3       4       5       6       7       8

这是在vs上跑的，不知道为什么vs上nth_element的实现是把顺序全排了，导致结果是有序的，但是不能保证其他平台的实现是全排序的。
其实如果上面nth_element之后输出的是2 1 3 4 5 7 6 8更能表达函数的作用。

partial_sort 例子

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    std::vector<int> nums{ 6, 2, 7, 3, 1, 8, 5, 4 };

    std::cout << std::endl << "before partial_sort() : " << std::endl;
    for (auto i : nums) {
        std::cout << i << "\t";
    }

    std::partial_sort(nums.begin(), nums.begin() + 4, nums.end());

    std::cout << std::endl << "after partial_sort() : " << std::endl;
    for (auto i : nums) {
        std::cout << i << "\t";
    }

    system("pause");
    return 0;
}

结果：

before partial_sort() :
6       2       7       3       1       8       5       4
after partial_sort() :
1       2       3       4       7       8       6       5

可以发现对前4个元素进行了排序

参考

http://www.cplusplus.com/reference/algorithm/nth_element/
http://www.cplusplus.com/reference/algorithm/partial_sort/