Sappiamo che l'ordinamento rapido è il miglior algoritmo di ordinamento.Perché Collections.sort utilizza l'ordinamento di unione anziché il quicksort?
Il metodo collections.sort ha utilizzato un algoritmo di ordinamento di tipo merge invece di un ordinamento rapido. Ma Arrays.sort usa un ordinamento rapido.
Qual è la ragione per cui Collections.sort utilizza l'ordinamento di unione anziché l'ordinamento rapido?
altamente probabile da Josh Bloch §:
ho scritto questi metodi, quindi suppongo che sono qualificato per rispondere. È vero che non esiste un singolo algoritmo di ordinamento migliore. QuickSort ha due principali carenze rispetto ai mergesort:
Non è stabile (come osservato parsifal).
Non corrisponde a garanzia n log n prestazioni; può degradare a prestazioni quadratiche su input patologici.
stabilità è un non-problema per i tipi primitivi, in quanto non v'è alcuna nozione di identità distinta da (valore) l'uguaglianza. E la possibilità del comportamento quadratico non è stata considerata un problema nella pratica per l'implementazione di Bentely e McIlroy (o successivamente per Dual Pivot Quicksort), motivo per cui queste varianti QuickSort sono state utilizzate per gli ordinamenti primitivi .
Stabilità è un grosso problema quando si ordinano oggetti arbitrari. Ad esempio, si supponga di avere oggetti che rappresentano messaggi di posta elettronica e si ordinano prima per data, poi per mittente. Ci si aspetta che vengano ordinati per data all'interno di ciascun mittente, ma ciò sarà vero solo se l'ordinamento è stabile. Ecco perché abbiamo scelto di fornire un ordinamento stabile (Merge Sort) per ordinare i riferimenti agli oggetti. (Tecnicamente interviene parlando, più sequenziali tipi stabili si traducono in un ordinamento lessicografico sui tasti del ordine inverso dei tipi: il tipo finale determina il più significativo sottochiave.)
Si tratta di un beneficio lato bello che merge sort garanzie n log n (tempo) prestazioni, non importa quale sia l'input. Ovviamente c'è un lato negativo: l'ordinamento rapido è un ordinamento "sul posto": richiede solo il registro n spazio esterno (per mantenere lo stack di chiamate). Unisci, ordina, d'altra parte, richiede O (n) spazio esterno. La variante TimSort (introdotta in Java SE 6) richiede uno spazio sostanzialmente minore (O (k)) se l'array di input è quasi ordinato.
Inoltre, il following è rilevante:
L'algoritmo utilizzato da java.util.Arrays.sort e (indirettamente) da java.util.Collections.sort per ordinare i riferimenti oggetto è un " modificato mergesort (in cui l'unione viene omessa se l'elemento più alto nella sottolista bassa è inferiore all'elemento più basso nella sottolista alta)."It è un ordinamento abbastanza veloce stabile che garantisce prestazioni O (n log n) e richiede O (n) spazio extra. Nel suo giorno (è stato scritto nel 1997 da Joshua Bloch), è stata una buona scelta, ma oggi, ma siamo in grado di fare molto meglio.
Dal 2003, di Python elenco di ordinamento ha utilizzato un algoritmo noto come timsort (dopo Tim Peters, che lo ha scritto). si tratta di una stalla, adattativo, iterativo mergesort che richiede lontano meno di n log (n) confronti quando in esecuzione su array parzialmente ordinati, mentre offre prestazioni comparabili a un mergesort tradizionale quando eseguito su array casuali. Come stabile e viene eseguito in tempo O (n log n) (caso peggiore). Nel peggiore dei casi, timsort richiede spazio di archiviazione temporanea per n/2 riferimenti a oggetti; nel migliore dei casi, richiede solo una piccola quantità di spazio costante pari a . Confrontalo con l'attuale implementazione , che richiede sempre spazio aggiuntivo per n oggetti riferimenti, e batte n log n solo su liste quasi ordinate.
Timsort è descritto in dettaglio qui: http://svn.python.org/projects/python/trunk/Objects/listsort.txt.
L'implementazione originale di Tim Peters è stata scritta in C. Joshua Bloch portandola da C a Java e terminata testata, sottoposta a benchmark e ottimizzata estensivamente il codice risultante . Il codice risultante è un sostituto sostitutivo per java.util.Arrays.sort. Sui dati altamente ordinati, questo codice può essere eseguito fino a 25 volte più velocemente dell'implementazione corrente (su la VM del server HotSpot). Su dati casuali, le velocità delle vecchie e nuove implementazioni sono paragonabili. Per elenchi molto brevi, la nuova implementazione è notevolmente più veloce della precedente anche su dati casuali (poiché evita la copia non necessaria dei dati).
Vedere anche Is Java 7 using Tim Sort for the Method Arrays.Sort?.
Non c'è una sola scelta "migliore". Come con molte altre cose, si tratta di compromessi.
A meno che non si riesca a ottenere un autore JDK per rispondere, tutto quello che si otterrà è una congettura. Non è una vera domanda. – EJP
@EJP Buon punto, ma sicuramente "Non costruttivo" è il giusto motivo di chiusura. Mi è chiaro quale sia la domanda qui. –
Perché i ragazzi di Java hanno deciso di farlo in questo modo. Chiediglielo. Non riesci a ottenere una risposta legittima qui penso. E l'ordinamento rapido è ** non ** il migliore. È solo il migliore per ** uso generico **. –