python - 词表的字典排序

Question

我需要按字典顺序合并和排序 100,000 多个单词的列表。我目前使用稍微修改的冒泡排序来做到这一点，但在 O(n^2) 时需要相当长的时间。有没有更快的算法来排序单词列表？我正在使用 Python，但如果有一种语言可以更好地处理这个问题，我愿意接受建议。

Answer 1

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

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

它使用O(n lg(n))排序¹，即Timsort（我相信这是一种修改过的合并排序。它针对速度进行了高度调整。）。

---

¹正如评论中所指出的，这是指元素比较的次数，而不是低级操作的次数。由于这种情况下的元素是字符串，并且比较两个字符串需要进行min{|S1|, |S2|}字符比较，所以总复杂度是O(n lg(n) * |S|)被|S|排序的最长字符串的长度。然而，所有比较排序都是如此——真正的操作数取决于被排序元素类型的元素比较函数的成本。由于所有比较排序都使用相同的比较函数，因此在比较这些排序的算法复杂度时，您可以忽略这种微妙之处。

Answer 2

任何O(nlogn) 排序算法都可能比冒泡排序做得更好，但它们会O(nlogn * |S|)

但是，可以使用trie和简单的DFS对字符串进行排序，O(n*|S|)其中|S|是平均字符串的长度。

高级伪代码：

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.