寻找中项，时间复杂度O(n) C/C++实现

题目

对于长度为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;
}