这个Python模块是否能计算数据结构的有序插入,还是先插入然后排序?由于需要牢记内存问题来开发算法,因此需要一种在列表中正好插入的方法,就像Java使用LinkedList一样,但不确定应该使用什么和如何使用。任何帮助都将不胜感激。
该函数将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)
。
append
(列表中的方法)将属性插入到列表末尾,然后按照该属性作为键进行排序。 - Dani Mesejo