string 高效的字符串排序算法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/6972635/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Efficient string sorting algorithm
提问by Piotr Turek
Sorting strings by comparisons (e.g. standard QuickSort + strcmp-like function) may be a bit slow, especially for long strings sharing a common prefix (the comparison function takes O(s) time, where s is the length of string), thus a standard solution has the complexity of O(s * nlog n). Are there any known faster algorithms?
通过比较对字符串进行排序（例如标准 QuickSort + strcmp 类函数）可能有点慢，特别是对于共享公共前缀的长字符串（比较函数需要 O(s) 时间，其中 s 是字符串的长度），因此标准解的复杂度为 O(s * nlog n)。有没有已知的更快的算法？
回答by phimuemue
If you know that the string consist only of certain characters (which is almost always the case), you can use a variant of BucketSortor RadixSort.
如果您知道字符串仅由某些字符组成（几乎总是如此），您可以使用BucketSort或RadixSort的变体。
回答by Oliver Charlesworth
回答by Stefan Savev
Please search for "Sedgewick Multikey quick sort" (Sedgewick wrote famous algorithms textbooks in C and Java). His algorithm is relatively easy to implement and quite fast. It avoids the problem you are talking above. There is the burst sort algorithm which claims to be faster, but I don't know of any implementation.
请搜索“Sedgewick Multikey quick sort”（Sedgewick 用 C 和 Java 编写了著名的算法教科书）。他的算法相对容易实现并且速度相当快。它避免了你上面所说的问题。有声称更快的突发排序算法，但我不知道任何实现。
There is an article Fast String Sort in C# and F#that describes the algorithm and has a reference to Sedgewick's code as well as to C# code. (disclosure: it's an article and code that I wrote based on Sedgewick's paper).
有一篇文章C# 和 F#中的快速字符串排序描述了算法，并引用了 Sedgewick 的代码以及 C# 代码。（披露：这是我根据 Sedgewick 的论文写的一篇文章和代码）。
