字詞列表的字典排序

Question

我需要按照字典順序對100,000多個單詞的列表進行合併和排序。我現在用一個稍微修改過的冒泡排序來做，但是在O（n^2）它需要很長時間。有沒有更快的算法來排序單詞列表？我使用Python，但是如果有一種語言可以更好地處理這個問題，我很樂意提供建議。

Answer 1

任何O(nlogn)sorting algorithm可能會做的更好，然後冒泡排序，但他們會O(nlogn * |S|)

然而，排序字符串可以在O(n*|S|)來完成，其中|S|是平均字符串的長度，使用trie，和簡單的DFS。

高級別僞代碼：

1. create a trie from your collection. 
2. do a DFS on the trie generated, and add each string 
    to the list when you reach terminal node. 

Answer 2

使用內置sort()列表方法：

>>> words = [ 'baloney', 'aardvark' ] 
>>> words.sort() 
>>> print words 
['aardvark', 'baloney'] 

它採用了O(n lg(n))排序的Timsort（。這是一個修改合併排序，我認爲這是非常適應的速度） 。

---

如在評論中指出，這是指元件的比較的數量，而不是低級別的操作的數量。由於這種情況下的元素是字符串，並且比較兩個字符串需要min{|S1|, |S2|}個字符比較，所以總複雜度爲O(n lg(n) * |S|)，其中|S|是要排序的最長字符串的長度。但是，所有比較排序都是如此 - 操作的真實數量取決於要排序的元素類型的元素比較函數的成本。由於所有比較排序都使用相同的比較函數，所以在比較這些排序的算法複雜性時，您可以忽略這種細微差別。