最近發現一個有趣的排序算法，通過位圖來完成排序。位圖排序其實就是基數排序，只不過位圖排序的下標是比特位。

問題描述

輸入：一個最多包含n個正整數的文件，每個數都小于n，其中n=10^7。如果在輸入文件中有任何正數重復出現就是致命錯誤。沒有其他數據與該正數相關聯。

輸出：按升序排列的輸入正數的列表。

約束：最多有1MB的內存空間可用，有充足的磁盤存儲空間可用。運行時間最多幾分鐘，運行時間為10秒就不需要進一步優化。

一種解決方法是把整個文件分成 40 份，每份 250000 個整數，一個整形占 4 字節，剛好可以在 1MB 的空間里操作。在第一趟遍歷中，將大小為 0 至 249999 之間的任何整數都讀入內存中，并對這 250000 個整數進行排序，寫到輸出文件中。第二趟遍歷排序 250000 至 499999 之間的整數，依此類推，到第 40 趟結束，我們已經完成了排序。這種排序的代價是要讀取輸入文件 40 次。

而另一種解決方法就是使用位圖排序。

位圖排序

一般編程語言的 int 類型所占空間大于等于 4 字節，共 32 位。我們可以用這 32 位來表示 0 到 31 的的數字。假設有一個集合為 {0, 3, 5}，在位圖里表示就是 0000101001 ，這里省去了前面 22 個 0 。

一個 32 位的 int 數可以表示 32 個數字。假設總共有 100 個數，我們只需 (100/32)+1=4 個 int 整數就可以表示這 100 個數，0~31 儲存在第 1 個 int 數，32~63 儲存在第 2 個 int 數。

這樣，存儲所有數值需要的 int 個數為 10^7 / 32 = 312500, 需要總內存為312500 * 4 / 1024 / 1024 = 1.25M, 1M內存限制跑兩趟就可以完成排序。

位圖排序實現

我們可以用 3 個函數來實現位圖。

函數1：將所有的位都置為0，從而將集合初始化為空。

函數2：通過讀入文件中的每個整數來建立集合，將每個對應的位置都置為 1。

函數3：檢驗每一位，如果該為為1，就輸出對應的整數。

位圖操作類

class BitMap:# maxval        最大值# bitsperword   一個int數的位數# shift         能表示 bitsperword 需要的位數, 5 位可以表示 32 這個數# mask          能表示 bitsperword 需要的位數，用二進制表示def __init__(self, maxval, bitsperword=32, shift=5, mask=0b11111):self.bitsperword = bitsperwordself.shift = shiftself.mask = mask# 初始化位圖，相當于函數1self.x = [0 for i in range(1 + int(maxval / bitsperword))]def set(self, i):# i>>self.shift 操作等同于 i 除于 2^self.shift# i & self.mask 操作等同于 i 對 2^self.shift 求余# 1 << n 等同于 1 * 2^nself.x[i >> self.shift] |= (1 << (i & self.mask))# 如果某位上有數，就返回 truedef test(self, i):return self.x[i >> self.shift] & (1 << (i & self.mask))

設置

>>> bit = BitMap(500)
>>> bit.x
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]>>> bit.x
[2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# self.x[0] 的二進制為 10>>> bit.set(4)
>>> bit.x
[18, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# self.x[0] 的二進制為 10010

輸出位對應的值

>>> print (bit.test(1))
2

排序實現

def bitSort(lists, maxval):sortLists = []bit = BitMap(maxval)for val in lists:bit.set(val)for i in range(maxval):if bit.test(i):sortLists.append(i)return sortLists

排序測試

>>> lists = [5, 2, 6, 8, 10, 22, 25, 44, 29, 36, 40, 3, 4, 1, 20, 27, 37]
>>> print (bitSort(lists, max(lists)))
[1, 2, 3, 4, 5, 6, 8, 10, 20, 22, 25, 27, 29, 36, 37, 40]

位圖操作的優點非常明顯，內存占用非常低，非常適合在內存有限時使用。

完整代碼

#!/bin/python
# -*- coding:utf-8 -*-class BitMap:# maxval        最大值# bitsperword   一個int數的位數# shift         能表示 bitsperword 需要的位數, 5 位可以表示 32 這個數# mask          能表示 bitsperword 需要的位數，用二進制表示def __init__(self, maxval, bitsperword=32, shift=5, mask=0b11111):self.bitsperword = bitsperwordself.shift = shiftself.mask = mask# 初始化位圖，相當于函數1self.x = [0 for i in range(1 + int(maxval / bitsperword))]def set(self, i):# i>>self.shift 操作等同于 i 除于 2^self.shift# i & self.mask 操作等同于 i 對 2^self.shift 求余# 1 << n 等同于 1 * 2^nself.x[i >> self.shift] |= (1 << (i & self.mask))# 如果某位上有數，就返回 truedef test(self, i):return self.x[i >> self.shift] & (1 << (i & self.mask))def bitSort(lists, maxval):sortLists = []bit = BitMap(maxval)for val in lists:bit.set(val)for i in range(maxval):if bit.test(i):sortLists.append(i)return sortListsif __name__ == '__main__':lists = [5, 2, 6, 8, 10, 22, 25, 44, 29, 36, 40, 3, 4, 1, 20, 27, 37]print (bitSort(lists, max(lists)))

參考: 編程珠璣