STL nth_element神器

这周在看kd-tree,苦于找中位数写起来太过麻烦，去观摩了一下其他大佬的代码，竟然还有nth_element这种东西。
http://www.cplusplus.com/reference/algorithm/nth_element/
nth_element(first,nth,last)

first，last 第一个和最后一个迭代器，也可以直接用数组的位置。
nth，要定位的第$n$ 个元素，能对它进行随机访问.

将第$n\_th$ 元素放到它该放的位置上，左边元素都小于它，右边元素都大于它.

测试代码

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define PI acos(-1)
#define fi first
#define se second
#define INF 0x3f3f3f3f
#define INF64 0x3f3f3f3f3f3f3f3f
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define ms(x,v) memset((x),(v),sizeof(x))
#define scint(x) scanf("%d",&x );
#define scf(x) scanf("%lf",&x );
#define eps 1e-8
#define dcmp(x) (fabs(x) < eps? 0:((x) <0?-1:1))
using namespace std;
typedef long long LL;
typedef long double DB;
typedef pair<int,int> Pair;
const int maxn = 2e3+10;
const int MAX_V= 500+10;
const int MOD = 998244353;
int main()
{

   int a[10];
   for(int i=0 ; i<10 ; ++i){
      a[i] = i;
   }
   random_shuffle(a,a+10);
   for(int i=0 ; i<10 ; ++i) std::cout << a[i] << ' ';std::cout  << '\n';
   nth_element(a,a+6,a+10);
   for(int i=0 ; i<10 ; ++i) std::cout << a[i] << ' ';std::cout  << '\n';
   return 0;
}

运行结果

分别对应 $4,5,6$ 的运行结果.

复杂度

期望复杂度$O(n)$,一个很号好的用途就是找中位数了……