Ein Array der Länge N kann Werte 1,2,3 ... N ^ 2 enthalten. Ist es möglich, in O (n) Zeit zu sortieren?

Question

ein Array mit der Länge N. Da es Werte von im Bereich von 1 bis N enthalten kann ^ 2 (N zum Quadrat), beide eingeschlossen, Werte integral sind. Ist es möglich, diese Anordnung in O (N) Zeit zu sortieren? Wenn möglich, wie?

Edit:. Dies ist keine Hausaufgaben

Answer 1

Schreibe jede ganze Zahl in der Basis N, die jedes x ist, kann als (x1, x2) dargestellt werden, mit x = 1 + x1 + x2 * N. Jetzt können Sie sie sortieren zweimal Art mit Zählen, einmal auf x1 und einmal auf x2, was im sortierten Feld.

Answer 2

Ja, können Sie mit Hilfe Radixsort mit N Eimer und zwei Pässe. Grundsätzlich behandeln Sie die Zahlen als mit 2 Ziffern in der Basis N .

Answer 3

Es ist möglich, jedes Array von ganzen Zahlen mit einem gut definierten Maximalwert in O(n) Zeit zu sortieren, mit einem Radixsort . Dies ist wahrscheinlich der Fall für jede Liste von ganzen Zahlen auftreten. Zum Beispiel, wenn Sie erhielten eine Liste mit beliebiger Genauigkeit Integer Sortierung wäre es nicht wahr sein. Aber alle die C haben integrale Typen gut definierten festgelegten Bereichen.