极客笔记C++ 算法 nth_element()函数
C++算法 nth_element() 函数用于将第一个元素到第n个元素之间的元素按照升序排序，而第n个元素到最后一个元素之间的元素不排序。但是，在第一个元素到第n个元素之间的元素中，没有一个元素比第n个元素到最后一个元素之间的元素小。
元素的比较使用 < 运算符进行，而第二个版本使用 comp 。
语法
default (1) template <class RandomAccessIterator>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last);
custom (2) template <class RandomAccessIterator, class Compare>
void nth_element (RandomAccessIterator first, RandomAccessIterator nth,
RandomAccessIterator last, Compare comp);
参数
first : 一个指向要使用范围中第一个元素的随机访问迭代器。
last : 一个指向要使用范围中最后一个元素之后的位置的随机访问迭代器。
comp : 一个用户定义的二进制谓词函数，接受两个参数，并返回true，如果两个参数是有序的，则返回false。它遵循严格的弱排序以对元素进行排序。
nth : 一个随机访问迭代器，表示范围[first, last)中将包含排序后元素的位置。
返回值
无
复杂度
平均情况下，复杂度与first和last之间的距离成线性关系：比较元素并可能交换它们，直到元素正确重新排列。
数据竞争
范围[first, last)中的对象将被更改。
异常
如果元素比较、元素交换或迭代器上的操作引发异常，则此函数会引发异常。
注意：无效的参数会导致未定义的行为。
示例1
让我们看一个简单的示例来演示nth_element()的用法：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(vector<int> ar)
{
for(auto x : ar) cout << x << " ";
cout << endl;
}
int main()
{
vector<int> ar = {1, 3, 6, 1, 2, 4, 7, 0};
cout<<"Before: ";
// will print 1 3 6 1 2 4 7 0
print(ar);
// mid = 5th element (ar.begin() + 4)
auto mid = ar.begin() + distance(ar.begin(), ar.end()) / 2;
// lets nth_element ar to mid
nth_element(ar.begin(), mid, ar.end());
cout<<"\nAfter: ";
// will print 2 0 1 1 3 4 7 6
// mid points to element 3
print(ar);
return 0;
}
输出：
Before: 1 3 6 1 2 4 7 0
After: 2 0 1 1 3 4 7 6
示例2
让我们看一个更简单的示例：
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
cout<<"Elements are: ";
for (vector<int>::iterator it=v.begin(); it!=v.end(); ++it)
cout << ' ' << *it;
cout << '\n';
nth_element(v.begin(), v.begin() + v.size()/2, v.end());
cout << "The median is " << v[v.size()/2] << '\n';
nth_element(v.begin(), v.begin()+1, v.end(), greater<int>());
cout << "The second largest element is " << v[1] << '\n';
return 0;
}
输出：
Elements are: 5 6 4 3 2 6 7 9 3
The median is 5
The second largest element is 7
示例3
让我们看另一个简单的示例：
#include <iostream> // std::cout
#include <algorithm> // std::nth_element, std::random_shuffle
#include <vector> // std::vector
using namespace std;
bool myfunction (int i,int j) { return (i<j); }
int main () {
vector<int> myvector;
// set some values:
for (int i=1; i<10; i++) myvector.push_back(i); // 1 2 3 4 5 6 7 8 9
random_shuffle (myvector.begin(), myvector.end());
// using default comparison (operator <):
nth_element (myvector.begin(), myvector.begin()+5, myvector.end());
// using function as comp
nth_element (myvector.begin(), myvector.begin()+5, myvector.end(),myfunction);
// print out content:
cout << "myvector contains:";
for (vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it)
cout << ' ' << *it;
cout << '\n';
return 0;
}
输出:
myvector contains: 5 2 3 1 4 6 7 8 9
示例4
让我们看另一个简单的示例：
#include <vector>
#include <algorithm>
#include <functional> // For greater<int>( )
#include <iostream>
// Return whether first element is greater than the second
bool UDgreater ( int elem1, int elem2 ) {
return elem1 > elem2;
}
int main() {
using namespace std;
vector <int> v1;
vector <int>::iterator Iter1;
int i;
for ( i = 0 ; i <= 5 ; i++ )
v1.push_back( 3 * i );
int ii;
for ( ii = 0 ; ii <= 5 ; ii++ )
v1.push_back( 3 * ii + 1 );
int iii;
for ( iii = 0 ; iii <= 5 ; iii++ )
v1.push_back( 3 * iii +2 );
cout << "Original vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
nth_element(v1.begin( ), v1.begin( ) + 3, v1.end( ) );
cout << "Position 3 partitioned vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// To sort in descending order, specify binary predicate
nth_element( v1.begin( ), v1.begin( ) + 4, v1.end( ),
greater<int>( ) );
cout << "Position 4 partitioned (greater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
random_shuffle( v1.begin( ), v1.end( ) );
cout << "Shuffled vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
// A user-defined (UD) binary predicate can also be used
nth_element( v1.begin( ), v1.begin( ) + 5, v1.end( ), UDgreater );
cout << "Position 5 partitioned (UDgreater) vector:\n v1 = ( " ;
for ( Iter1 = v1.begin( ) ; Iter1 != v1.end( ) ; Iter1++ )
cout << *Iter1 << " ";
cout << ")" << endl;
return 0;
}
输出：
Original vector:
v1 = ( 0 3 6 9 12 15 1 4 7 10 13 16 2 5 8 11 14 17 )
Position 3 partitioned vector:
v1 = ( 1 0 2 3 8 5 9 4 7 6 10 16 13 15 12 11 14 17 )
Position 4 partitioned (greater) vector:
v1 = ( 16 17 14 15 13 12 11 9 7 8 10 6 1 4 5 3 2 0 )
Shuffled vector:
v1 = ( 13 10 6 3 5 2 0 17 11 8 15 9 7 14 16 1 12 4 )
Position 5 partitioned (UDgreater) vector:
v1 = ( 14 17 15 16 13 12 10 11 9 8 0 2 7 5 3 1 6 4 )