C++_nth_element

转自：https://blog.csdn.net/sugarbliss/article/details/88050145

C++的STL库中的nth_element()方法，默认是求区间第k小的（划重点）。

举个栗子求第3小，对于 a[9]={4,7,6,9,1,8,2,3,5};nth_element(a,a+2,a+9)，将下标为2，也就是第3个数放在正确的位置，求的是第3小的数a[2]。（下标从零开始）nth_element(a,a+k,a+n)，函数只是把下标为k的元素放在了正确位置，对其它元素并没有排序，当然k左边元素都小于等于它，右边元素都大于等于它，所以可以利用这个函数快速定位某个元素。

那求第k大时呢？

我们可以转化成求第n-k+1小，此时下标应该是n - k。nth_element(a,a+n-k,a+n)，将下标为n-k，也就是第n-k+1个数放在正确的位置，求的是第k大的数a[n-k]。当然也可以把要处理的序列全变成负值，那样求得第k小就是第k大了。

注意这个方法并不保证k位置前面和后面部分各自有序，只是k位置存放第k小。

时间复杂度为O(n)

C++_nth_element

原文：https://www.cnblogs.com/fresh-coder/p/14321630.html