# -*- 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/