Arrays sortieren in Java

Das Sortieren ist eine der Operationen, auf die man ständig zurückgreift, und Javas Standardbibliothek macht es meistens zu einem Einzeiler. Der Haken ist, dass die Art des Elements eine Rolle spielt: Primitive werden auf eine Weise sortiert, Objekte auf eine andere, und „Ich möchte absteigende Reihenfolge" oder „sortiere nach einem Feld" erfordert einen Comparator. Dieses Kapitel behandelt alles davon.

Die zentrale Methode ist Arrays.sort. Sie sortiert in-place — sie verändert das übergebene Array. Wenn das Original erhalten bleiben soll, muss man es zuerst kopieren.

Primitive sortieren

Für int[], long[], double[], char[] usw. reicht ein einziger Aufruf:

import java.util.Arrays;

int[] data = {3, 1, 4, 1, 5, 9, 2, 6};
Arrays.sort(data);
System.out.println(Arrays.toString(data));   // [1, 1, 2, 3, 4, 5, 6, 9]

Die Sortierung von Primitiven erfolgt immer aufsteigend. Es gibt keine Comparator-Überladung — Primitive können nicht durch eine beliebige Funktion verglichen werden, wie es bei Objekten möglich ist.

Für absteigende Sortierung besteht der Trick darin, nach Integer[] zu boxen und einen Comparator anzugeben, oder aufsteigend zu sortieren und manuell umzukehren:

int[] data = {3, 1, 4};
Arrays.sort(data);
// reverse in place
for (int i = 0, j = data.length - 1; i < j; i++, j--) {
  int tmp = data[i]; data[i] = data[j]; data[j] = tmp;
}

Einen Bereich sortieren

Übergib from (inklusive) und to (exklusive), um nur einen Teil des Arrays zu sortieren:

int[] data = {9, 8, 7, 6, 5, 4, 3, 2, 1};
Arrays.sort(data, 2, 6);
// {9, 8, 4, 5, 6, 7, 3, 2, 1} — only positions 2..5 sorted

Die Elemente außerhalb des Bereichs bleiben an ihrem Platz.

Objekt-Arrays sortieren (natürliche Ordnung)

Für ein Array von Objekten, deren Klasse Comparable<T> implementiert — String, die geboxteten numerischen Wrapper, LocalDate, alles mit einer „natürlichen" Ordnung — ruft man Arrays.sort direkt auf:

String[] words = {"banana", "apple", "cherry"};
Arrays.sort(words);
// {"apple", "banana", "cherry"} — alphabetical

Wenn die Klasse Comparable nicht implementiert, wirft dies zur Laufzeit eine ClassCastException. Die Lösung besteht darin, einen Comparator anzugeben.

Sortieren mit einem Comparator

Ein Comparator<T> ist eine Funktion, die zwei T-Werte erhält und eine negative Zahl, null oder eine positive Zahl zurückgibt, um „erstes ist kleiner", „gleich", „erstes ist größer" auszudrücken. Der sauberste Weg, einen zu erstellen, ist mit Comparator.comparing:

record Player(String name, int score) {}

Player[] players = {
  new Player("Ada", 1500),
  new Player("Linus", 1800),
  new Player("Grace", 1650)
};

// sort by score, ascending
Arrays.sort(players, Comparator.comparing(Player::score));

// sort by score, descending
Arrays.sort(players, Comparator.comparing(Player::score).reversed());

// sort by name (case-insensitive), then by score as tiebreaker
Arrays.sort(players,
  Comparator.comparing(Player::name, String.CASE_INSENSITIVE_ORDER)
            .thenComparing(Player::score));

Die Kette Comparator.comparing(...).reversed() und .thenComparing(...) ist die idiomatische Methode, Sortierreihenfolgen zu kombinieren. Man muss fast nie eine Comparator-Klasse von Hand schreiben. Für einen tieferen Blick auf den Unterschied zwischen der natürlichen Ordnung einer Klasse und einem externen Comparator siehe Comparable vs Comparator.

Umgang mit null-Elementen

Ein einfacher Comparator wirft eine NullPointerException, wenn das Array ein null enthält. Umschließe es mit Comparator.nullsFirst oder Comparator.nullsLast, um nulls stattdessen an ein Ende zu verschieben:

String[] words = {"banana", null, "apple"};
Arrays.sort(words, Comparator.nullsFirst(Comparator.naturalOrder()));
// {null, "apple", "banana"}

Geboxte Primitive sortieren

Integer[], Double[] usw. sind Objekt-Arrays — daher steht die gesamte Comparator-Maschinerie zur Verfügung:

Integer[] nums = {3, 1, 4, 1, 5};
Arrays.sort(nums, Comparator.reverseOrder());
// {5, 4, 3, 1, 1}

Wenn für ein primitives Array eine absteigende Reihenfolge benötigt wird, ist Boxing der sauberste Weg — vorausgesetzt, das Array ist nicht riesig, sind die Kosten akzeptabel.

Stabilität

Stabile Sortierung bedeutet, dass gleiche Elemente ihre ursprüngliche relative Reihenfolge behalten. Javas Objektsortierung ist stabil: Wenn zwei Player denselben Score haben, bleibt der zuerst gekommene an erster Stelle. Die Sortierung von Primitiven ist nicht garantiert stabil, aber da Primitive keine Identität über ihren Wert hinaus tragen, ist das nicht feststellbar.

Das ist wichtig, wenn Sortierungen verkettet werden — z.B. erst nach Score, dann nach Name. Bei einer stabilen Sortierung bewahrt der zweite Durchlauf die erste Ordnung, wo der neue Schlüssel gleich ist. Mit thenComparing werden beide Schlüssel in einen Comparator zusammengefasst, was die Frage umgeht und meist der sauberere Ansatz ist.

parallelSort

Für sehr große Arrays verteilt Arrays.parallelSort die Arbeit auf mehrere Threads:

int[] huge = new int[10_000_000];
// ... fill huge ...
Arrays.parallelSort(huge);

Gleiche API, gleiche In-place-Semantik. Das Einrichten der Threads verursacht Overhead, daher ist für kleine Arrays ein einfaches sort schneller. Der Schwellenwert liegt bei einigen Zehntausend Elementen; darunter lohnt es sich nicht.

Wenn die Daten in einer List statt in einem Array liegen, ist das Äquivalent Collections.sort oder list.sort(...) — dieselben Comparator-Regeln gelten. Siehe wie man eine ArrayList sortiert.

Ein ausgearbeitetes Beispiel

Was kommt als nächstes

Du hast jetzt die Lese-und-Transformationsseite von Arrays kennengelernt. Das letzte Kapitel dieses Teils behandelt das Kopieren von Arrays — die richtige Methode, ein vorhandenes Array zu duplizieren, zu schneiden und zu vergrößern, ohne beide durch gemeinsame Referenzen zu verflechten.

Übungen