Quel algorithme de tri 'Array.sort()' de JavaScript utilise-t-il ?

Algorithme utilisé par la fonction JavaScript Array.sort()

La fonction JavaScript Array#sort() est un mécanisme de tri polyvalent qui prend en charge diverses opérations de tri basées sur les arguments fournis. et fonctions. Mais quel moteur le tri vanilla, celui sans paramètres, utilise-t-il ?

En regardant de plus près le code source de WebKit (utilisé par Chrome et Safari), nous constatons que le choix de l'algorithme dépend du type de array:

Tableaux numériques ou tableaux contenant des types primitifs : Ces tableaux sont triés à l'aide de la fonction C std::qsort, qui implémente généralement une variation de tri rapide (souvent tri introspectif).

Tableaux contigus de types non numériques : Ces tableaux sont convertis en chaînes et triés à l'aide du tri par fusion (lorsque cela est possible pour des raisons de stabilité) ou du tri q (sinon).

Autres types (tableaux non contigus et tableaux associatifs) : WebKit utilise la sélection sort (tri min) ou, dans certains cas, trie dans une arborescence AVL pour ces types. En raison d'une documentation peu claire, il serait nécessaire de tracer les chemins du code pour déterminer l'algorithme spécifique utilisé pour chaque type.

Le code contient notamment un commentaire suggérant l'utilisation d'un tri par base pour un tri plus rapide des tableaux stringifiés, mais ce commentaire met en évidence une incompréhension de la complexité d'exécution du tri radix.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!