学步园

今天读到一篇文章：
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=importance_of_algorithms
其中提到用随机算法找数组中第k大数字，于是试着写了一下：

#include <vector>
#include <set>

using namespace std;

#include <cstdlib>
#include <cassert>
size_t rand(size_t maxn)
{
    size_t d = RAND_MAX / maxn;
    size_t nd = d * maxn;
    size_t r;
    do r = rand(); while(r >= nd);
    return r % maxn;
}
int rand(int a, int b)
{
    assert(a < b);
    return (int)rand(b - a) + a;
}

template<typename T>
size_t kthElement(const vector<T> &v, size_t k)
{
    vector<size_t> s(v.size());
    for (size_t i = 0; i < v.size(); i++)
        s[i] = i;
    
    size_t curK = k;
    size_t t;
    
    for(;;)
    {
        size_t c = 0;
        t = rand(s.size());
        const T &value = v[s[t]];
        for (vector<size_t>::const_iterator it = s.begin(); it != s.end(); ++it)
        {
            if (v[*it] < value)
                c++;
        }
        if (c == curK)
            break;
        swap(s[t], s.back());
        s.pop_back();
        // now, the v[s[t]] is c-th element of the rest v
        if (c > curK)
        {   
            // target is smaller than v[s[t]]
            // remove greater values from s
            // s.erase(remove_if(s.begin(), s.end(), bind2st(greater<T>(), value)), s.end());
            for (vector<size_t>::iterator it = s.begin(); it != s.end();)
            {
                if (v[*it] > value)
                    swap(*it, s.back()), s.pop_back();
                else
                    ++it;
            }
        }
        else if (c < curK)
        {
            // target is greater than v[s[t]]
            // remove smaller values from s
            for (vector<size_t>::iterator it = s.begin(); it != s.end();)
            {
                if (v[*it] < value)
                    swap(*it, s.back()), s.pop_back();
                else
                    ++it;
            }
            curK -= c + 1;
        }
        else
            break;
    }
    return s[t];
}

template<typename T>
T median(const vector<T> &v)
{
    size_t s = v.size();
    if (s & 1)
    {
        return v[kthElement(v, s / 2)];
    }
    T a = v[kthElement(v, s / 2 - 1)];
    T b = v[kthElement(v, s / 2)];
    return (a + b) / 2;
}

#include <cstdio>
#include <algorithm>

int main()
{
    int n;
    while(scanf("%d", &n) == 1)
    {
        
        int t;
        vector<int> v;
        for (int i = 0; i < n; i++)
        {
            //    scanf("%d", &t);
            v.push_back(i);
            //v.push_back(t);
        }
        random_shuffle(v.begin(), v.end());
        //printf("%d\n", v[kthElement(v, n / 2)]);
        printf("%d\n", median(v));
    }
    
    return 0;
}