我写了一个。本以为是最快的，最近有人说还有更快的，望指教。
int kth_a[n](int &a,int k)
{
    int *t,*key;
    int l=0,r=n-1,i,j;
    while (l<r)
   {
        for (key=a[((i=l)+(j=r+1))/2];i<j;)
        {
            for (j--;key<a[j];);//从右到左找到比key大的数，a[j]
            for (i++;a[i]<key;);//从左到右找到比key小的数，a[i]
            if (i<j) t=a[i],a[i]=a[j],a[j]=t;
        }//此时a[]被分为左边a[0..j-1]比a[j]小，a[j+1..n]比a[j]大
        if (k>j) l=j+1;//k为j右方的数
        else r=j;
    }
    return a[k];
}
看起来并非在O(n)内完成，但平均时间是o(n).最坏为o（n*logn）

三楼的朋友，你的代码中时间复杂度是o（m），m为数组中最大数。那样效果就不好了吧。