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é
 ;