// most_k.cpp : 定义控制台应用程序的入口点。
//第k个最大数
#include "stdafx.h"
#include <iostream>
using namespace std;
int k_most(int *a, int n, int k)//n个数组中第k个最大数
{
if (n==1 && k==1)
{
return a[0];
}
int x0;
if (a[0] < a[1])//取一个比较小的，防止特殊情况的发生
{
x0 = a[0];
}
else
{
x0 = a[1];
}
int *b = new int[n];//存储x0<=的数
int *c = new int[n];//存储x0>的数
int i;
for (i=0; i<n; i++)//初始化
{
b[i] = 0;
c[i] = 0;
}
int b_i=0, c_i=0;
for (i=0; i<n; i++)
{
if (a[i] > x0)
{
c[c_i] = a[i];
c_i++;
}
else
{
b[b_i] = a[i];
b_i++;
}
}
if (b_i>=k)//则要找的数在b中
{
delete c;
return k_most(b, b_i, k);
}
else
{
delete b;
return k_most(c, c_i, k-b_i);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[5]={8,2,3,4,5};
cout<<k_most(a,5,5)<<endl;
getchar();
return 0;
}