单词列表的词典排序

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|)

然而,排序字符串可以在完成O(n*|S|)其中|S|是平均字符串的长度,使用字典树,和一个简单的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.