algorithm
並べ替えを数える
サーチ…
基本情報をソートする
カウントソートは、オブジェクトのキーに従ってソートするオブジェクトのコレクションの整数ソートアルゴリズムです。
ステップ
- 入力配列Aの範囲に等しいサイズを持つ作業配列Cを構築します。
- Aを反復し、 Aに現れた回数xに基づいてC [x]を代入する 。
- Cを配列に変換する。ここで、 C [x]は配列を反復して、各C [x]の前の値とその前のCのすべての値の合計を代入して値xの数を参照する。
- Aを通って後方に反復し、各値をCで記録されたインデックスの新しいソート済み配列Bに配置します。これは、B [C [A [X]]] [X]、及びCをデクリメントする[Aが [X]の場合に重複した値が元のソートされていない配列であったを割り当てることによって、[X]所与のために行われます。
並べ替えソートの例
補助空間: O(n+k)
時間複雑度:最悪ケース: O(n+k)
、最良ケース: O(n)
、平均ケースO(n+k)
擬似コード実装
制約:
- 入力(ソートされる配列)
- 入力要素数(n)
- 0..k-1 (k)の範囲のキー
- カウント(数値の配列)
擬似コード:
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;
}
}
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow