1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#_*_coding=utf-8_*_
'''常见数据结构-bitmap（位图）'''
 
class  Bitmap:
     '''初始化'''
     def  __init__( self , max ):
         '''#计算需要多少个数组的数量'''
         self .size  =  int (( max  +  31 - 1 )  /  31 )
         '''为每个数组生成单元，每个单元存储为0'''
         self .array  =  [ 0  for  i  in  range ( self .size)]
 
     def  bitindex( self ,num):
         '''位索引，这个方法求余的操作就是判断某个数在某个数组中的具体的第几位'''
         return   num  %  31
 
     def  set ( self ,num):
         '''计算到某个数对应在位图中的哪个数之后，需要将对应的位置成1'''
 
         '''#判断需要计算的数字具体是在哪个数组中'''
         elemindex  =  num  /  31
         '''#表示计算数的位索引'''
         byteindex  =  self .bitindex(num)
         '''#选择哪个数组进行操作'''
         elem  =  self .array[elemindex]
 
          #逻辑或，进行置1的操作，1向左移动了byteindex位
         self .array[elemindex]  =  elem | ( 1  << byteindex)
 
     def  test( self ,i):
         '''#判断对应的数字在第几个数组上'''
         elemindex  =  i  /  31
         '''#进行位索引'''
         byteindex  =  self .bitindex(i)
         '''#逻辑与操作，判断某一位到底在不在bitmap上，如果在就代表着应该取出并遍历出来，遍历的时候出现1的位置就将这个位置上的数转换为十进制然后取出来，依次遍历生成排序序列'''
         if  self .array[elemindex] & ( 1  << byteindex):
             return  True
         return  False
 
if  __name__  = =  "__main__" :
     '''将z转换为assci码最大的数'''
     MAX  =  ord ( 'z' )
     suffle_array  =  [x  for  x  in  'coledraw' ]
     result  =  []
     '''#调用这个类，将最大数的传递给它。生成位图表'''
     bitmap  =  Bitmap( int ( MAX ))
 
     '''分别遍历这个数组'''
     for  c  in  suffle_array:
         bitmap. set ( ord (c))
     for  i  in  range ( int ( MAX )  +  1 ):
         '''#存在1的话，就取出数据'''
         if  bitmap.test(i):
             '''#存储到列表里'''
             result.append( chr (i))
 
     print ( "原始数组: %s"  %  suffle_array)
     print ( "排序后数组: %s"  %  result)