xyjzsh

O(n)的时间内找到第k个最大值（最小值）的算法

下面介绍一种在O(n)的时间内找出第k个最大值(最小值)的方法
该方法和快速排序相似。不同在于每次只出理一边。
伪代码如下：
Random-select(A,p,r,i)//找到A中的第i个最小值
if p==r
then return a[p]
q = random-partition(A,p,r)
k = p-q+1
if(i==k)
then return A[q]
else if i<k
then return random-select(A,p,q-1,i)
else return random-select(A,q+1,r,i-k)
这个算法很不错。

posted on 2010-12-02 11:02 呆人 阅读(926) 评论(0)  编辑 收藏 引用 所属分类: 算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2010年12月>
日一二三四五六
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜