string - 効率的な文字列並べ替えアルゴリズム

Question

比較による文字列の並べ替え（たとえば、標準のQuickSort + strcmpのような関数）は、特に共通のプレフィックスを共有する長い文字列の場合（比較関数はO（s）時間かかります。ここで、sは文字列の長さです）、少し遅くなる可能性があります。標準ソリューションの複雑さはO（s * nlog n）です。既知のより高速なアルゴリズムはありますか？

Answer 1

文字列が特定の文字のみで構成されていることがわかっている場合 (ほとんどの場合そうです)、BucketSortまたはRadixSortのバリアントを使用できます。

Answer 2

あなたはトライを作ることができます、それはそうあるべきだとO(s*n)私は信じています。

Answer 3

「Sedgewick マルチキー クイック ソート」で検索してください (Sedgewick は C と Java で有名なアルゴリズムの教科書を書いています)。彼のアルゴリズムは実装が比較的簡単で、非常に高速です。上で話している問題を回避します。より高速であると主張するバーストソートアルゴリズムがありますが、実装については知りません。

C# および F# での Fast String Sortという記事があり 、アルゴリズムについて説明し、Sedgewick のコードと C# コードへの参照があります。(開示: Sedgewick の論文に基づいて私が書いた記事とコードです)。