JavaScript implémente une analyse de tri rapide

Cet article présente principalement la méthode d'implémentation du tri rapide en JavaScript. Il analyse le principe, la méthode d'implémentation et les précautions de fonctionnement associées sous forme d'exemples. J'espère que cela pourra aider tout le monde. .

Idéologie :

Utilisez l'idée de diviser pour régner et la méthode récursive pour décomposer les données en différentes sous-séquences contenant des éléments plus petits et des éléments plus grands. .

1. Sélectionnez un élément du tableau comme repère

2. Parcourez le tableau, les éléments plus petits que le repère sont déplacés vers la gauche du repère et les éléments plus grands que le repère. sont déplacés vers la droite du benchmark

3. Répétez les deux premières étapes pour les deux sous-ensembles à gauche et à droite du benchmark jusqu'à ce qu'il ne reste qu'un seul élément dans tous les sous-ensembles

Code d'implémentation :

function sqort(arr){
 if(arr.length===0){
 return [];
}
var left=[];
var right=[];
var pivot=arr[0];//(基准以首元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,qsort(right));//递归
}
var a=[];
for (i=0;i<10;++i){
a[i]=Math.floor(Math.random()*100+1);
}
console.log(a);
console.log(sqort(a));
//(基准以中间元素的情况)
function sqort(arr){
 if(arr.length<=1){
 return arr;
}
var left=[];
var right=[];
var pivotIndex=Math.floor(arr.length/2);
var pivot=arr.splice(pivotIndex,1)[0];//(基准以中间元素)
for(var i=1;i<arr.length;i++){
 if(arr[i]<pivot){
 left.push(arr[i]);
}else{
 right.push(arr[i]);
}
}
return sqort(left).concat(pivot,sqort(right));//递归
}
var a=[12,34,23,78,34,26];
console.log(a);
console.log(sqort(a));

Remarque : Appelez récursivement la fonction sqort() pour les tableaux plus petits et des tableaux plus grands respectivement, lorsque la récursion se termine. À ce moment-là, le plus petit tableau est concaténé avec la base et le plus grand tableau pour former le tableau ordonné final et renvoyé.

Recommandations associées :

Exemple d'implémentation PHP d'une méthode de tri rapide

Exemple d'implémentation PHP d'un algorithme de tri rapide pour tableaux bidimensionnels

Comment implémenter le tri rapide

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!