用法
c
nth_element(first,kth,end)
1
first,end 第一个和最后一个迭代器 kth 要定位的第k个元素,能对它进行随机访问
将第kth元素放到它该放的位置,左边元素都小于等于它,右边的元素都大于等于它
空间复杂度O(1), 时间复杂度O(n)
c
#include <cstdio>
#include <algorithm>
using namespace std;
int main(){
int a[15] = { 0,1,2,5,7,3,4,1};
nth_element(a+1,a+4,a+8);
int i;
printf("nth_element 4th:\n");
for(i=1;i<=7;i++){
printf("%d ",a[i]);
}
printf("\n");
printf("4th element: %d\n",a[4]);
sort(a+1,a+8);
printf("sorted:\n");
for(i=1;i<=7;i++){
printf("%d ",a[i]);
}
printf("\n");
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24