python - 替代 python 的 .sort() (用于插入大列表并保持排序)

Question

我需要不断地向预先排序的列表中添加数字:

for num in numberList:
    list.append(num)
    list.sort()

每次迭代都很短，但是当给定的 numberList 包含数万个值时，此方法会变慢。是否有更有效的函数可以使列表保持原样并找出插入新数字的索引以保持数字的正确顺序？我自己尝试编写的任何东西都比 .sort() 花费的时间更长

Answer 1

您可以使用 bisect.insort() function将值插入到已排序的列表中:

from bisect import insort

insort(list, num)

请注意，这仍然需要一些时间，因为插入点之后的剩余元素都必须向上移动一步；您可能需要考虑将列表重新实现为链表。

但是，如果您保持列表排序只是为了始终能够获得最小或最大的数字，您应该使用 heapq module反而;堆没有按照严格的排序顺序保存，但在任何时候都能非常快速地为您提供最小值或最大值。