Explication détaillée de l'algorithme d'implémentation du tri rapide dans les compétences Javascript_javascript

Actuellement, il existe environ sept ou huit algorithmes de tri les plus courants, parmi lesquels « Quicksort » est le plus largement utilisé et le plus rapide. Il a été proposé par C. A. R. Hoare (1934--), lauréat du prix Turing, en 1960.

L'idée du « tri rapide » est très simple 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 "pivot".

(2) Tous les éléments plus petits que « base » sont déplacés vers la gauche de « base » ; tous les éléments plus grands que « base » sont déplacés vers la droite de « base ».

(3) Répétez les première et deuxième étapes pour les deux sous-ensembles à gauche et à droite de la "ligne de base" jusqu'à ce qu'il ne reste qu'un seul élément dans tous les sous-ensembles.

Par exemple, il existe un ensemble de données {85, 24, 63, 45, 17, 31, 96, 50}. Comment le trier ?

La première étape consiste à sélectionner l'élément central 45 comme "ligne de base". (La valeur de base peut être choisie arbitrairement, mais choisir une valeur intermédiaire est plus facile à comprendre.)

La deuxième étape consiste à comparer chaque élément avec la "baseline" afin de former deux sous-ensembles, l'un "inférieur à 45" et l'autre "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 seul élément dans tous les sous-ensembles.

Ce qui suit fait référence aux informations sur Internet et utilise le langage Javascript pour implémenter l'algorithme ci-dessus.

Tout d'abord, définissez une fonction quickSort dont le paramètre est un tableau.

var quickSort = function(arr) {
};

Ensuite, vérifiez le nombre d'éléments dans le tableau, et s'il est inférieur ou égal à 1, renvoyez-le.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
};

Ensuite, sélectionnez le "pivot" et séparez-le du tableau d'origine, puis définissez deux tableaux vides pour stocker deux sous-ensembles, un à gauche et un à droite.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
};

Ensuite, commencez à parcourir le tableau, en plaçant les éléments plus petits que la « ligne de base » dans le sous-ensemble de gauche et les éléments plus grands que la « ligne de base » dans le sous-ensemble de droite.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2) ;
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
};

Enfin, utilisez la récursivité pour répéter ce processus afin d'obtenir le tableau trié.

var quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1);
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat(pivot, quickSort(right));
};
 
var dataArray = [85,24,63,45,17,31,96,50];
console.log(dataArray.join(","));
console.log(quickSort(dataArray).join(","));

J'espère que cet article sera utile à la conception de la programmation JavaScript de chacun.