Sort rapide, également connu sous le nom de partitionnement et de tri des échanges. Un algorithme de tri rapide mis en œuvre avec la stratégie de division et de conquête.
Cet article parle principalement de l'utilisation de JavaScript pour mettre en œuvre un tri rapide des idées en place
Méthodes de division et de traitement:
En informatique, la méthode de la division et de la conquête est un paradigme d'algorithme très important basé sur une récursivité multiple de branche. L'explication littérale est de "diviser et conquérir", ce qui signifie diviser un problème complexe en deux sous-problèmes identiques ou similaires jusqu'à la fin du sous-problème peut être simplement résolu, et la solution du problème d'origine est la fusion des solutions du sous-problème. (Extrait de Wikipedia)
Idée de tri rapide
Spécifiez un élément dans le tableau en tant que règle, placez le plus grand que lui et mettez le plus petit que avant l'élément, répétez ce jusqu'à ce que tous soient disposés dans l'ordre positif.
Le tri rapide est divisé en trois étapes:
Sélectionnez une référence: sélectionnez un élément comme référence dans la structure des données (PIVOT)
Partition: reportez-vous à la taille de la valeur de l'élément de référence, divisez la zone non ordonnée. Toutes les données plus petites que l'élément de référence sont placées dans un intervalle, et toutes les données plus grandes que l'élément de référence sont placées dans un autre intervalle. Une fois l'opération de partition terminée, la position de l'élément de référence est la position où elle devrait être après le tri final.
Récursion: appelez récursivement les algorithmes aux étapes 1 et 2 pour la première fois jusqu'à ce qu'il ne reste qu'un élément dans tous les intervalles non ordonnés.
Parlons maintenant des méthodes de mise en œuvre courantes (aucun algorithme en place n'est utilisé)
fonction Quicksort (arr) {if (arr.length <= 1) return; // s'il vous plaît le benchmark de chiffre le plus proche du milieu du tableau, des nombres impairs et même des nombres prennent des valeurs différentes, mais je ne le pense pas. Bien sûr, vous pouvez choisir le premier ou le dernier numéro en tant que benchmark, et il n'y a pas trop de description ici var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; // les intervalles gauche et gauche sont utilisés pour stocker les nombres triés var gauche = []; (var i = 0; i <arr.length; i ++) {console.log ('la' + (i + 1) + 'boucle d'opération de partition:'); // il y a moins que la référence, placée dans l'intervalle gauche, supérieur à la référence, placé dans l'intervalle droit if (arr [i] <pivot) {gauche.) {droite.push (arr [i]); console.log ('droite:' + (arr [i]))}} // L'opérateur Concat est utilisé ici pour épisser l'intervalle gauche, la référence et l'intervalle droit en un nouvel tableau // puis récursive 1 et 2 étapes jusqu'à Quicksort (à droite));} var arrr = [14, 3, 15, 7, 2, 76, 11]; console.log (Quicksort (arr)); / ** lorsque la base est 7, la première partition est obtenue avec deux sous-ensembles à gauche et à droite [3, 2,] 7 [14, 15, 76, 11]; * avec la base est 2, le sous-ensemble gauche [3, 2] est partitionné et a été trié pour la base. Le tri des extrémités du sous-ensemble gauche * avec la référence comme 76, le sous-ensemble droit est divisé et trié pour obtenir [14, 15, 11] 76 * À l'heure [14, 11] est divisé et trié à ce qui précède [11] est divisé et trié à la base 11, 11 [14] * Il ne reste qu'un élément dans tous les intervalles non ordonnés, et l'extrémité récursive ** /Grâce à un débogage des points d'arrêt, les résultats peuvent être obtenus.
Inconvénients:
Il nécessite un espace de stockage supplémentaire de ω (n), qui est aussi mauvais que le tri de fusion. Dans un environnement de production, un espace mémoire supplémentaire est requis, affectant les performances.
Dans le même temps, beaucoup de gens pensent que ce qui précède est un genre très rapide. Par conséquent, ci-dessous, il est nécessaire de recommander le tri rapide de l'algorithme sur place
Pour plus d'informations sur l'algorithme in situ, veuillez vous référer à Wikipedia. Les étudiants qui sont sous le mur sont similaires à Baidu.
en place
Le tri rapide est généralement mis en œuvre avec une récursivité. La chose la plus importante est la fonction de segmentation de partition, qui divise le tableau en deux parties, l'une est plus petite que pivot et l'autre est plus grande que le pivot. Le principe spécifique a été mentionné ci-dessus
fonction QuickSort (arr) {// Swap Swap Swap (arr, a, b) {var temp = arr [a]; arr [a] = arr [b]; arr [b] = temp;} // partition de partition partition (arr, gauche, à droite) {/ *** au début, vous ne connaissez pas le plus de temps de stockage de pivot, vous pouvez faire pivoter vers le dos en premier * ici arr [à droite]; / *** Lorsque le stockage des éléments plus petits que le pivot, ils sont à côté de l'élément précédent, sinon l'élément stocké dans l'écart peut être plus grand que le pivot, * Par conséquent, une variable d'étape indice est déclarée et initialisée à gauche pour stocker des éléments plus petits que pivot l'un à côté de l'autre. * / var storeIndex = gauche; pour (var i = gauche; i <droite; i ++) {if (arr [i] <pivot) {/ *** Traverse le tableau et trouver l'élément plus petit que pivot, (des éléments plus grands que le pivot seront ignorés) * échangé * / swap (arr, storeIndex, i); storeIndex ++;}} // enfin: échangez un pivot à storeIndex, placez l'élément de référence à la position correcte finale échange (arr, à droite, storeIndex); return storeIndex;} fonction SORT (arr, gauche, droite) {if (gauche> droite) 1).Optimisation de partition
Les étudiants prudents ici peuvent se demander s'il y aura différentes performances lors de la sélection de différentes repères. La réponse est oui, mais parce que je suis une personne frontale et je ne sais pas grand-chose sur l'algorithme, donc cette fosse est laissée à des gens puissants à remplir.
Complexité
Le tri rapide est l'algorithme de tri le plus rapide, et sa complexité temporelle est O (log n)
Dans la situation moyenne, l'ordre de n éléments nécessite des comparaisons (n log n). Dans le pire des cas, des comparaisons (N2) sont nécessaires.
https://github.com/lyz0106/
Ce qui précède est la méthode de tri rapide de la mise en œuvre JavaScript des idées en place introduites par l'éditeur. J'espère que ce sera utile à tout le monde. Si vous avez des questions, laissez-moi un message. L'éditeur vous répondra à temps. Merci beaucoup pour votre soutien pour le site Web du réseau Wulin!