カウンティングソート

これは、整数の配列または整数をキーとする構造体に使用する並べ替えアルゴリズムです。整数の範囲が入力のサイズのオーダーにある場合に特に便利です。

主なアイデアは、整数の出現頻度を決定し、それを使用して並べ替え順序を決定することです。

例: 配列 {1,3,1,2} を取得するとします。

まず、この入力の整数の範囲、最大と最小、1 と 3 を決定します。

次に配列を作成し、それを counts 配列と呼びます。これは、整数の範囲 + 1 のサイズであるため、この場合は 3 (3-1+1) になります。
入力配列を反復処理して、適切なエントリのカウントをインクリメントします。指定された入力値のカウントは、counts[value - min] に配置されます。指定された入力に対して、counts[0] は値 1 のカウントを保持します。

これにより、カウント配列が生成されます: {2,1,1}

ここで累積カウントを決定します。これは基本的に counts[i] = counts[i-1] + counts[i] です。

これにより、累積カウント配列が生成されます: {2,3,4}

ソートされた入力の出力配列を作成します。

次に、入力を逆の順序で繰り返します。

各ステップで、入力配列内の値の累積カウントを取得します。値は、取得したカウント - 1 に対応する出力配列インデックスに配置されます。その後、累積カウント値をデクリメントします。

最初のステップでは、値 2 が取得され、累積カウントは 3 になります。値は出力のインデックス 2 (3-1) に配置される必要があります。

次の反復では、値 1 と累積カウント 2;したがって、この「1」は出力のインデックス 1 (2-1) に配置されます。

続けて、値 3 と累積カウント 4;それを出力のインデックス 3 に配置します。

最後に、2 回目の値は 1 で、累積カウントは 1 です (カウントは最初に表示されたときにデクリメントされたため)。したがって、この「1」は出力のインデックス 0 に配置されます。

、逆方向に反復することで等しい要素の順序が維持され、並べ替えが「安定」する方法をご覧ください

結果としてソートされた配列は {1,1,2,3} になります

もっと効率的にすることはできますか?以下にコメントや提案を残してください。

ありがとう！

この投稿とこのシリーズのすべての投稿のコードはここにあります

以上がカウンティングソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。