Selon Wikipedia :
"en java, les méthodes de tableau () utilisent une sorte de fusion ou un réglage Quicksort en fonction des types de données et de l'efficacité de la mise en œuvre Basculer vers l'insertion Trier lorsque moins de sept éléments de tableau sont être trié "
Mais pourquoi? Les deux conditions de fusion et de tri rapide sont
O (n log n) .
5 Réponses :
Ce n'est pas si ad-hoc:
TRESAYS.JAVA'S TRY MODE utilise QuickSort pour les matrices de primitives et la fusion Trier pour les tableaux d'objets.
Pourquoi la méthode de java.sort Utilisez deux algorithmes de tri différents pour différents types?
Aussi, selon les documents:
Par exemple, l'algorithme utilisé par type (objet []) ne doit pas nécessairement être une fusion, mais il doit être stable.
et une autre citation du Javadoc:
Ce type est garanti d'être stable: les éléments égaux ne seront pas réorganisé à la suite du tri.
Mise en œuvre Note: Cette implémentation est une stable, adaptative, Mergesort itératif qui nécessite beaucoup moins que les comparaisons N LG (N) Lorsque le tableau d'entrée est partiellement trié, en offrant le performance d'une fusion traditionnelle lorsque la matrice d'entrée est commandé au hasard. Si la matrice d'entrée est presque triée, la La mise en œuvre nécessite environ N comparaisons. Stockage temporaire Les exigences varient d'une petite constante pour des tableaux d'entrée presque triés aux références d'objet N / 2 pour les matrices d'entrée commandées de manière aléatoire.
La mise en œuvre prend l'égalité d'avantage de l'ascension et de la descente ordre dans son tableau d'entrée et peut tirer parti de l'ascension et ordre décroissant dans différentes parties du même tableau d'entrée. Il est bien adapté à la fusion de deux ou plusieurs tableaux triés: simplement concaténer les matrices et trier le tableau résultant.
La mise en œuvre a été adaptée de Tim Peters's List Tri pour Python (Timsort).
Ils ont déménagé sur TIMED Fusion Sort car ont constaté que les ensembles de données partiellement triés de manière statistique, cette méthode peut être un peu plus rapide que la tri rapide.
Java n'a jamais utilisé Mergesort pour les primitives et n'a jamais utilisé QuickSort pour les types de référence.
Qui est-ce qu'ils? Références, s'il vous plaît.
C'est pour collections.sort . En outre, cela dit aussi vite que. Je crois que la raison principale est toujours la stabilité, cependant.
où les algorithmes diffèrent est leur comportement Case typique , c'est là que le tri d'insertion est l'un des pires. D'autre part, pour de très petites collections (n ≈ n 2 ) La simplicité de type d'insertion gagne.
Les règles de sélection d'algorithme d'algorithme Java préfèrent d'abord le QuickSort, et ne relèvent que quelque chose d'autre en raison de restrictions spécifiques. Quicksort, nommément, est un type instable et n'est donc qu'acceptable pour le tri des primitives. Pour les types de référence, Timsort est utilisé à partir de OpenJDK 7 (précédemment Mergesort).
Remarque supplémentaire: le tri d'insertion gagne sur de petites collections car il a un facteur constant plus bas, lequel Big-O n'enregistre pas. Notez que, par exemple: n ^ 2 <10n pour n <10 .
@Dukeling Oui, c'est mon point. La simplicité signifie un facteur faible constant.
Quicksort et Mergesort sont tous les deux (n log n) dans la performance moyenne . Dans le pire des cas, Quicksort est O (n ^ 2).
Leur cas moyen n'est pas O (n ^ 2), son o (nlogn).
Merci d'avoir attrapé ça. Je me suis concentré sur le pire des cas N ^ 2 et j'ai tapé accidentellement pour la moyenne.
Bien Java 7 utilise Timsort - un hybride de fusion et d'insertion. En fait, il est largement utilisé - Android, Octave, Python l'utiliser aussi. http://en.wikipedia.org/wiki/timsort
Je sais que Yannis va se présenter et me frapper pour cela, mais cela devrait probablement être sur les programmeurs.
Et voici une réponse de l'auteur du code Stackoverflow.com/Questtions/15154158/...