注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

火车的家

Put first thing first

 
 
 

日志

 
 

2016.06.17 BFPRT算法  

2016-06-17 11:23:16|  分类: 技术博客 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

BFPRT算法是解决从n个数中选择第k大或第k小的数这个经典问题的著名算法。主要步骤为:

1. 首先把数组按5个数为一组进行分组,最后不足5个的忽略。对每组数进行排序(如插入排序)求取其中位数。
2. 把上一步的所有中位数移到数组的前面,对这些中位数递归调用BFPRT算法求得他们的中位数。
3. 将上一步得到的中位数作为划分的主元进行整个数组的划分。
4. 判断第k个数在划分结果的左边、右边还是恰好是划分结果本身,前两者递归处理,后者直接返回答案。

参考实现:

int BFPRT(int a[], int l, int r, int id) //求数组a下标l到r中的第id个数
{
 if (r - l + 1 <= 5) //小于等于5个数,直接排序得到结果
 {
  insertionSort(a, l, r); return a[l + id - 1];
 }

 int t = l - 1; //当前替换到前面的中位数的下标
 for (int st = l, ed; (ed = st + 4) <= r; st += 5) //每5个进行处理
 {
  insertionSort(a, st, ed); //5个数的排序
  t++; swap(a[t], a[st+2]); //将中位数替换到数组前面,便于递归求取中位数的中位数
 }

 int pivotId = (l + t) >> 1; //l到t的中位数的下标,作为主元的下标
 BFPRT(a, l, t, pivotId-l+1);//不关心中位数的值,保证中位数在正确的位置
 int m = partition(a, l, r, pivotId), cur = m - l + 1;
    if (id == cur) return a[m];                   //刚好是第id个数
    else if(id < cur) return BFPRT(a, l, m-1, id);//第id个数在左边
    else return BFPRT(a, m+1, r, id-cur);         //第id个数在右边
}

int partition(int a[], int l, int r, int pivotId) //对数组a下标从l到r的元素进行划分
{
    //以pivotId所在元素为划分主元
 swap(a[pivotId],a[r]);
 
    int j = l - 1; //左边数字最右的下标
    for (int i = l; i < r; i++)
        if (a[i] <= a[r])
            swap(a[++j], a[i]);
    swap(a[++j], a[r]);
    return j;
}

  评论这张
 
阅读(112)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017