取n个数中第k大数

问题：有一个大小为n的数组，求其中第k大的数。

这里采用快速排序思想，将数组进行划分 ，该算法时间复杂度为O(n)。

#include<iostream>
#include<time.h>
#include<stdlib.h>
using namespace std;

int random_partion(int *arry,int n)
{
    time_t t; 
    srand((unsigned)time(&t));
    int index=rand()%n;
    swap(arry[index],arry[n-1]);   //起到随机效果 
    int i=-1;    				    //i指向小于p[n-1]的元素的位置
    int j=0;     
    while(j<n)
    {                               //将大于p[n-1]的数交换到前半部分
        if(arry[j]>arry[n-1])
        {
			swap(arry[++i],arry[j]);
        }
        j++;
     }
     swap(arry[++i],arry[n-1]);
     return i; 
}

int getKMax(int *arry,int n,int k)
{
	int pos;
    if(k<=0)
        return -1;
    if(k>n)
        return -1;
	pos=random_partion(arry,n);   //对原数组进行划分
    if(pos == k-1)             //如果pos+1==k，那么返回该值，这就是第k大的数
		return arry[pos];
    else if(pos<k-1)
		return getKMax(arry+pos+1,n-pos-1,k-pos-1);  
    else
		return getKMax(arry,pos,k);   
}

int main()
{
	int arry[] = {543,56,6435,965,561,555,604,21,546,844,68};
	int k;
	cout<<"input k:";	
	cin>>k;
	cout<<getKMax(arry,11,k)<<endl;
	system("pause");
	return 0;
}

【免责声明】本站内容转载自互联网，其相关言论仅代表作者个人观点绝非权威，不代表本站立场。如您发现内容存在版权问题，请提交相关链接至邮箱：bqsm@foxmail.com，我们将及时予以处理。