python - python bisect.insort（列表，值）

Question

这个python模块是计算一个数据结构的有序插入还是先插入然后排序？自从开发了一种算法以来，我一直在 python 中与这种事情作斗争，我必须牢记内存问题，因此需要一种方法在正确的位置插入列表，因为它应该在 java 中使用链表而不是确定使用什么以及如何使用。

任何帮助都感激不尽。

Answer 1

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

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

最后一部分是指在 Python 列表上的插入是O(n). 搜索是使用二分搜索完成的。

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

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)