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

平安甜橙博客

家俭则兴,人勤则健,能勤能俭,永不贫贱

 
 
 

日志

 
 
 
 

【转载】计数排序:  

2017-12-14 08:28:58|  分类: 数据结构 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自jia_huiqiang《计数排序:》

计数排序:是一种线性排序算法,不用进行比较。

基本思想:对于每个元素x,找出比x小的数的个数,从而确定x在排好序数组中的位置。例如:算法导论中的例子,

   数组A[]是待排序的数组,C[]是用来中间数组B[]是最终排好序的数组。对于A[]中的每一个元素,将其元素作为C[]数组的下标。也就是,如图a)a[4]=0 a[7]=0,C[0]=2表示A[]中的元素为0的有两个,C[1]=0,表示A[]数组中没有值为1的元素,以此类推。所以C[j]中存放的是A[]中j的个数。图b)中c[]数组是对图a)中的c[]数组前面的数字相加后的结果,如C[2]=4表示,A[]中小于等于2的元素有4个。以此类推。在得到A[]和C[]之后,开始排序,如A[1]=2,我们由C[]数组知道,小于等于2的元素有4个,所以排好序的数组中,2应该放在数组的第4位,同时c[2]减1。图中是从后往前的。比如A[8]=3,由c[3]=7,数组A中小于等于3的元素有7个,因此B[7]=3,c[3]减1,c[3]=6.

注意:由于数组中可能会有相等的元素,在排序后,要把C[]中对应部分减1。时间复杂度是:O(N+K),N表示待排序数组中的元素个数,K表示中间数组元素的个数(也就是待排序数组中元素值最大的元素);空间复杂度是:O(K)

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

历史上的今天

评论

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

页脚

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