最好的方法来排序一长串字符串

Question

我想知道排序一长串字符串与时间和空间效率的最佳方法。我更喜欢时间效率而非空间效率。

字符串可以是数字，字母，字母数字等。我不喜欢排序行为像字母数字排序v/s字母排序只是排序本身。

以下我可以想到的一些方法。

1. 使用代码例如：.Net框架的Arrays.Sort（）函数。我认为这样做的方式是计算字符串的哈希码，并使用二分搜索将字符串插入到适当的位置。

2. 使用数据库（例如：MS-sql）。我没有这样做。我不知道这将是多么有效。

3. 使用像trie这样的前缀树数据结构。排序需要使用DFS（深度优先搜索） - O（| V | + | E |）时间遍历树树的所有trie节点。 （搜索需要O（l）时间，其中l是要比较的字符串的长度）。

其他任何方式或数据结构？

Answer 1

你说你有一个数据库，可能是字符串存储在数据库中。那么你应该让数据库为你做这项工作。它可能能够利用索引，因此不需要实际对列表进行排序，而只需按照排序顺序从索引中读取它。

如果没有索引，数据库可能仍然可以帮助您。如果您只为某个小的常量数k获取前k行，例如100.当您使用带有LIMIT子句的ORDER BY时，它允许SQL Server使用称为TOP N SORT的特殊优化，该优化以线性时间而不是O（n log （n））时间。

如果您的字符串不在数据库中，那么您应该使用.NET提供的功能。我认为你不可能编写比默认排序快得多的自定义代码。

Answer 2

我找到了this paper，它使用了trie数据结构来有效地对大量字符串进行排序。尽管我没有详细研究过它。

Answer 3

Radix sort也可能是不错的选择，如果琴弦不是很长，例如，名单

Answer 4

让我们假设你有一个字符串的大名单，而且名单长度为N

使用基于像归并，堆排序或快速排序排序算法的比较会给你一个

其中n是列表的大小，d是列表中所有字符串的最大长度。

在这种情况下，我们可以尝试使用基数排序。设b为基数，令d为最大字符串的长度，则我们可以证明使用基数排序的运行时间为。

此外，如果字符串是说，小写英文字母的运行时间是

来源：MIT Opencourse算法讲座教授。 Eric Demaine。