using System;
using System.Collections.Generic;
public static class Program
{
public static void RadixSort(ref Int32[] a)
{
const Int32 M = ushort.MaxValue;
const Int32 MASK = ushort.MaxValue;
Int32[] f = new Int32[M + 1];
Int32[] b = new Int32[a.Length];
//下位から上位に向かって、16ビットずつ2回ループを実行する
for (Int32 bit = 0; bit < 32; bit += 16)
{
//累積度数分布表をゼロクリア
for (Int32 i = 0; i < f.Length; i++)
{
f[i] = 0;
}
//キーの数え上げ
for (Int32 i = 0; i < a.Length; i++)
{
f[(a[i] >> bit) & MASK]++;
}
//数え上げたキーの累積度数分布表を作成
for (Int32 i = 1; i <= M; i++)
{
f[i] += f[i - 1];
}
//目的配列を作成
for (Int32 i = a.Length - 1; i >= 0; i--)
{
b[--f[(a[i] >> bit) & MASK]] = a[i];
}
//目的配列を元の配列をコピー
for (Int32 i = 0; i < a.Length; i++)
{
a[i] = b[i];
}
}
}
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;
}
RadixSort(ref arr);
Array.ForEach(arr, (n) => Console.WriteLine(n));
}
}