如何在Python中输入数据时保留排序列表

Question

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

Answer 1

这取决于正在使用的数据结构：

• Dynamic Array
  • 排序后的数组上找到合适的指数使用平分
  • 插入是O(n)因为你必须转移O(log 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中的heapq是一个实现。您可以在堆中简单地推送项目，并在完成后，可以在O(n)中获得排序结果。同时，您可以访问O(1)中的树的根目录，并且在O(k)中的k最小，排序。