Sto usando JDK-8 (x64). Per Arrays.sort (primitive) ho trovato quanto segue nella documentazione di Java:
L’algoritmo di ordinamento è un Quicksort Dual-Pivot di Vladimir Yaroslavskiy, Jon Bentley e Joshua Bloch. »
Per Collections.sort (oggetti) ho trovato questo “Timsort”:
Questa implementazione è un mergesort stabile, adattivo e iterativo … Questa implementazione scarica l’elenco specificato in un array, ordina l’array e scorre l’elenco reimpostando ogni elemento dalla posizione corrispondente nell’array.
Se Collections.sort utilizza un array, perché non chiama semplicemente Arrays.sort o usa QuickSort dual-pivot? Perché usare Mergesort ?
L’API garantisce un ordinamento stabile che Quicksort non offre. Tuttavia, quando si ordinano i valori primitivi per il loro ordine naturale, non si noterà una differenza poiché i valori primitivi non hanno id quadro. Pertanto, Quicksort viene utilizzato per gli array primitivi in quanto è leggermente più efficiente.
Per oggetti che potresti notare, quando oggetti che sono ritenuti uguali secondo la loro implementazione di equals o il Comparator fornito cambiano il loro ordine. Pertanto, Quicksort non è un’opzione. Quindi viene utilizzata una variante di MergeSort, le versioni correnti di Java utilizzano TimSort . Questo vale sia per Arrays.sort che per Collections.sort , sebbene con Java 8, l’ List stesso possa sovrascrivere gli algoritmi di ordinamento.
Non conosco la documentazione, ma l’implementazione di java.util.Collections#sort in Java 8 (HotSpot) va così:
@SuppressWarnings({"unchecked", "rawtypes"}) public static void sort(List list, Comparator c) { list.sort(c); }
E List#sort ha questa implementazione:
@SuppressWarnings({"unchecked", "rawtypes"}) default void sort(Comparator c) { Object[] a = this.toArray(); Arrays.sort(a, (Comparator) c); ListIterator i = this.listIterator(); for (Object e : a) { i.next(); i.set((E) e); } }
Quindi, alla fine, Collections#sort usa gli Arrays#sort (degli elementi dell’object) dietro le quinte. Questa implementazione utilizza l’ordinamento di tipo merge o di tipo tim.
Secondo Javadoc, solo gli array primitivi vengono ordinati usando Quicksort. Anche gli array di oggetti sono ordinati con un Mergesort.
Quindi Collections.sort sembra utilizzare lo stesso algoritmo di ordinamento di Arrays.sort for Objects.
Un’altra domanda sarebbe perché un algoritmo di ordinamento diverso viene utilizzato per gli array primitivi rispetto agli array Object?
Come affermato in molte delle risposte.
Quicksort viene utilizzato da Arrays.sort per ordinare raccolte primitive perché la stabilità non è richiesta (non saprai né ti preoccuperai se due tipi identici sono stati scambiati nell’ordinamento)
MergeSort o più specificamente Timsort viene utilizzato da Arrays.sort per ordinare raccolte di oggetti. La stabilità è richiesta Quicksort non fornisce stabilità, fa Timsort.
Collections.sort delegati ad Arrays.sort che è il motivo per cui si vede il javadoc che fa riferimento a MergeSort.
Quick Sort ha due principali svantaggi quando si tratta di unire sort:
La stabilità è un non-problema per i tipi primitivi, in quanto non esiste alcuna nozione di id quadro distinta dall’uguaglianza (valore).
La stabilità è un grosso problema quando si ordinano oggetti arbitrari. È un buon vantaggio collaterale che Merge Sort garantisce prestazioni n log n (time) indipendentemente dall’input. Ecco perché merge sort è selezionato per fornire un ordinamento stabile (Merge Sort) per ordinare i riferimenti agli oggetti.