我有一个排序列表L，我有一个二进制搜索，用于确定列表中插入元素的位置，以便结果列表仍然按顺序排列。
然而，L.insert（索引，对象）需要O（N）时间复杂度。
L的另一个数据结构是否可以用于相同的目的，但允许更快的插入？
检查blist模块。
https://pypi.python.org/pypi/blist/
它声称O（log n）插入。
用法：
x = #list contents
y = blist(x)
y.insert(index, object) #now works in O(log n)
向sortedcontainers.SortedList喊道。这将使您的列表自动保持顺序，并且插入时间快。
from sortedcontainers import SortedList
mylist = SortedList([1, 2, 4, 5])
mylist.add(3)
mylist
#>>> SortedList([1, 2, 3, 4, 5], load=1000)
SortedList insertions are amortized O(sqrt n), or O(cbrt n) with different choices of parameters,但它比blist更好地扩展，这是O(log n)，因为常数要好得多。有a very in-depth look at performance on their website。
或者，您可能想要一个priority queue，在这种情况下，您可以使用the heapq module获得可能更快的插入。