在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)，这取决于您使用的实现。^python中的{a6}就是一个实现。您可以在堆中简单地推送项，完成后，可以在O(n)中获得排序结果。同时，您可以在O(1)中访问树的根，在O(k)中访问k最小的排序树。你知道吗