如何按字典順序對字符串進行排序？

我有一個字符串文件，我必須按照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

如何按字典順序對字符串進行排序？

回答

相關問題