python - 如何在阅读元素时保持列表排序

Question

将元素读入列表并保持列表排序与在现有排序列表中搜索新元素的位置并插入其中的有效方法是什么？

Answer 1

使用专门的数据结构，在 Python 中，您可以使用bisect模块：

该模块支持以排序顺序维护列表，而无需在每次插入后对列表进行排序。对于具有昂贵比较操作的长列表项目，这可能是对更常见方法的改进。调用该模块是bisect因为它使用基本的二分算法来完成其工作。

Answer 2

您正在寻找heapq.

该模块提供了堆队列算法的实现，也称为优先队列算法。

Answer 3

@Aswin 的评论很有趣。如果每次插入项目时都进行排序，则调用sort()是 O(n) 而不是通常的 O(n*log(n))。这是由于 sort(timsort) 的实现方式。

但是除此之外，您还需要沿列表移动一堆元素以腾出空间。这也是 O(n)，所以总的来说 -.sort()每次调用都是 O(n)

没有办法让排序列表保持比 O(n) 更好，因为总是需要这种转换。

如果您不需要实际列表，heapq（如@Ignacio 的回答中所述）通常会以有效的方式涵盖您确实需要的属性。

否则，您可能会发现许多树数据结构中的一种比列表更适合您的原因。