python bisect.insort(list, value)

Question

9

这个Python模块是否能计算数据结构的有序插入，还是先插入然后排序？由于需要牢记内存问题来开发算法，因此需要一种在列表中正好插入的方法，就像Java使用LinkedList一样，但不确定应该使用什么和如何使用。任何帮助都将不胜感激。

- jupcan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dani Mesejo · Accepted Answer

该函数将value插入到一个已排序的list中的正确位置，需要注意的是此函数假定该列表已经排序。根据文档：

将x以排序顺序插入到a中。这相当于假设a已经排序：a.insert(bisect.bisect_left(a, x, lo, hi), x)。请记住，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)的插入步骤，该算法的复杂度为O(n*n)。