您当前位置:设计在线网 >> JavaScript >> 浏览文章

节省空间的一种排序方法:位图算法排序与查找

分享到:
本文章讲述了节省空间的一种排序方法:位图算法排序与查找.

文详细介绍下关于位图算法排序与查找知识:

 位图算法称的上是最简单的算法,只需要一个for循环就能够搞定排序和查找,但是同时它也是对待操作的数据要求最苛刻的 ,首先这些数据必须是正整数,其次要大致知道这些数据的范围,且有一定的聚集性。

位图排序是一种效率极高(复杂度可达O(n))并且很节省空间的一种排序方法,但是这种排序方法对输入的数据是有比较严格的要求(数据不能重复,大致知道数据的范围)。位图排序即利用位图或者位向量来表示集合。举个例子,假如有一个集合{3,5,7,8,2,1},我们可以用一个8位的二进制向量set[1-8]来表示该集合,如果数据存在,则将set相对应的二进制位置1,否则置0.根据给出的集合得到的set为{1,1,1,0,1,0,1,1},然后再根据set集合的值输出对应的下标即可得到集合{3,5,7,8,2,1}的排序结果。这个就是位图排序的原理。

1.给40亿个不重复的unsigned int的整数,没有排过序,然后再给一个数,如果快速判断这个数是否在那40亿个数当中。

因为unsigned int数据的最大范围在在40亿左右,40*10^8/1024*1024*8=476,因此只需申请512M的内存空间,每个bit位表示一个unsigned int。读入40亿个数,并设置相应的bit位为1.然后读取要查询的数,查看该bit是否为1,是1则存在,否则不存在。

2.给40亿个unsigned int的整数,如何判断这40亿个数中哪些数重复?

同理,可以申请512M的内存空间,然后读取40亿个整数,并且将相应的bit位置1。如果是第一次读取某个数据,则在将该bit位置1之前,此bit位必定是0;如果是第二次读取该数据,则可根据相应的bit位是否为1判断该数据是否重复。

这个算法的空间复杂度在于data的数据类型,下面为了方便使用了int ,其实还可是Byte或者bit !

[java]

int[] data = {4,10,19,1,9,6,4,9};

//[1-20] 因为这些数字都在1-20之间

int[] a = new int[20];//默认全0

for(int i=0;i < data.length;i++){

if(a[ data[i] ] != 1){

a[ data[i] ] = 1;

}else{

System.out.println(data[i]+" 是重复的数字");

}

}

System.out.println("排序结果");

for(int i=1;i<=19;i++){

if( a[i] == 1){

//输出下标

System.out.print(i+" ");

}

}

System.out.println("\n10是否在这个数组里面?");

System.out.println(a[10]==1);

[java]

4 是重复的数字

9 是重复的数字

排序结果

1 4 6 9 10 19

10是否在这个数组里面?

true

推荐阅读:
使用Java操作记事本方法介绍
Java调用sql语句存储过程
JSP和J2EE的关系简述
上一篇:怎样利用Java实现单例模式
下一篇:没有了

相关文章:

推荐文章  
赞助商链接  
热门排行  
主题推广  
中国设计在线网 All Rights Reserved. 互联网违法和不良信息举报
信息产业部备案号:湘ICP备09001063号