Warum verwendet Java bei Primitiven keine Radix-Sortierung?

java.util.Arrays.sort(/* int[], char[], short[], byte[], boolean[] */) wird eher als 'tuned quicksort' als als radix sort implementiert.

Ich habe vor einiger Zeit einen Geschwindigkeitsvergleich durchgeführt und mit n> 10000 war die Radix-Sortierung immer schneller. Warum?

Ich würde das spekulieren:

• Array.sort ist als Quicksort implementiert, da Quicksort mit einem Komparator alles in angemessener Zeit sortieren kann.
• Das Sortieren einer Liste mit 10000 Einträgen ist nicht so häufig. Der Zugriff auf eine Datenstruktur von 10000 oder mehr Elementen ist weit verbreitet. Wenn Sie die Reihenfolge beibehalten müssen, ist ein ausgeglichener Suchbaum häufig der bessere Weg, als jedes Mal, wenn Sie das kleinste Element benötigen, das gesamte Array zu sortieren.
• Das Sortieren von Primitiven ist nicht so üblich, ungeachtet dessen, was die Universität lehrt.

Der Punkt ist, dass es nicht so häufig vorkommt, dass die Optimierung in der Standardbibliothek erfolgen muss. Wenn Sie eine Anwendung geschrieben haben, die Leistungsprobleme aufweist und bei der Sie durch Profilerstellung feststellen, dass das Sortieren eines Arrays von mehr als 10000 Zoll tatsächlich der Engpass ist, können Sie die Sortierung auch manuell schreiben oder Ihre Auswahl der Datenstruktur im ersten Schritt überdenken Platz.

Back2dos hat alles gesagt, ich werde nur versuchen, den Punkt weiter zu klären, den ich für das Wichtigste halte:

Radix-Sortierung kann nur die tatsächlichen Grundwerte, die im Array enthalten sind, basierend auf ihren Binärziffernmustern sortieren. In realen Szenarien der Softwareentwicklung tritt dieser Fall fast nie auf . Viel häufiger sortieren wir Arrays komplexerer (nicht primitiver) Datenstrukturen, und manchmal sortieren wir Arrays von Indizes nach anderen Entitäten.

Nun ist ein Array von Indizes zu anderen Entitäten tatsächlich ein Array von Grundelementen, aber die Sortierreihenfolge wird von der Komparatorschnittstelle (und / oder dem Delegat in C #) bereitgestellt, die nicht die Indizes, sondern die durch die Indizes indizierten Entitäten vergleicht. Somit hat die Sortierreihenfolge absolut keine Beziehung zur Reihenfolge der Werte der Grundelemente, und daher ist die Radix-Sortierung für dieses Szenario absolut unbrauchbar.

Ein Beispiel:

Wir haben eine Reihe von Zeichenfolgen: [0] = "Mike", [1] = "Albert", [2] = "Zoro". Dann deklarieren wir ein Array von Indizes zu diesen Zeichenfolgen: [0] = 0, [1] = 1, [2] = 2. Dann sortieren wir das Array von Indizes und übergeben es einem Komparator, der nicht die Indizes selbst vergleicht, sondern die tatsächlichen Zeichenfolgen, auf die diese Indizes verweisen. Nach dem Sortieren sieht das resultierende Array von Indizes folgendermaßen aus: [0] = 1, [1] = 0, [2] = 2. Wie Sie sehen, hat diese Sortierreihenfolge nichts mit den Binärmustern der im Array enthaltenen Werte zu tun. Durch Durchlaufen dieses Array von Indizes und Abrufen der entsprechenden Zeichenfolgen werden die Zeichenfolgen jedoch in sortierter Reihenfolge aufgerufen.