In [2]:
import bisect
In [3]:
values = [23, 1, 54, 34, 56]
In [4]:
lst = []
for item in values:
index = bisect.bisect(lst, item) # bisect返回item准备插入的索引位置
bisect.insort(lst, item) # insort方法将item插入到lst中的合适位置
print('{:3} {:3}'.format(item, index), lst)
23 0 [23] 1 0 [1, 23] 54 2 [1, 23, 54] 34 2 [1, 23, 34, 54] 56 4 [1, 23, 34, 54, 56]
bisect 返回元素在插入 lst 后的索引位置，这个时候还没有进行插入操作，
只是预先获知应该插入的位置
insort 方法将数据插入到列表的合适位置上。
可以看到，每一次插入数据，列表都保持着有序的特性，
虽然可以在全部插入后进行一次 sort 排序，但中间过程如果也需要有序的话，
使用 bisect 最为合适。
除了 insort 方法外，bisect 还提供了 insort_left 方法和 insort_right 方法，
他们用来处理重复数据，插入重复数据时，insort_left 会在重复数据的左侧插入，
insort_right 在重复数据的右侧插入，insort 是 insort_right 的别名。
虽然提供了这两种方法，但看不出这两个方法有什么特别的用处，
毕竟重复数据的位置对于列表的最终结果没有任何影响。
bisect 实现原理
这种算法的实现原理非常简单，因为列表始终保持有序，因此只需要使用二分查找法， 就可以快速定位到需要插入的位置，源码如下：
In [5]:
def insort_right(a, x, lo=0, hi=None):
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if x < a[mid]: hi = mid
else: lo = mid+1
a.insert(lo, x)