#部分排序（std::nth_element）
定义于头文件<algorithm>中：
template< typename RandomIt >
void nth_element( RandomIt first, RandomIt nth, RandomIt last ); (1)template< typename randomIt, typename Compare >
void nth_element( RandomIt first, RandomIt nth, RandomIt last, Compare comp ); (2)nth_element是一个部分排序算法，它像这样重新排列区间[first, last)里的元素：
nth所指向的元素变成[first, last)排好序后该位置的元素。- 新的
nth之前的所有元素小于或等于nth之后的元素。
更一般地，nth_element部分地对区间[first, last)里的元素按升序排序，直至对于区间[first, nth)里的任何元素i和区间[nth, last)里的任何元素j，条件!(*j < *i)（版本2则为comp(*j, *i) == false）满足。nth位置的元素恰为若该区间全排序时第n小（或大）的元素。
nth可能为end迭代器，这种情况对函数无影响。
##参数
first, last —— 待排序的元素的区间
comp —— 比较函数，若第一个参数小于第二个则返回true。
比较函数必须使用下面的等效声明：
bool cmp(const Type1 &a, const Type2 &b);
比较函数不一定非得声明为const &，但是这个函数对象应该不能修改传递过来的参数。
类型Type1和Type2必须是能够解除引用操作和隐式互转的RandomIt类型。
类型约束
##返回值 无返回值。
##复杂度
平均时间复杂度为线性于std::distance(first, last)。
##注意
该算法通常是一个introselect算法，尽管也允许使用其他平均性能也不错的selection algorithms算法。
##例子
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
int main()
{
std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "The median is " << v[v.size()/2] << '\n';
std::nth_element(v.begin(), v.begin()+1, v.end(), std::greater<int>());
std::cout << "The second largest element is " << v[1] << '\n';
}输出为：
The median is 5
The second largest element is 7##另见
- partial_sort_copy 按一定顺序排出区间里的前N个元素（函数模板）
- stable_sort 对区间的元素进行排序，同时保持相等元素的先后顺序（函数模板）
- sort 递增排序，且不一定会保持相等元素的先后次序（函数模板）