如何在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最小，排序。