如何按字典顺序对字符串进行排序？

我有一个字符串文件，我必须按照O（nlog（n））或更少的时间以字典顺序对它们进行排序。我知道排序算法并将它们用于排序数字。但我不知道如何使用快速排序或任何其他排序算法来排序字符串。请提供未在方法中构建的算法。如何按字典顺序对字符串进行排序？

来源

2014-04-21 vivek

必须使用？在PHP中简单的'sort'函数将按字母顺序对字符串进行排序。 –

任何语言！我只想知道算法或方法。 – vivek

如果你必须创建你自己的功能。比如，你可以给这封信分配一个数字。在某些语言中有这样的标准功能。 –

对于字符串，共同建议，可能是radix sort

它严格取决于字母表这是用于形成串并O(kN)时间复杂度，其中n是数密钥和k是平均密钥长度。请注意，这可能会产生混淆与O(n log n)来比较这（其中n意味着输入元素数）

所以 - 较小的是k，更好的是基数排序方法。这意味着，对于较小的基数，它会更有效。我只想引用扩展的解释（无需改换）：

基数效率的排序比其他排序算法0的主题是有点棘手，并受到相当多的误解。基数排序是否等效，是否比基于比较的最佳算法效率更低或效率更高取决于所作假设的细节。基数排序效率对于n个具有小于或等于数字的键的O（d·n）。有时d是作为一个常数表示，这将使得基数排序比基于比较的最佳排序算法更好（对于足够大的n），这些算法都需要进行O（n·log（n））个比较。但是，一般来说d不能被认为是一个常数。特别是，在普通（但有时是隐含的）假设下，所有密钥都是不同的，所以d必须至少为log（n）的顺序，这给出最好（具有密集打包的密钥）时间复杂度为O （N·的log（n））。那似乎使得基数排序与最好的基于比较的排序（如果密钥远远长于 log（n））相比最高效。

此外，该算法会使用一些额外的空间（与价值空间复杂O(k+n)） - 因此，你应该意识到这一点（不喜欢，不会使用额外的空间比较算法）什么语言你

来源

2014-04-21 11:06:08

感谢您的好评。我希望这是我的解决方案。让我试试/ – vivek

你看看字母的数值（ASCII值）并用它们来做数字顺序。

所以你看一个字从左到右。如果字母匹配，你看第二等

来源

2014-04-21 10:58:58 rethab

之前的数组中，那么字符串将成为一组数字。以及分配了大于9的数字的字母是什么？ – vivek

我不明白你的问题。字母表如何分配数字？来自流行语言的排序算法通常声明他们使用例如ASCII。 – rethab

如何按字典顺序对字符串进行排序？

回答

相关问题