Python的bisect模块是内置模块，bisect模块实现了一个算法用于插入元素到有序列表。
在一些情况下，这比反复排序列表或构造一个大的列表再排序的效率更高。Bisect是二分法的意思，这里使用二分法排序，将待插入的元素插入到合适的位置
bisect模块提供了如下几个函数：
（下面函数中的lo和hi用于指定列表的区间，默认的是整个列表）
bisect.bisect_left(a, x, lo=0, hi=len(a)) 返回将x插入到列表a中的索引位置，如果已有x，则返回第一个x的位置
bisect.bisect_right(a, x, lo=0, hi=len(a)) 返回将x插入到列表a中的索引位置，如果已有x，则返回最后一个x位置的下一个位置
bisect.bisect(a, x, lo=0, hi=len(a)) 与bisect_right相同
bisect.insort_left(a, x, lo=0, hi=len(a)) 将x插入到列表a中，如果已有x，插入到所有x的最左边
bisect.insort_right(a, x, lo=0, hi=len(a)) 将x插入到列表a中，如果已有x，插入到所有x的最右边
bisect.insort(a, x, lo=0, hi=len(a)) 与insort_right相同
下面看个例子：
- >>> import bisect
- >>> import random
- >>> mylist = list()
- >>> for i in range(10):
- num = random.randint(1,100)
- index = bisect.bisect_left(mylist, num)
- bisect.insort_left(mylist, num)
- print('num ', str(num), '\tindex ', str(index), '\tlist ', mylist)
- num 37 index 0 list [37]
- num 31 index 0 list [31, 37]
- num 82 index 2 list [31, 37, 82]
- num 27 index 0 list [27, 31, 37, 82]
- num 62 index 3 list [27, 31, 37, 62, 82]
- num 83 index 5 list [27, 31, 37, 62, 82, 83]
- num 83 index 5 list [27, 31, 37, 62, 82, 83, 83]
- num 87 index 7 list [27, 31, 37, 62, 82, 83, 83, 87]
- num 98 index 8 list [27, 31, 37, 62, 82, 83, 83, 87, 98]
- num 99 index 9 list [27, 31, 37, 62, 82, 83, 83, 87, 98, 99]
- >>> mylist = list()
- >>> for i in range(10):
- num = random.randint(1,100)
- index = bisect.bisect_right(mylist, num)
- bisect.insort_right(mylist, num)
- print('num ', str(num), '\tindex ', str(index), '\tlist ', mylist)
- num 85 index 0 list [85]
- num 73 index 0 list [73, 85]
- num 82 index 1 list [73, 82, 85]
- num 36 index 0 list [36, 73, 82, 85]
- num 80 index 2 list [36, 73, 80, 82, 85]
- num 4 index 0 list [4, 36, 73, 80, 82, 85]
- num 79 index 3 list [4, 36, 73, 79, 80, 82, 85]
- num 6 index 1 list [4, 6, 36, 73, 79, 80, 82, 85]
- num 64 index 3 list [4, 6, 36, 64, 73, 79, 80, 82, 85]
- num 25 index 2 list [4, 6, 25, 36, 64, 73, 79, 80, 82, 85]
- >>> mylist = list()
- >>> for i in range(10):
- num = random.randint(1,100)
- index = bisect.bisect(mylist, num)
- bisect.insort(mylist, num)
- print('num ', str(num), '\tindex ', str(index), '\tlist ', mylist)
- num 25 index 0 list [25]
- num 28 index 1 list [25, 28]
- num 81 index 2 list [25, 28, 81]
- num 9 index 0 list [9, 25, 28, 81]
- num 29 index 3 list [9, 25, 28, 29, 81]
- num 66 index 4 list [9, 25, 28, 29, 66, 81]
- num 34 index 4 list [9, 25, 28, 29, 34, 66, 81]
- num 60 index 5 list [9, 25, 28, 29, 34, 60, 66, 81]
- num 61 index 6 list [9, 25, 28, 29, 34, 60, 61, 66, 81]
- num 3 index 0 list [3, 9, 25, 28, 29, 34, 60, 61, 66, 81]