public static class Program
{
private static Int32 Max(Int32[] a)
{
Int32 max = Int32.MinValue;
foreach (Int32 n in a)
{
if (n > max)
{
max = n;
}
}
return max;
}
public static void CountSort(ref Int32[] a)
{
Int32 max = Max(a);
Int32[] f = new Int32[max + 1];//度数分布表
Int32[] b = new Int32[a.Length];//目的配列
//度数分布表の作成
for (Int32 i = 0; i < a.Length; i++)
{
f[a[i]]++;
}
//累積度数分布表の作成
for (Int32 i = 1; i <= max; i++)
{
f[i] += f[i - 1];
}
//目的配列の作成
for (Int32 i = a.Length - 1; i >= 0; i--)
{
b[--f[a[i]]] = a[i];
}
//元配列にコピー
a = b;
}
static void Main()
{
Random random = new Random();
Int32[] arr = new Int32[1000];
for (Int32 i = 0; i < arr.Length; i++)
{
arr[i] = random.Next() % arr.Length;
}
CountSort(ref arr);
Array.ForEach(arr, (n) => Console.WriteLine(n));
}
}