長さNの配列は値1,2,3 ... N ^ 2を含むことができます。それはO（n）の時間でソートすることは可能ですか？

Question

これは、1からN ^ 2の範囲の値を含むことができる長さNの配列を指定（N平方）の両方含め、値は一体です。それはO（N）時間で、この配列をソートすることは可能ですか？可能な場合はどのように？

編集：これは宿題ではありません。

Answer 1

各Xは、X = 1 + X1 + X2 * Nと（X1、X2）として表すことができ、ある基地N、の各整数を書きます。今、あなたは、ソートされた配列で、その結果、一度X1上とx2に一度、ソートカウントで二回、それを並べ替えることができます。

Answer 2

はい、することができます、使用して基数ソートするとのN バケツと二つのパス。基本的に、あなたはのN のベースで2桁の数字を持つものとして数字を扱います。

Answer 3

は基数ソートの使用O(n)時間で明確に定義された最大値を持つ整数の任意の配列をソートすることが可能ですに。これはおそらく、あなたが遭遇した整数の任意のリストの場合です。あなたは、任意精度の整数のリストを並べ替えた場合例えば、それは真実ではないでしょう。しかし、すべてのC整数型が固定範囲を明確に定義されています。