c++ nth

查找第n小的元素

nth_element(起始地址，查找元素的下标，最后一个元素地址+1)；
nth_element(起始地址，查找元素的下标，最后一个元素地址+1，自定义排序)；

举例：
查找数组中第6小的元素

#include
#include//必要头文件 
using namespace std;
int main(){
	int a[10]={1,5,6,3,9,2,8,7,4,10};
	nth_element(a,a+5,a+10);//查找数组第6小的元素 
	cout<<"第6小的数是："< 
那么能不能查找第n大的元素呢？
 当然可以的，将第n大的问题转换为求第m小的问题就可以了
 例如一个数组有10个元素，求第2大的数，那么它等同于求第10-2+1=9小的元素
 
#include
#include//必要头文件 
using namespace std;
int main(){
	cout<<"请问您需要查找第几大的数？" <>n; 
	int a[10]={1,5,6,3,9,2,8,7,4,10};
	nth_element(a,a+10-n,a+10);
	cout<<"第"< 
自定义排序：
 假如遇到无法直接比较大小的结构体怎么办呢？重载运算符是一种办法，也可以自定义排序，例：
 
#include
#include
#include//必要头文件 
using namespace std;
struct node{
	int x,y;
//	构造函数 
	node(int x,int y){
		this->x=x;
		this->y=y;
	}
};
bool cmp(node n1,node n2){
	return n1.x v;
	node n1(1,3);
	node n2(5,2);
	node n3(3,6);
	node n4(2,6);
	node n5(4,4);
	v.push_back(n1);
	v.push_back(n2);
	v.push_back(n3);
	v.push_back(n4);
	v.push_back(n5);
	nth_element(v.begin(),v.begin()+1,v.end(),cmp);
	cout<<"按x排序，第2小点的数是："< 
函数的实现 
与快速排序思路大致相同，例如一个数组有10个元素：4，3，9，1，8，6，5，10，2，7；
 
找第7小的元素：
 第一步：开找第一个数，4，比4小的放在4左边，比4大的放在4右边
 结果:3，1，2，4，9，8，6，5，10，7
 结论：那么4是第4小的数，因为有3个比它小的元素在左边
 
第二步：第7小的元素肯定在4的右边，找4右边的第一个数，9，比9小的放在9左边，比9大的放在9右边
 结果:3，1，2，4，8，6，5，7，9，10
 结论：那么9是第9小的数，因为有8个比它小的元素在左边
 
第三步：第7小的元素肯定在9的右边，找9左边的第一个数，7，比7小的放在7左边，比7大的放在7右边
 结果:3，1，2，4，6，5，7，8，9，10
 结论：那么7是第7小的数，因为有6个比它小的元素在左边
 
得到第7小的数7，结束
 
时间复杂度平均为O(n),最差为O(n^2);
 它把不必要的排序步骤省略掉了，复杂度大大降低