位图排序

1.位图的理解
我们都明白图形格式中位图储存方式,其实就是以象素为单位的小方块,一格一格的纵横累积起来. 每一个小方块代表一种颜色,当然,如果对于黑白的二色图来说更加简单,只需要一个bit位即可表示. 这和我们的数据在计算机中的存储格式是相似的,内存条的也像是一格一格的bit位纵横交错而成. 因为这样的启发,我们发现一个个bit位象列队一样排列着,顺序相当严谨,如果我们的数据能够通过一种转换方式(逻辑上)能有序的和bit位一一对应起来的话,那么我们按照bit位的顺序把它输出来不就是排序的数据集合吗?

2.索引的概念
通过上面的描述,我们很容易联想到一样东西-索引。索引对于我们数据库的使用无疑相当重要,以至于现在很多数据量巨大的单表查询的性能完全仰仗于它.它和位图的相似性在于:如果我们把每一行数据看作一个单位的数据,那么索引可以看作是该数据通过一种转化方式映射到某个存储空间,如果数据的顺序和索引的顺序是一致的话,那么当我们按序对该存储空间访问时,就得到了有序的数据集.当然很多情况下,索引都是数据的一部分,然而在Oracle中有函数索引的概念,它就完全表达了这种转化方式和映射关系了.

3.排序的一种巧妙方法
位图天生和排序分不开,因为它是最本质的有序载体. 有一种问题如下:现有某市的所有7位数字的电话号码,要求我们按序输出.

分析: 问题的目标-是对数字进行排序 问题的条件-7位数字,简单看作0000000到9999999
问题的环境-一个市的电话号码,数量不菲,极有可能接近1000万,任何排序方法的时间
和空间代价都很大.
联想: 抓住问题的意义,电话号码在本问题上的一个现实意义就是该电话号码在整个电话号码集合上的位子,更具有特征的是,电话号码本身就反应了这么一个位子信息.如果我们设立1000万个bit位,每一位表示该位置上电话号码是否存在(设定1为存在,0-不存在),位号就是电话号码本身,那么我们遍历所有的位,输出位号为1的电话号码,不就是排序的电话号码吗? 巧妙之处: 因为我们利用了数据本身的意义!

描述过程:
1.把整个bit位组初始化为0(000000000000......00000000)

2.读入所有的号码,在号码对应的Bit上置1

3.循环: for(int i=0;i<10000000;++i) { //i就是电话号码 if(bit[i]==1){ print i; }

4.扩展位图排序本身需要一定的环境,就像上面描述的数量大,且和位置数字序号的意义吻合. 当然,我们看到了位图排序的高效与精彩巧妙之处,对于我们的数据进行排序的时候,可不可以思考一下: 分析我们的数据特征很关键,任何问题可能都是从分析特征找突破口的,考虑一下我们的数据存不存在一种转化方法使得他能映射到这种数字关系上来.构造的过程也是你的创造.


引自：
http://www.cnblogs.com/glacierh/archive/2008/08/11/1264922.html

以空间换取时间