ソート可変長項目/アルゴリズム

Question

私はアルゴリズムの中期のために勉強していると私は可変長項目を並べ替えについて出くわした本の中で、この質問があります：

• あなたは文字列の配列を与えられているが、異なる文字列の文字数が異なる場合がありますが、すべての文字列の文字数の合計はnです。 O（n）時間に文字列をソートする方法を示します。

私は多くの回答をオンラインで見つけましたが、その説明ではあまり明確ではありませんでしたので、この回答が示唆していることを私にもっと深く説明する時間があれば本当に感謝します。 O（n）の中の文字列時間：

1. グループ長さの文字列やグループに
2. 開始を注文し、私の最大の長さにして1まで行くには、i番目の文字の上に 並べ替えを数える行います。 i番目の文字が のグループのみを含めるようにしてください。あなたが最初の数字でソート開始

   ：簡単な言葉でhttps://en.wikipedia.org/wiki/Radix_sort

   ： グループは元の配列内の後続のサブアレイがある場合、我々は

Answer 1

を実行しているこれがために、あなたが探しているものです弦の これは、各要素を他の要素と比較する必要がないため、1回のパスO（N）で実行できます。配列内の値の各グループの開始位置と終了位置を覚えておくだけで済みます。例えば、 'g'で始まるすべての文字列は、配列の位置35から500にあります。 'g'で始まる文字列を見つけたら、このグループの最後に追加します。

次のフェーズでは、これらのグループごとに同じ処理を行います。

ご覧のとおり、Mは文字列の長さで、Nは文字列の数ですが、O（M * N）が必要です。 あなたの場合、Nはすべての文字列の合計長さなので、O（N）です。

長さの異なる文字列があるにもかかわらず、短すぎるいくつかのポイント項目では再ソートする必要がないため、O（N）は保持できます。