高效自動排序列表python

我想在python中編寫一個list-lie類，當添加數字時它會自動排序。這是爲了好玩，而不是爲了一個班級：p我想知道的是什麼是最有效的方式去做這件事。我應該這樣做嗎？：高效自動排序列表python

class SortedList: 
    def __init__(self, data): 
     self.data = list(data) 

    def add(self, num): 
     self.data.append(num) 
     self.data.sort()

有沒有更好的方法來做到這一點？

來源

2012-09-14 Broseph

-Edit- sort()是O（n log n）。在添加每個數字後，通過排序將n個數字添加到列表中將是O（n^2 log n）（但實際上，這可能比O（n^2）算法快，這取決於排序的優化）。

一個更好的O實現是花O（n）時間來搜索插入位置和O（n）時間來向列表中添加一個新數字（總時間仍然是O（n））。將n個數字添加到列表中將是O（n^2）。代碼如下：

def addFaster(self, num): 
    index = 0 
    if(len(self.data) == 0): 
     self.data = [num] 
    else: 
     for i in range(0, len(self.data)): 
     if(self.data[i] >= num): 
      self.data.insert(i, num) 
      return 
     self.data.append(num)

我們可以通過二進制搜索到O（log n）時間的正確索引的方式做得更好。向列表添加新號碼是O（n）。由於整個操作（比以前更好）O（n），向列表中添加n個數字是O（n^2），具有較低的常量。（不包括代碼）

如果你要在大集團中添加新的號碼，但是，將大大，如果你一次添加他們的所有排序加快算法（使用extend()），然後。然後，在O（n log n）時間（與排序相同的時間）中添加n個數字。

見http://wiki.python.org/moin/TimeComplexity

來源

2012-09-14 05:15:29 irrelephant

對不起，我花了這麼長的時間來接受這個答案，這正是我所期待的。謝謝！ – Broseph

你指定你想實現這個作爲一個列表;你認爲你的數據結構是堆嗎？可能更適合你想要做的事情。

請參閱heapq。

來源

2012-09-14 05:34:34

高效自動排序列表python

回答

相關問題