カウンティングソート

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

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

例: 配列 {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} です

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min+1)
    for _, v := range in {
        counts[v-min]++
    }
    // determine cumulative counts
    for i := 1; i < len(counts); i++ {
        counts[i] = counts[i-1] + counts[i]
    }
    // create the output array
    out := make([]int, len(in))
    for i := range in {
        v := in[len(in)-1-i]
        out[counts[v-min]-1] = v
        counts[v-min]--
    }
    return out
}

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

ありがとうございます!

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

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