Es gibt verschiedene Sortieralgorithmen wie Insertsortierung, Auswahlsortierung, Blasensortierung usw., die oft in Lehrbüchern der Informatik diskutiert werden. Gibt es ein Array von Integern oder Objekten, gibt es eine eingebaute Java 6-API, die es mir erlaubt, einen bestimmten Sortieralgorithmus anzuwenden, um das Array zu sortieren, anstatt diese Räder neu zu erfinden? Wenn es nicht in Java 6 integriert ist, gibt es Open-Source-Bibliotheken, die diese Funktionalität hervorbringen, und was sind sie?
Die Arrays.sort() Methoden verwenden eine schnelle Sortierung in allen primitiven Arrays.
Der Sortieralgorithmus ist ein abgestimmter Quicksort, der von Jon L. Bentley und M. Douglas McIlroys "Engineering a Sort Function", Software-Practice and Experience. 23 (11), S. 1249-1265 (November 1993). Dieser Algorithmus bietet n * log (n) -Leistung für viele Datensätze, die andere Quicksorts zu einer quadratischen Leistung führen.
Die Collections.sort() Methode verwendet eine Mischsortierung. Diese Art wird auch in Arrays.sort(Object[]) und Arrays.sort(T[], Comparator<? super T>) .
Der Sortieralgorithmus ist ein modifizierter Mergesort (in dem die Zusammenführung weggelassen wird, wenn das höchste Element in der niedrigen Teilliste kleiner ist als das niedrigste Element in der hohen Teilliste). Dieser Algorithmus bietet garantierte n log (n) -Leistung. Diese Implementierung lädt die angegebene Liste in ein Array, sortiert das Array und iteriert über die Liste, wobei jedes Element an der entsprechenden Position im Array zurückgesetzt wird. Dies vermeidet die n2 log (n) -Leistung, die sich aus dem Versuch ergibt, eine verknüpfte Liste an Ort und Stelle zu sortieren.
Arrays.sort(int[] a) verwendet einen abgestimmten Quicksort.
Arrays.sort[Object[] a) verwendet einen modifizierten Mergesort.