从无序（互异）数组中找到第K大的数

1.利用排序算法对其排序，然后直接取出第K个元素——O（nlogn）

随机选择算法——可达到O(N)级别

• 在对A[left,right]执行一次randpartition()后，主元A[p]左侧元素都小于主元，主元右侧元素都大于主元，且主元A[p]是第p-letf+1大的元素。当p>K时，在A[left,p-1]找第K大元素，、；当p==K时，找到；当p<K时，在A[p+1,right]找第K-p大元素

#include<cstdio>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<cmath>
const int max=1000;
using namespace std;
double round(double r)//因为c++没有自带的round()四舍五入函数
{
    return (r > 0.0) ? floor(r + 0.5) : ceil(r - 0.5);
}
int  randPartition(int(&a)[max],int low,int high){//这里数组大小需要标明
	//left,high内生成随机数p 
	int p=(int)(round(1.0*rand()/RAND_MAX*(high-low)+low));//！！！ 取随机数太复杂啦！！
	swap(a[p],a[low]);
	//
	int t=a[low];
	while(low<high){
		while(low<high&&a[high]>t)high--;
		a[low]=a[high];
		while(low<high&&a[low]<=t) low++;
		a[high]=a[low];	
	}
	a[low]=t;
	return low;
}
int randSelect(int (&a)[max],int left,int right,int K){//!!除了引用外，**还可以设置全局变量**
	//递归边界
	if(left==right) return a[left]; 
	int p=randPartition(a,left,right);
	int m=p+1;//下标所处的位置 
	if(K==m) return a[p];
	else if(K>p) return randSelect(a,p+1,right,K-m);
	else return randSelect(a,left,p-1,K);
	 
}
int main(){
	//生成随机数种子
	srand((unsigned)time(NULL)); 
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	int K=3;
	printf("%d",randSelect(a,0,n-1,K));
	return 0;
	
}

出自算法笔记