Explication détaillée de l'algorithme de tri rapide Javascript_Connaissances de base

Le tri rapide est une amélioration du tri à bulles. Divisez les données à trier en deux parties indépendantes grâce à un tri en un seul passage. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie. Utilisez ensuite cette méthode pour trier rapidement les deux parties des données respectivement. le processus de tri peut se dérouler de manière récursive et, finalement, les données entières deviennent une séquence ordonnée.

Supposons que le tableau à trier est A[0]...A[N-1]. Tout d'abord, sélectionnez au hasard une donnée (généralement le premier numéro du tableau) comme données de référence, puis tous les nombres plus petits. qu'il ne l'est. Placez-le devant et tous les nombres plus grands sont placés derrière. Ce processus est appelé tri rapide en un seul passage. Il convient de noter que le tri rapide n'est pas un algorithme de tri stable, c'est-à-dire que les positions relatives de plusieurs valeurs identiques peuvent changer à la fin de l'algorithme.
L'algorithme de tri rapide en un seul passage est :
1) Définissez deux variables faible et élevée Lorsque le tri commence : low=0, high=N-1 ; 2) Utilisez le premier élément du tableau comme données de référence et attribuez-le à base, c'est-à-dire base=A[0]
; 3) Recherchez vers l'avant à partir du haut, c'est-à-dire recherchez vers l'avant depuis l'arrière (haut--), trouvez la première valeur A[haute] qui est inférieure à la base et échangez A[haute] et A[basse]
 ; 4) Recherchez en arrière depuis le bas, c'est-à-dire recherchez d'avant en arrière (bas), trouvez le premier A[bas] qui est supérieur à la base et échangez A[bas] et A[haut]
 ; 5) Répétez les étapes 3 et 4 jusqu'à ce que faible = élevé
 ;

Copier le code Le code est le suivant :

partition de fonction (éléments, bas, haut){
//Par défaut, le premier élément à gauche est utilisé comme élément de base
var base=elements[low];
while(faible < élevé){
//Recherchez de l'arrière vers l'avant jusqu'à trouver un élément plus petit que l'élément de base et échangez-le
Tandis que(faible < élevé && éléments[élevé] >= base) élevé--;
var swap1=elements[low];elements[low]=elements[high];elements[high]=swap1;
//Recherchez d'avant en arrière jusqu'à trouver un élément plus grand que l'élément de base et échangez-le
While(low < high && elements[low] <= base) low ;
var swap2=elements[low];elements[low]=elements[high];elements[high]=swap2;
>
//Renvoie la position de l'élément de référence comme position de division de la séquence
Retour bas ;
>
fonction sort(éléments, bas, haut){
si(faible<élevé){
// Divisez la séquence en deux et divisez-la en séquence avant et après la position divisée. La première séquence a une valeur plus petite que la position divisée, et la dernière séquence a une valeur plus grande que la position divisée
. var partitionPos=partition(elements, low, high);
//Continuer le tri récursif de la séquence précédente
Trier(éléments, 0, partitionPos-1);
//Continuer à trier récursivement la séquence suivante
Trier(éléments, partitionPos 1, élevé);
>
>
var éléments = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log('avant : ' éléments);
sort(elements, 0, elements.length-1);
console.log(' après : ' éléments);

Efficacité :

Complexité temporelle : Meilleur : O(nlog2n), Pire : O(n^2), Moyenne : O(nlog2n).

Complexité spatiale : O(nlog2n).

Stabilité : Instable.