位图排序

所谓位图，就是用一个位（bit）来标记某个元素对应的值，而键就是该元素。才用位为单位的来存储数据，可以大大节省存储空间。
位图通过使用位数组来表示某些元素是否存在，可进行数组的快速查找、判重、删除。
下面来看一个排序的示例。假设要对 0~7 中的 5 个元素（4，2，5，3，1）进行排序，我们采用位图的方法来实现快速排序：
因为要表示 8 个数，所以只需要 8 位，由于 8 位等于 1 字节，所以开辟 1 字节的空间就够了。将这个空间所有位都置 0 ，如图（第一行代表列序号）：

0	1	2	3	4	5	6	7
0	0	0	0	0	0	0	0

然后遍历 5 个元素，因为待排序的第一个元素是 4 ，所以把 4 对应的位置置为 1 。因为从 0 开始计数，所以第 5 位重置为 1 。如下图所示：

0	1	2	3	4	5	6	7
0	0	0	0	1	0	0	0

对待排序的其它元素依次这样处理，最后得到结果：

0	1	2	3	4	5	6	7
0	1	1	1	1	1	0	0

最后遍历这个位区域，将某位是 1 的位的编号（1，2，3，4，5）输出，就达到了排序的目的。

附：位、字符、字节区别

1、计算机存储信息的最小单位，称之为位（bit），音译比特，二进制的一个“0”或一个“1”叫一位。
2、计算机存储容量基本单位是字节（Byte），音译为拜特，8个二进制位组成1个字节，一个标准英文字母占一个字节位置，一个标准汉字占二个字节位置。
3、计算机存储容量大小以字节数来度量，1024进位制：
1024B=1K（千）B
1024KB=1M（兆）B
1024MB=1G（吉）B
1024GB=1T（太）B
以下还有PB、EB、ZB、YB 、NB、DB，一般人不常使用了。
4、字符是一种符号，同以上说的存储单位不是一回事。