使用bitmap实现对一千万个无重复的正整数（范围1~1亿）快速排序

1 Bytes(字节)  == 8 bit

1 KBytes  == 1024 Bytes

思路：

1）申请长度为1亿的保存二进制位的数组 a，

2）通过位运算，将整数做为索引，将数组a对应的索引位置为1。

3）重复步骤2，直到最后一个整数放到数组中

4）从头开始遍历数组a，将值为1的索引id打印出来。

python 提供了bytearray这个动态的字节数据，以下代码就用bytearray实现

class Bitmap:

    def __init__(self, num_bits:int):

        self._num_bits = num_bits

        self._bytes = bytearray(num_bits // 8 +1)

    def setbit(self, k:int) ->None:

        if k > self._num_bits or k < 1:

            return None

        # 通过位左移和 或运算可以将对应的bit置为1

        self._bytes[k//8] |= (1<<k %8)

    def getbit(self, k:int)->Optional[bool]:

        if k > self._num_bits or k < 1: return

        return self._bytes[k // 8] & (1 << k % 8) != 0