我写了一个。本以为是最快的，最近有人说还有更快的，望指教。
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(n)的时间不过如果数据太大空间会增大。应该还有更好的方法。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    int a[6]={2,4,67,8,3,5};
    int i,max=0,count=0;
    int k;
    scanf("%d",&k);
    for(i=0;i<6;i++)
    {
        max=max>a[i]?max:a[i];
    }
    int *p=(int*)malloc(sizeof(int)*max+1);
    memset(p,0,sizeof(int)*max+1);
    for(i=0;i<6;i++)
    {
        p[a[i]]=a[i];
    }
    for(i=max;i>0;i--)
    {
        if(p[i]!=0)
        {
            count++;
            if(count==k)
            {
                break;
            }
        }
    }
    printf("%d",p[i]);
    return 0;
}

[ 本帖最后由 玩出来的代码 于 2010-3-28 21:39 编辑 ]

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

学习了，谢谢

一楼和三楼的思想都很high，，，汲取所长，