1. Notion d'algorithme.
Le tri rapide est une amélioration du tri à bulles. Proposé par CAR Hoare en 1962.
2. Pensée algorithmique.
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 procéder de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.
3. Mettez en œuvre les idées.
① Utilisez le premier mot-clé K 1 comme mot de contrôle, divisez [K 1 ,K 2 ,…,K n ] en deux sous-zones, de sorte que tous les mots-clés dans la zone de gauche soient inférieurs ou égaux à K 1 et tous les mots-clés dans la zone de droite sont supérieurs ou égaux à K 1, et enfin le mot de contrôle est situé à la position appropriée entre les deux sous-zones. Les données de la sous-zone sont toujours dans un état désordonné.
② Traitez la zone gauche dans son ensemble et traitez-la avec les étapes de ①, et effectuez le même traitement sur la zone droite. (c'est-à-dire récursivité)
③ Répétez les étapes ① et ② jusqu'à ce que la zone de gauche soit traitée.
public static void quickSortByMid(int[] a, int low, int high) { if (low >= high) return; // Split int pivot = a[low]; // Valeur de base int i = low, j = high; while (i < j) { while (i < j && a[j] >= pivot) --j; a[i]=a[j] while (i < j && a[i] <= pivot) + +je; a[j]=a[i]; } a[i]=pivot; quickSortByMid(a, faible, i-1); quickSortByMid(a, i+1, élevé);Diagramme schématique de l'algorithme de tri rapide :
Ce qui précède représente l'intégralité du contenu de cet article. J'espère qu'il sera utile à tout le monde d'apprendre l'algorithme de tri rapide Java.