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