L'idée de "tri rapide" est très simple, et l'ensemble du processus de tri ne nécessite que trois étapes:
(1) Dans l'ensemble de données, sélectionnez un élément comme "base" (pivot).
(2) Tous les éléments plus petits que la "référence" sont déplacés vers la gauche de la "référence"; Tous les éléments plus grands que la "référence" sont déplacés vers la droite de la "référence".
(3) Pour les deux sous-ensembles à gauche et à droite de la "ligne de base", répétez les première et deuxième étapes jusqu'à ce qu'il ne reste qu'un élément dans tous les sous-ensembles.
Par exemple, il y a maintenant un ensemble de données {85, 24, 63, 45, 17, 31, 96, 50}. Comment le trier?
Dans la première étape, sélectionnez l'élément intermédiaire 45 comme "base". (La valeur de référence peut être sélectionnée arbitrairement, mais le choix de la valeur intermédiaire est plus facile à comprendre.)
La deuxième étape consiste à comparer chaque élément avec la "base" afin de former deux sous-ensembles, l'un est "moins de 45" et l'autre est "supérieur ou égal à 45".
La troisième étape consiste à répéter les première et deuxième étapes pour les deux sous-ensembles jusqu'à ce qu'il ne reste qu'un élément dans tous les sous-ensembles.
Ce qui suit est une référence aux informations en ligne (ici et ici) pour implémenter l'algorithme ci-dessus dans le langage JavaScript.
Tout d'abord, définissez une fonction Quicksort dont les paramètres sont un tableau.
var Quicksort = fonction (arr) {};Ensuite, vérifiez le nombre d'éléments dans le tableau, et s'il est inférieur ou égal à 1, il sera retourné.
var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; }};Ensuite, sélectionnez "Pivot" et séparez-le du tableau d'origine, puis définissez deux tableaux vides pour stocker deux sous-ensembles d'une gauche et un à droite.
var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var gauche = []; var droit = [];};Ensuite, commencez à traverser le tableau, mettez des éléments plus petits que la "base" dans le sous-ensemble à gauche et des éléments plus grands que la base dans le sous-ensemble à droite.
var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var gauche = []; var droit = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {Left.push (arr [i]); } else {droite.push (arr [i]); }}};Enfin, répétez ce processus en continu en utilisant la récursivité pour obtenir le tableau trié.
var Quicksort = fonction (arr) {if (arr.length <= 1) {return arr; } var pivotIndex = math.floor (arr.length / 2); var pivot = arr.splice (pivotIndex, 1) [0]; var gauche = []; var droit = []; for (var i = 0; i <arr.length; i ++) {if (arr [i] <pivot) {Left.push (arr [i]); } else {droite.push (arr [i]); }} return Quicksort (gauche) .concat ([pivot], Quicksort (à droite));};Lorsque vous l'utilisez, appelez simplement Quicksort ().
Ce qui précède est une explication détaillée de l'exemple d'algorithme Quicksort de la série d'algorithmes JavaScript introduite par l'éditeur. J'espère que cela vous sera utile. Si vous avez des questions, veuillez me laisser un message et l'éditeur vous répondra à temps. Merci beaucoup pour votre soutien au site Web Wulin.com!