// main.cpp
# include <iostream>
# include <vector>
# include <algorithm>
using std::vector;
using std::sort;

int select(vector<int> A, int low, int high, int k)
// Return the number in A which is the K-th in its size. 
{
    int length = high - low + 1;
    if (length < 6) {
        // sort A[low, high], return A[k].
        sort(A.begin(), A.end());
        return A[k-1];
    }
    int groups = length / 5;
    int i;
    vector<int> medians;
    for (i = 0; i < groups; ++i) {
        // sort A[low+5*i, low+5*(i+1)], return median.
        std::vector<int>::iterator p = A.begin() + 5*i, q = A.begin() + 5*(i+1);
        sort(p, q);
        medians.push_back(A[low + 5*i + 2]);
    }
    int mm = select(medians, 1, groups, groups/2);
    // Partition the |medians| numbers into three sets: 
    // A1 - all the numbers smaller than mm
    // A2 - all the numbers is equal to mm
    // A3 - all the numbers bigger than mm

    vector<int> A1, A2, A3;
    for (i = low; i < high; ++i) {
        if (A[i] < mm) {
            A1.push_back(A[i]);
        }
        else if (A[i] == mm) {
            A2.push_back(A[i]);
        }
        else if (A[i] > mm) {
            A2.push_back(A[i]);
        }
    }
    if (A1.size() >= k) {
        return select(A1, 1, A1.size(), k);
    }
    else if ( (A1.size() + A2.size()) >= k ) {
        return mm;
    }
    else if ( (A1.size() + A2.size()) < k ) {
        return select( A3, 1, A3.size(), (k - A1.size() - A2.size()) );
    }
}

using std::cin;
using std::cout;
using std::endl;
int main()
{
    // Let a1, ..., an be n real numbers. We would like to compute their median in linear time.
    int n;
    cin >> n;
    vector<int> array;
    int i;
    for (i = 0; i < n; ++i) {
        int item;
        cin >> item;
        array.push_back(item);
    }
    int k = n/2;
    cout << select(array, 1, n, k) << endl;
    // testbench:
    // 25
    // 8 33 17 51 57 49 35 11 25 37 14 3 2 13 52 12 6 29 32 54 5 16 22 23 7
    return 0;
}


[url=http://blog.csdn.net/Sedgewick]感兴趣的来我的窝看看。[/url]