假设现在有一亿个8位以内的数要进行排序，应该怎么处理？

想一想，如果是使用普通的排序算法，那需要将这一亿个数全部都读到内存中，然后再进行排序计算的话，如果全部按照 int类型来说，一个 int32位，4字节，那一千万个数就是 400M，再加上运行时的一些额外内存，肯定是不会少于400M 的。

内存可是服务器的宝贵资源，这实在是有点浪费了，而且快速排序的时间复杂度是 ，这样一来，这一亿个数光排序计算的时间就会很长，还不包括将这一亿个数读入内存的时间。

那有没有什么又快有省内存的方法呢？今天咱们来介绍一种方法叫做位图排序法。

什么是位图

位图（Bitmap）是一种用于表示和存储数据的数据结构，一种数据类型。

实际上位图就是一组二进制位（0或1）的序列，每个二进制位表示一个数据元素的状态。

在位图中，每个数据元素对应位图中的一个位，位图中的每一位都可以看作是一个开关，表示某个数据元素是否存在或满足某个条件。如果某个数据元素存在，对应的位值为1；如果不存在，对应的位值为0。

位图的大小通常由位数来决定，比如8位（一个字节）、16位、32位或64位等。每个位的取值只有0或1，所以位图的存储空间相对于存储实际数据本身要小得多。

为什么位图的存储空间要比实际存储数据本身要小呢？

首先来举个例子。假设你有排列为从 0 到 9 的10个待办事项，假定待办事项有只有两种状态，就是未完成和已完成。在开发过程中，我们很容易想要可以用用布尔值来表示完成和未完成的状态。

那我们可以这样声明这10个待办事项的集合，一个状态集合。

List<Boolean> statusList = new ArrayList();

那这样一来，这10个状态会占用多少空间呢，List本身也占用空间的，这个咱们先不算，单纯算这10个布尔值。在 Java 中一个 Boolean 占用1个字节，那10个呢，就是10个字节。

而我们把它换成用位图来表示呢？

把从 0 到 9 的10个待办事项只用 10个比特位就可以表示了。

上面的顺序表示从0到9的待办事项排序，下面每一个蓝色的表示一个比特，0 表示未完成，1表示已完成。

这样一来，想看第 0 个事项的状态，就获取第0个比特位的值，想看第1个事项的状态，就取第1个比特位的值，依此类推，可以获取每一个事项的状态。

位图排序

通过以上的分析，我们就知道用位图如何表示简单的数据了，但一时间好像和排序扯不上什么关系啊。

假设现在有5个数用位图法排序，分别是1、3、5、7、10，怎么做呢？一个比特位要么是0要么是1，怎么表示1、3、5、7、10 呢？

其实总结下来就是两点：

把位图想象成一个比特数组，数组索引下标可以表示数值，例如3这个数字，就是索引为3的位置；每一个比特位的值表示这个索引位置上有没有数值存在，因为待排序的集合中有3这个数字，所以在索引3的位置上应该是1，集合中没有2这个数字，所以在索引2的位置上应该是 0 。

根据以上两点，可以将这5个待排序数的分布变换成下面的位图形式。

变换的过程

1、首先找到排序集合中的最大数，因为最大的数决定了位图的长度。

位图排序的一个特点就是最大长度就是最大的那个数，所以说，位图排序不适合那种范围、跨度特别大的情况，比如排1万个数，最小的是0，最大的一百亿，那这样一来，这个位图的长度就是一百亿比特了，还不如用其他排序算法。

这个集合中最大的数是10，所以位图的长度是11，因为包含0了。

2、将位图中所有比特位的默认值设置为 0 。

3、遍历集合中的每一个元素，根据元素的数值，将此元素所在索引位的值设置为1。

这样一来呢，只要从头开始遍历这个位图，依次找出值为1的比特位，这个比特位的索引就是实际的值，顺序一下就出来了。

接近一亿个8位以内的排序

回到最开始说的那个问题，将近一亿个8位以内的数排序，差不多就是一亿个数的全排列了，那最大的数就按照一亿算，差不多是12.5M，比快速排序算法全放到内存中的400M要小的多了。

public static void main(String[] args) {        String inputFile = "random_numbers.txt";        int maxRandomNumber = 999999999;        // 从文本文件中读取随机数        Set<Integer> randomNumbers = new HashSet<>();        try (BufferedReader reader = new BufferedReader(new FileReader(inputFile))) {            String line;            while ((line = reader.readLine()) != null) {                int randomNumber = Integer.parseInt(line);                randomNumbers.add(randomNumber);            }        } catch (IOException e) {            return;        }        // 将随机数转换为位图        BitSet bitmap = new BitSet(maxRandomNumber + 1);        for (int num : randomNumbers) {            bitmap.set(num);        }             //输出到一个文件        String outputFile = "sorted_random_numbers.txt";        try (BufferedWriter writer = new BufferedWriter(new FileWriter(outputFile))) {            for (int i = 0; i <= maxRandomNumber; i++) {                if (bitmap.get(i)) {                    writer.write(String.format("%08d", i));                    writer.newLine();                }            }            System.out.println("随机数已成功从文件中位图排序并写入文件：" + outputFile);        } catch (IOException e) {            System.err.println("写入文件时出现错误：" + e.getMessage());        }    }

另外说一点，这接近一亿个数应该是没有重复数据的情况，如果重复数据过多，用位图排序就要用很多额外的手段来标记重复，到最后可能得不偿失。

位图的使用场景

排序小范围整数：

位图排序对于排序小范围的非负整数非常高效。当待排序的整数范围相对较小，并且整数数量较大时，传统的比较排序算法如快速排序、归并排序等可能会有较大的开销，而位图排序则能够在较短的时间内完成排序。

刚才这个接近一亿个数是个比较极端的例子，很多时候其实位图占用的空间还是比较大的，只要有一个特别大的数，就会把整个空间放大。

去重操作：

位图排序可以用于去除重复的元素。通过位图排序，可以快速识别是否有重复元素，并对重复元素进行去重操作。

查找元素：

位图排序可以用于快速查找元素是否存在。在位图中，每个整数对应一个位，如果位为1表示该整数存在，如果位为0表示该整数不存在。通过查找对应的位，可以快速判断一个整数是否存在。

统计频率：

位图排序可以用于统计整数出现的频率。通过在位图中记录整数的出现次数，可以快速计算每个整数的频率。

集合操作：

位图排序可以用于进行集合操作，如并集、交集、差集等。通过对两个位图进行位运算，可以快速得到集合操作的结果。

来源：