一亿个8位数字，用什么排序方法中国之最大数 _中国之最大数

假设现在有一亿个8位以内的数要进行排序，应该怎么处理？
想一想，如果是使用普通的排序算法，那需要将这一亿个数全部都读到内存中，然后再进行排序计算的话，如果全部按照 int类型来说，一个 int32位，4字节，那一千万个数就是 400M，再加上运行时的一些额外内存，肯定是不会少于400M 的。
内存可是服务器的宝贵资源，这实在是有点浪费了，而且快速排序的时间复杂度是，这样一来，这一亿个数光排序计算的时间就会很长，还不包括将这一亿个数读入内存的时间。
那有没有什么又快有省内存的方法呢？今天咱们来介绍一种方法叫做位图排序法。
什么是位图【一亿个8位数字，用什么排序方法中国之最大数】位图（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了。

一亿个8位数字，用什么排序方法 中国之最大数

一亿个8位数字，用什么排序方法中国之最大数