需求:
1.需要就N位数字进行排序(N>5)
2.N位数是一个稠密的数字集合
3.集合中没有重复的元素(数字)
限制:
1.尽量减少内存使用
2.要求算法时间要短
先写一个工具类,生成稠密集合
import java.util.Date;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;
public class InitArray
{
public static Integer[] getArray(int nums)
{
int count=0;
Random random = new Random(new Date().getTime());
Set<Integer> set = new HashSet<Integer>();
for(;count<nums;count++)
{
set.add((int)(random.nextFloat()*nums));
}
return set.toArray(new Integer[]{});
}
}
排序实现
import java.util.Date;
public class BitMapSort
{
//N 数字数量级
public static int NUMS=1000;
/**
* Logger for this class
*/
private static final Log logger = LogFactory.getLog(BitMapSort.class);
@SuppressWarnings("deprecation")
public static Integer[] sort(Integer array[])
{
byte[] loop =new byte[NUMS];
//置0 java默认为0
// for(int i=0;i<NUMS;i++)
// {
// loop[i]=0;
// }
logger.info("--------------开始位向量排序--------------");
Date begin = new Date();
//将数据插入位图
for(int j=0;j<array.length;j++)
{
loop[array[j]]=1;
}
//输出排序
for(int j=0,k=0;k<NUMS;k++)
{
if(loop[k]==1)
{
array[j++]=k;
}
}
Date end = new Date();
logger.info("--------------位向量排序结束--------------");
logger.info("--------------位向量排序耗时:"+(end.getMinutes()-begin.getMinutes())+"分钟 "+(end.getSeconds()-begin.getSeconds())+"秒--------------");
return array;
}
}
测试:
import org.apache.commons.logging.Log;
import org.apache.commons.logging.LogFactory;
public class Main
{
/**
* Logger for this class
*/
private static final Log logger = LogFactory.getLog(Main.class);
private static int NUMS=BitMapSort.NUMS;
/**
* <b>main。</b>
* <p><b>详细说明:</b></p>
* <!-- 在此添加详细说明 -->
* 无。
* @param args
*/
public static void main(String[] args)
{
logger.info("--------------生存"+NUMS+"以内的稠密数组--------------");
Integer array[] = InitArray.getArray(NUMS);
logger.info("--------------生成完毕--------------");
Integer arr1[] = BitMapSort.sort(array);
}
}
说明:这个排序的速度很快,但是适合稠密的数据集合,不然会浪费很多内存。
分享到:
相关推荐
基于聚合位向量算法,提出一种新的改进算法,在不影响时间效率的基础上,通过改变算法中位图的存储方式,将聚合位图与位图交叉存储,忽略位图中全为0的部分,极大地减少了空间开销。最后,在仿真环境中对算法进行评测...
Delphi中用位图ScanLine属性快速灰度图像
将24位位图转换成16位位图的源码,包括555和565格式
这个使用完全使用位图自制对话框的例子,在VC6 和VC2008 下编译通过。很好的例子Y
Flash as3基于位图的碰撞检测实例,自己写的,有兴趣的话可以看看
基于共享内存的位图,重点解释了为什么同步重要 GPU CUDA
基于OpenCV的(序列图像)8位图转24位图,可以操作序列图像
24位彩图转为8位灰度图的C++代码,通过修改位图文件信息头来实现位图转换。
基于位图的数字图像处理系统毕业设计软件学院.doc
MFC程序 位图显示 支持8,24,32位位图显示
基于位图识别的UI自动化测试研究和应用.rar
基于位图识别的UI自动化测试研究和应用.pdf
24位图转化为8位图的C++代码,很好用的
行业分类-设备装置-一种基于位图追踪法的双探针自动测试平台.zip
Delphi自制的水晶按钮(基于BMP位图)
本程序实现了jpg图片、png图片、24位/32位位图转256色灰度位图图,使用了MFC框架,并且提供了保存位图的功能
实现PNG转32位位图,32位位图间对接,十分适合RIBBON工具栏的制作!!!
绝度能用,代码完整,本人亲自测试,运行完美,能将24位位图转换为8位位图
VB制作基于BMP位图的图标工具栏,把一些基于位图格式的图标添加到工具栏窗口上,美化工具栏,更显专业,也有利于操作,具体是怎么实现的呢?这个VB源码会演示实现原理,推荐下载。
基于24位bmp位图的信息隐藏编程实例,提供源代码,可为信息隐藏技术的学习者提供参考