# -*- coding: utf-8 -*-
# python:2.x
__author__ = 'Administrator'
#bisect
#作用：维护有序列表，而不必在每次向列表增加一个元素时都调用sort()排序
#版本:1.4及之后
#其他：实现了一个算法用于向列表中插入元素，同时保持列表有序，有些情况下，这比反复对一个列表排序更高效，另外也比构建一个大列表之后显示对基排序更高效
#有序插入
#insort()按有序顺序向一个列表中插入元素
import bisect,random
random.seed(1)
# Use a constant see to ensure that we see
# the same pseudo-random numbers each time
# we run the loop.
print 'new pos contents'
print '--- --- -------'
# Generate 20 random numbers and
# insert them into a list in sorted
# order.
l = []
for i in range(1, 20):
r = random.randint(1, 100)
position = bisect.bisect(l, r)
bisect.insort(l, r)
print '%3d %3d' % (r, position), l
#处理重复
#bisect提供了2种方法来处理重复，亲传以插入到现有值的左边或者右边，insort()实际上是insort_right()另外，这个函数会在现有值之后插入新值，对应的insort_left()则会在现有值之前插入新值
# Reset the seed
random.seed(1)
# Use bisect_left and insort_left.
print 'new pos contents'
print '--- --- -------'
l=[]
for i in range(1,15):
r=random.randint(1,100)
position = bisect.bisect_left(l, r)
bisect.insort_left(l, r)
print '%2d %2d' % (r, position), l
#官方文档：https://docs.python.org/2.7/library/bisect.html?highlight=bisect#bisect
#对这部分算法讨论：http://pymotw.com/2/articles/data_structures.html#article-data-structures
#更多标准库有关例子 ：http://pymotw.com/2/