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

 
 
 

日志

 
 

对于基数排序的一些理解  

2014-05-08 08:59:34|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
居然在这种sx问题上卡了好久
决定为它写一点东西吧
首先 学基数排序的话 最好先把计数排序&桶排序学一下
其实从一些参考书上直观感受的话 基数排序是用双向链表实现的(这个应该不用解释多少了)
但是实际上如果真的这样做的话 常数会比较大
在有些应该用基排的题目上 这样实现效率甚至不如快排
然后便去请教了不少神犇 但是大家似乎都认为基排是 只可意会 不可言传的
最后 神犇hockey_for_NOI发了一份伪代码
----------------------------------------------------------
清空count
count[value[i]]++
count前缀和
for (int i=n; i; i--) result[count[value[i]]--]=i;
然后他还说
相对位置转绝对位置 手推一下立刻明白
----------------------------------------------------------
于是 又拿去问了下lwh巨巨 
然后他解释说
先记录每个值有几个
然后前缀和,这样count[i]就变成了值为i的数在排序后的数组中最后一位的位置
然后下面那个for就是去领位置,每领完一个就,向前移一位
----------------------------------------------------------
然后还要再扫一遍来更新rank
大概就是这么多了吧(最近真是越来越笨了)
  评论这张
 
阅读(156)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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