STL | nth_element 的使用

nth_element：

• 头文件: <algorithm>

• 对给定范围内的元素进行重新布置。位置的元素放置的值就是把所有不大于的值放到的前面，把所有不小于的值放到后面，对给定范围内的元素"排序"。

参数：

• first、last
  随机访问迭代器，指定了需要重新"排序"的范围，包括first，但不包括last。

• nth
  随机访问迭代器，指向范围[first,last)内的一个位置，这个位置将放置排序后应该放于此位置的元素。

• compare
  二元函数， 返回bool值。 表明是否第一个参数应该排序到第二个参数的前面。此函数不应该修改参数值，可以是一个函数指针或函数对象。

返回值：

无

• 简单的说，nth_element算法仅排序数组下标为的元素（数组下标从0开始）。

• 如 元素区间，排序后 就是第大的元素（数组下标从0开始）。

• 要注意的是，区间 和 内的大小顺序还不一定（不能确定是否有序），只能确定是第大的元素。

• 当然 肯定是不大于 的。

简单测试代码如下：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int main()
{
    int nth=7;//数组下标：nth>=0 && nth<len
    int iarray[]={5,6,15,89,7,20,1,3,52,63,12,64,47};
    int len=sizeof(iarray)/sizeof(int);
    cout<<"LEN:"<<len<<endl;
    cout<<"Before:\n";
    for(int i=0;i<len;i++)cout<<iarray[i]<<" ";
    cout<<endl;
    nth_element(iarray,iarray+nth,iarray+len);// 排序第 8个元素(nth+1) 
    cout<<"\nAfter:\n";
    for(int i=0;i<len;i++)cout<<iarray[i]<<" ";
    cout<<endl;
    cout<<"7-th:"<<iarray[nth]<<endl;// 输出数组下标为 7的元素（也就是第 8个元素） 
}

要注意的是，此函数只是将第nth大的元素排好了位置，但并没有返回值。所以要知道第nth+1大 的元素 还得自己输出数组下标为nth 的元素，即cout<<iarray[nth]<<endl;。

写在最后：

参考资料：

• 博客：C/C++中nth_element函数
• 博客：C++ STL nth_element原理与应用
• 博客：C++ nth_element(STL nth_element)排序算法详解

学无止境，奋斗不止。