基数ソート

概要 「バケットソート」は、 値の範囲が限られた整数限定で、計算量 O(n) で極めて高速にソートを行えるアルゴリズムでした。 ですが、「値の範囲が限られた」が曲者で、用途が非常に限定されてしまいます。 基数ソート（radix sort）は、 この欠点を少しでもマシにした、 「バケットソート」の改良版ともいえるアルゴリズムです。 基数（radix）というのは、10進数の10、16進数の16というように、 桁上がりの基準になる数のことです。 基数ソートの発想は、要するに、 「桁ごとに「バケットソート」を繰り返す」というものです。 そうすることで、必要となるバケツの数を基数分（10進数で1桁ずつソートするなら10個で OK）に抑えられます。 基数ソートでも、もちろん、 ソートできる値の桁数に制限が生じますが、 コンピュータ上で扱える整数の桁なんてたかが知れている （例えば、32ビット整数で、1

[jar2]

C#のサンプルコード付き