Sortieren durch Zählen mit Wiederherstellung der Reihenfolge

Java Hard sorting

Aufgabe «Sortieren durch Zählen mit Wiederherstellung der Reihenfolge»

Gegeben ist ein Array von ganzen Zahlen. Es muss aufsteigend sortiert werden, unter Verwendung des Counting-Sort-Algorithmus. Bei gleichen Elementwerten muss jedoch ihre ursprüngliche relative Reihenfolge beibehalten werden (stabile Sortierung). Geben Sie das sortierte Array aus. Einschränkungen: Die Länge des Arrays beträgt 1 bis 10^5, die Werte der Elemente liegen zwischen -10^4 und 10^4.

Eingabeformat

Die erste Zeile enthält eine ganze Zahl N (1 ≤ N ≤ 100000) — die Anzahl der Elemente. Die zweite Zeile enthält N ganze Zahlen, getrennt durch Leerzeichen — die Elemente des Arrays.

Ausgabeformat

Geben Sie N Zahlen aus — das sortierte Array, getrennt durch Leerzeichen.

Beispiele

Beispiel 1

EINGABE

5
3 1 2 1 3

AUSGABE

1 1 2 3 3

Beispiel 2

EINGABE

4
-2 0 -2 1

AUSGABE

-2 -2 0 1

Beispiel 3

EINGABE

1
42

AUSGABE

42

main.java