词Lis的词典分类

Question

我需要合并和排序100000多个单词的词汇表。我现在用一个稍微修改过的冒泡排序，但是在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|是要排序的最长字符串的长度。然而，对于所有比较类型来说，这都是正确的——真正的操作数取决于被排序元素类型的元素比较函数的成本。因为所有比较排序都使用相同的比较函数，所以在比较这些排序的算法复杂性时，可以忽略这一微妙之处。