午夜拍键惊奇
子夜 编程 代码与我同在
首页
新随笔
新文章
联系
聚合
管理
posts - 48,comments - 118,trackbacks - 79
<
2005年12月
>
日
一
二
三
四
五
六
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
7
枯藤老树昏鸦
小桥流水人家
古道西风瘦马
夕阳西下
断肠人在天涯
留言簿
(10)
给我留言
查看公开留言
查看私人留言
随笔分类
(49)
Design Patterns(5)
Java 点滴(15)
OO(5)
Struts(2)
基础理论(1)
破解(5)
程序人生(16)
随笔档案
(48)
2008年9月 (1)
2006年6月 (1)
2006年3月 (3)
2006年2月 (1)
2005年11月 (7)
2005年10月 (7)
2005年9月 (7)
2005年8月 (16)
2005年2月 (5)
相册
Mustang
IBM Developer Works
驯服 Tiger: 并发集合
驯服 Tiger: 集合框架
其它链接
MSN blog
积分与排名
积分 - 104334
排名 - 558
最新评论
1. re: 接口与Object类的关系?[未登录]
因为Object的clone方法是protect的,你试试那些public方法(equals、toString....)。所有的接口都会声明Object的public方法(大多数是隐式的)。
--KK
2. 发现一个问题
你前半部分的消费者线程搞的有问题
--刘sir
3. re: Alloy Look and Feel下载
謝謝..可以使用的
--zf
4. re: 位图(bitmap)排序
为了更节省时间 应该用 BitArray
--zhangdp
5. re: 接口与Object类的关系?
@allen
靠,4年前的文章还有人回复……
--^ Mustang ^
6. re: 接口与Object类的关系?[未登录]
靠你掉TOSTING()绝对可以。任何的类包括实现类都是其子类。。。CLONE是没实现而已
--allen
7. re: Borland Look and Feel下载[未登录]
用了,但是不是很好看啊~~
但是还要谢谢你
--海阔天空
8. re: 腾讯七宗罪 [转载自PCHome]
评论内容较长,点击标题查看
--无名之人
9. re: 搬家
我靠,你呀的技术博客居然还在
--郑
10. re: 位图(bitmap)排序
这段代码是错的,不能用integer array, 只能用BitArray, 否则,在内存受限的情况下,你是不能把所有的的数装下的。所谓的位图排序也是这个意思
--haibo
11. re: 搬家
吃惊....竟然是两...年
--猪
12. re: 群硕笔试题
今天我也去笔试
--goodspeed
13. re: 群硕笔试题
正要去笔试
谢谢!
--。。。
14. re: 群硕笔试题
今天马上去笔试群硕
--yz79845
15. re: 群硕笔试题
明早就去群硕笔试了 希望顺利完成
--IMAX
16. re: 群硕笔试题[未登录]
我想问一下,你是笔试的软件开发吗?
因为我今年要参加群硕的笔试,可是我申请的是测试,开发和测试的题目是一样的吗?
谢谢~~
--Tina
17. re: 群硕笔试题
评论内容较长,点击标题查看
--Suriel
18. re: 群硕笔试题
怎么那怎么多傻B啊,还有人敢在这说是13,真TMD的傻B
--路人
19. re: Alloy
请给我一份,hq.cn.com@gmail.com , 谢谢
--岛主
20. re: Alloy
也给我发一份,angelswingadam@163.com,谢谢
--angelswing
21. re: Alloy
评论内容较长,点击标题查看
--Simon Gong
22. re: Alloy
可否给我发一份,谢谢先
spimlee@yahoo.com.cn
--spimlee
23. re: JBuilder 2006 BT种子
好棒哦,可以下JBuilder 2006了也
--girl
24. re: Alloy
key: v#ej_technologies#uwbjzx#e6pck8
--jhonny
25. re: 群硕笔试题
刚进去有多少钱?
不方便写的话请发我邮箱吧,大谢了!!!
well88@citiz.net
--路过
26. re: Alloy
tcmy_168@163.com
给我一份,谢谢了
--tian
27. re: IDEA破解过程
破解了的class文件
给我也发一个吧
谢谢了!
email:huhaitao1231@gmail.com
--huhaitao
28. re: 群硕笔试题
评论内容较长,点击标题查看
--re: 群硕笔试题
29. re: JBuilder 2006 BT种子
真的太好喇!
--Angus
30. re: 群硕笔试题
经过DEV-C++编译器测试结果是7,13
--微微
31. re: 软件设计师
工作几年后,发现,这个东西一点都不重要了! 实践比重要呀!
--Moon[匿名]
32. re: 群硕笔试题
测试结果7 13
--潇洒哥
33. re: IDEA破解过程
破解了的class文件
给我也发一个吧
谢谢了!
我的email: s9027059@gmail.com
--CCT
34. re: 不要更新:Windows XP 安全更新程序 (KB913446)
谢谢你了,差点犯错!
--火烈鸟
35. re: Alloy
一直没有狠心下来学学汇编、破解,其实还是蛮有用的啊。羡慕……
--陈小稳
36. re: Alloy
也请给我一份研究学习下吧。我的邮箱是:ccxw1983@yahoo.com.cn。先道声谢谢了!
--陈小稳
37. re: 使用策略模式(Strategy)实现多关键字排序
I got it!
3ks!
--zhl
38. re: JBuilder 2006 BT种子
非常感谢!
--xx
39. re: Alloy
是否可以给我一份破解1.4.4,谢谢了!
townsendtan@yahoo.com.cn
--townsend
40. re: JBuilder 2006 BT种子
@chenxiaoming
--23525
阅读排行榜
1. Java Concurrent框架之阻塞队列(Blocking queue)(13653)
2. 群硕笔试题(11176)
3. JBuilder 2006 BT种子(8857)
4. IDEA破解过程(6149)
5. 在Struts中使用Validator实现可配置的信息校验(一)(5284)
6. 适配器模式(Adapter)(3159)
7. 接口与Object类的关系?(2415)
8. Alloy(2413)
9. Java API中文版[转载自Sun技术社区](2227)
10. java.util.Calendar中的陷阱(2226)
11. Alloy Look and Feel下载(2080)
12. 不要更新:Windows XP 安全更新程序 (KB913446)(2016)
13. 在Struts中使用Validator实现可配置的信息校验(二)(1808)
14. 使用FilterServlet对页面进行转码(1765)
15. Borland Look and Feel下载(1702)
16. Tomcat 5.5.9 不支持switch(<enum>)?(1518)
17. 位图(bitmap)排序(1476)
18. OO基本概念(1449)
19. 奇怪的范型定义(1438)
20. 腾讯七宗罪 [转载自PCHome](1387)
21. “软件工业奥斯卡”SYS-CON读者选择奖: Java开发(转载自CSDN)(1310)
22. Alloy破解过程(1297)
23. IDEA cracker下载(1295)
24. James Gosling(1278)
25. 使用策略模式(Strategy)实现多关键字排序(1232)
26. Joshua Bloch咏Tiger诗八首(1195)
27. “软件危机”时总结的坏的编程习惯——我们是否依旧守着古风?(1165)
28. A beginners guide to Dependency Injection [转载自TSS](1107)
29. 缺省适配器模式(Default Adapter)(1077)
30. Java code name(1051)
31. Object Modeling Strategies (IV) (1038)
32. IDEA(942)
33. 软件设计师(915)
34. 原型模式(Prototype)(904)
35. Object Modeling Strategies (I)(857)
36. 接受程序设计语言的再教育[转载自dearbook书评](836)
37. 我回来了(836)
38. 在Java中使用Oracle blob(827)
39. Object Modeling Strategies (III)(818)
40. Object Modeling Strategies (II)(798)
评论排行榜
1. Alloy(26)
2. 群硕笔试题(15)
3. IDEA破解过程(13)
4. 接口与Object类的关系?(9)
5. JBuilder 2006 BT种子(7)
6. 腾讯七宗罪 [转载自PCHome](5)
7. 软件设计师(5)
8. 位图(bitmap)排序(4)
9. James Gosling(4)
10. IDEA(3)
11. IDEA cracker下载(3)
12. Alloy Look and Feel下载(2)
13. Borland Look and Feel下载(2)
14. 搬家(2)
15. 搬家咯(2)
16. Alloy破解过程(2)
17. Tomcat 5.5.9 不支持switch(<enum>)?(2)
18. java.util.Calendar中的陷阱(2)
19. 接受程序设计语言的再教育[转载自dearbook书评](2)
20. 使用策略模式(Strategy)实现多关键字排序(2)
21. class文件中的秘密(1)
22. java.util.StringTokenization(1)
23. 在Struts中使用Validator实现可配置的信息校验(二)(1)
24. 不要更新:Windows XP 安全更新程序 (KB913446)(1)
25. 奇怪的范型定义(1)
26. Java Concurrent框架之阻塞队列(Blocking queue)(1)
27. Object Modeling Strategies (IV) (0)
28. Java code name(0)
29. “软件危机”时总结的坏的编程习惯——我们是否依旧守着古风?(0)
30. 使用FilterServlet对页面进行转码(0)
31. OO基本概念(0)
32. Java API中文版[转载自Sun技术社区](0)
33. 在Struts中使用Validator实现可配置的信息校验(一)(0)
34. 我回来了(0)
35. “软件工业奥斯卡”SYS-CON读者选择奖: Java开发(转载自CSDN)(0)
36. Object Modeling Strategies (III)(0)
37. Object Modeling Strategies (II)(0)
38. Joshua Bloch咏Tiger诗八首(0)
39. Object Modeling Strategies (I)(0)
40. 缺省适配器模式(Default Adapter)(0)
位图(bitmap)排序
放假之前从图书馆借来《编程珠玑》,开篇便把我震住,作者以位图排序优雅地解决了一个现实问题:
有3000万个没有重复的电话号码,1M内存,外存比较充裕,需要将这3000万个电话排序
借此作者引出了位图排序:
位图排序是指以一个N位长的串,每位上以“1”或“0”表示需要排序的集合(后简称“集合”)中的数。比如集合为{2,7,4,9,1,10},则生成一个10位的串,将第2、7、4、9、1、10位置为“1”,其余位置为“0”,这样当把串中所有位都置完后,排序也自动完成了(因为串的下标是有序的):1101001011
位图排序的代码如下:
public
void
bitmapSort(
int
[]
set
)
{
int
max
=
max(
set
);
int
[] array
=
new
int
[max];
for
(
int
i
=
0
;i
<
array.length;i
++
)
array[i]
=
0
;
for
(
int
i
=
0
;i
<
set
.length;i
++
)
array[
set
[i]]
=
1
;
for
(
int
i
=
0
;i
<
array.length;i
++
)
{
if
(array[i]
==
1
)
System.
out
.println(i
+
” ”);
}
}
private
int
max(
int
[]
set
)
{
//
return the maxium integer of the set
}
可以看出,位图排序的时间复杂度是O(n)的,比一般的排序都快,但它是以空间换时间(需要一个N位的串),而且有一些限制,比如排序前集合大小最好已知,而且集合中元素的最大重复次数必须已知,最好是稠集数据(不然空间浪费很大)。
posted on 2005-02-13 22:17
^ Mustang ^
阅读(1476)
评论(4)
编辑
收藏
所属分类:
基础理论
FeedBack:
#
re: 位图(bitmap)排序
2005-12-16 13:44 |
我的万花@
绝!不知道谁发明的
回复
更多评论
#
re: 位图(bitmap)排序
2005-12-16 13:45 |
我的万花@
不过看你写的文字看不懂,还是要看代码,嘿嘿
回复
更多评论
#
re: 位图(bitmap)排序
2008-10-04 12:14 |
haibo
这段代码是错的,不能用integer array, 只能用BitArray, 否则,在内存受限的情况下,你是不能把所有的的数装下的。所谓的位图排序也是这个意思
回复
更多评论
#
re: 位图(bitmap)排序
2009-08-27 12:51 |
zhangdp
为了更节省时间 应该用 BitArray
回复
更多评论
新用户注册
刷新评论列表
只有注册用户
登录
后才能发表评论。
网站导航:
博客园
IT新闻
知识库
C++博客
博问
管理