题目
对于长度为n的整型数组A，随机生成其数组元素值，然后实现一个线性时间的算法，在该数组中查找其中项。
算法思想
选择数组中任意数作为基准，将数组分为大于，小于，等于此数的三部分，寻找中项。设小于基数的个数为n_small,大于的为n_big,数组长度的一般为k，若k<=n_s，说明中项在小于基数的数组里面，再对small数组递归上述操作，若k=n_s+1，则说明中项就是基数，若k>n_s+1，说明中项在big数组里，那么对big数组递归，此时k=k-1-n_s。
代码
#include <iostream>
#include <vector>
using namespace std;
int select(vector<int>&A, int k,int n)
{
int x = A[rand() % n];
vector<int>small;
small.resize(n);
vector<int>big;
big.resize(n);
int equal,n_s=0,n_b=0;
for (int i = 0; i < n; i++)
{
if (A[i] > x)
big[n_b++] = A[i];
else if (A[i] == x)
equal = x;
else
small[n_s++] = A[i];
}
if (k <= n_s)
return select(small, k,n_s);
else if (k == n_s + 1)
return equal;
else
return select(big, k - 1 - n_s,n_b);
}
int main(void)
{
vector<int>A;
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
cin >> temp;
A.push_back(temp);
}
int k = (1 + n) / 2;
cout << select(A, k,n);
system("pause");
return 0;
}
