python bisect.insort（列表，值）

Question

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

任何帮助将不胜感激。

Answer 1

此插入 value 到 list 的正确位置，请注意，它假设已经排序。来自文档：

Insert x in a in sorted order. This is equivalent to a.insert(bisect.bisect_left(a, x, lo, hi), x) assuming that a is already sorted. Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

最后一部分是指 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) 插入步骤，此算法的复杂度为 O(n*n)。

python bisect.insort（列表，值）

python bisect.insort(list, value)

python

module

list

insert

bisect