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

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

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



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

ありがとう！

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