Effiziente Implementierungen von Such- und Sortieralgorithmen in Java

Question

Hat jemand eine gute Referenz für eine Reihe von Java-Code-Implementierungen gängiger Such- und Sortieralgorithmen?

Es gibt viele Möglichkeiten, eine Katze zu häuten (es ist einfach, Java-Code von verschiedenen Algos im Netz zu finden), aber gibt es eine Liste der effizientesten Möglichkeiten in Java, diese verschiedenen Algorithmen zu implementieren?

Es gibt zum Beispiel die http://www.algorithmist.com aber die meisten Implementierungen sind in C/C++.

Prost!

Answer 1

Ich würde vorschlagen, den Quelltext der Java Standard Library selbst zu betrachten.

Die Klassen Collections und Arrays haben Implementierungen für binäre Suche und Binärsortierung, die Sie studieren können.

Hier ist die Quelle für Collections.java von openjdk: http://www.docjar.com/html/api/java/util/Collections.java.html

Answer 2

Ich fand das Buch "Algorithmen in Java (Teile 1-4)" von Sedgewick nützlich. Der Code ist available online, aber ohne das Buch könnte es schwer zu verstehen sein.

Answer 3

Die Laufzeit Komplexität eines Algorithmus ist gleichgültig gegenüber der Programmiersprache, in der es implementiert ist - so sollten Sie nicht wirklich kümmern zu viel. Aber da Sie fragen, würde ich in Betracht ziehen, grepcode zu verwenden. Zum Beispiel, schau was ich found wenn ich "Java Quicksort" durchsucht.

Answer 4

Einige Standardalgorithmen für Maps, Sets, Listen usw. sind verfügbar. Sie müssen download the src.zip from the Oracle-Java homepage, wo es verfügbar ist.

Für allgemeine Anwendungsfälle sollten die Algorithmen ziemlich effizient sein, aber natürlich muss für jeden Algorithmus ein Worst-Case-Szenario für die Daten bereitgestellt werden. In Ausnahmefällen können Sie bessere finden oder produzieren.

Answer 5

https://intelligentjava.wordpress.com/2014/07/05/sorting-algorithms/ hat eine gute Bewertung mit Implementierungen und Benchmark für die Performance-Vergleich.