python bisect.insort(list, value)

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)。