python - 如何在 Python 中输入数据时保持排序列表

Question

我有一个列表列表，需要根据列表的长度进行排序。我现在要做的就是首先将列表插入到主列表中，然后对主列表进行排序，给出key=len。此步骤总共需要 n + nlg(n) 时间。在将数据输入主列表时是否可以维护排序列表？可以使用二等分来完成吗(或者有没有更好的方法)，如果可以的话，它的性能会比n + nlg(n)更好吗？

Answer 1

这取决于您使用的数据结构:

• Dynamic Array
  • 使用二分法在排序数组上查找正确的索引的时间复杂度为O(log n)
  • 插入的时间复杂度为O(n)，因为您必须移动所有内容
  • 总计“O(n)”
• Linked List
  • 要在已排序的链表上查找正确的索引，需要浏览该列表直到到达那里。 (O(n))
  • 插入操作很简单，只需 O(1)。
  • 总计 O(n)
• Self-balancing BST
  • 边维持订单边插入，余额O(log n) 摊销
  • this question 中有实现的链接
• Heap 。不完全符合您的要求，但插入堆是 O(log n) 或 Theta(1) ，具体取决于您使用的实现。 heapq python 中是一种实现。您只需将项目推送到堆中，完成后，您就可以在 O(n) 内获得排序结果。同时，您可以在 O(1) 内访问树的根，并在 O(k) 内访问 k 个最小的排序后的树。