【算法】第 n 小数 nth_element

stl 中取第 n 小数的算法 nth_element 的函数原型如下

算法说明：

1、功能：执行 nth_element 后，nth 所指位置的元素将是整个区间有序时在该处的元素。对 [first, nth) 中的任意迭代器 i 和 [nth, last) 中的任意迭代器 j，满足 !(*i > *j)。

2、要求：randomaccessiterator 必须满足 valueswappable。*first 的类型必须满足 moveconstructible 和 moveassignable。

3、复杂度：平均为线性。

源码如下：

其中的  和 在之前介绍过，这里不再列出它们的源码。

函数中的 first 和 last 可能改变，当 [first, last) 区间大于3时就一直划分，划分是采用三者取中的方式以缓解输入时的糟糕情况，每次划分后产生两段，若右段起点 cut <= nth，则再对右段划分，否则对左段划分。直到区间长度小于等于3时，索性对这个小区间进行插入排序，注意 nth 始终在 [first, last) 中。