algorithm
並べ替えを数える

基本情報をソートする

カウントソートは、オブジェクトのキーに従ってソートするオブジェクトのコレクションの整数ソートアルゴリズムです。

ステップ

1. 入力配列Aの範囲に等しいサイズを持つ作業配列Cを構築します。
2. Aを反復し、 Aに現れた回数xに基づいてC [x]を代入する 。
3. Cを配列に変換する。ここで、 C [x]は配列を反復して、各C [x]の前の値とその前のCのすべての値の合計を代入して値xの数を参照する。
4. Aを通って後方に反復し、各値をCで記録されたインデックスの新しいソート済み配列Bに配置します。これは、B [C [A [X]]] [X]、及びCをデクリメントする[Aが [X]の場合に重複した値が元のソートされていない配列であったを割り当てることによって、[X]所与のために行われます。

並べ替えソートの例

補助空間： O(n+k)
時間複雑度：最悪ケース： O(n+k) 、最良ケース： O(n) 、平均ケースO(n+k)

擬似コード実装

制約：

1. 入力（ソートされる配列）
2. 入力要素数（n）
3. 0..k-1 （k）の範囲のキー
4. カウント（数値の配列）

擬似コード：

for x in input:
    count[key(x)] += 1
total = 0
for i in range(k):
    oldCount = count[i]
    count[i] = total
    total += oldCount
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1
return output

C＃の実装

public class CountingSort
{
    public static void SortCounting(int[] input, int min, int max)
    {
        var count = new int[max - min + 1];
        var z = 0;

        for (var i = 0; i < count.Length; i++)
            count[i] = 0;

        foreach (int i in input)
            count[i - min]++;

        for (var i = min; i <= max; i++)
        {
            while (count[i - min]-- > 0)
            {
                input[z] = i;
                ++z;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortCounting(input, input.Min(), input.Max());
        return input;
    }
}