java位图排序算法怎么实现

这篇文章主要介绍“java位图排序算法怎么实现”，在日常操作中，相信很多人在java位图排序算法怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”java位图排序算法怎么实现”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

算法要求

输入：一个最多包含n个正整数的文件，其中每个数字都小于n（n=10^7）没有重复文件

输出：按照升序输出

约束条件：只有1M左右的内存空间，足够的磁盘空间。最多运行为几分钟，如果为10秒就不需要优化。

在我上学刚毕业那会曾经碰到过三个面试官提问我这道题，当时我第一次的回答是简单的冒泡排序，面试官直接提醒了我，内存有限，后来我灵机一动，我可以借助第三方数据库，先把它存到数据库，然后order by顺序查询出来。很明显，这是一个不是办法的办法。当然，我当时也是答非所问。但是现在回过头来想一想，还是有办法解决的。

问题分析
 如果说我们把这些数据引入到内存进行排序显然是不现实的，因为一部分n的大小都可能超过1M，这时我们可以考虑使用位图排序。

实现概要

假设我们有一组 {3,1,8,5,4,9} 这样的一组小于10数据。我们可以用如下字符串进行表示这个集合

0 1 0 1 1 1 0 0 1 1 其中代表集合中的数据表示为1，其它的为零

如果我们使用伪代码可以如下实现：

1 初始化一个大小为n的数组

for n = [1,n);
    bit[i] = 0

2 顺序读取每个文件中每一个数字

for each i;
    bit[i] = 1;

3 输出

for n = [0,n);
    if(bit[i]==1)
        print i;



 java代码实现


int[] arrs = {12,234,13,1,143,321,1411};//磁盘中的文件
        
int[] sorts = new int[2000];

for(int arr : arrs) {
    sorts[arr] = 1;
}

for(int i=0;i<2000; i++) {
    if(sorts[i] == 1) {
        System.out.print(i+",");
    }
}

到此，关于“java位图排序算法怎么实现”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注亿速云网站，小编会继续努力为大家带来更多实用的文章！