python bisect.insort(列表，值)

Question

这个python模块是计算数据结构中的有序插入，还是先插入然后排序？自从开发了一种算法以来，我就一直在努力解决python中的这种事情，在这种算法中，我必须记住内存问题，因此需要一种方法来插入到列表中的正确位置，因为在java中应该使用linkedlist来完成插入，但不确定使用什么以及如何使用。

任何帮助都将不胜感激。

Answer 1

将value插入到list中的正确位置，请注意，它假定已经排序。从文档中：

按排序顺序插入x。这等同于假设a已经排序的a.insert(bisect.bisect_left(a, x, lo, hi), x)。请记住，O(log )搜索是由缓慢的O(n)插入步骤主导的。

最后一部分提到了在Python列表上插入是O(n)的事实。搜索是使用binary search完成的。

如果您从一个空列表开始，并重复使用此算法将对象插入到列表中，则最终的列表将被排序。这种算法称为binary insertion sort。例如：

import bisect

l = [1, 3, 7, 5, 6, 4, 9, 8, 2]

result = []
for e in l:
    bisect.insort(result, e)

print(result)

输出

[1, 2, 3, 4, 5, 6, 7, 8, 9]

注意：这个算法的复杂度是O(n*n)，给定了O(n)插入步骤。