Par rapport aux algorithmes tels que le tri des bulles, le tri de sélection, etc., les principes d'algorithmes spécifiques et la mise en œuvre du tri rapide sont difficiles. Pour mieux comprendre le tri rapide, nous décrivons toujours les principes algorithmiques du tri rapide en détail sous forme d'exemples. Dans l'algorithme de tri précédent, nous utiliserons le problème de tri de la hauteur de 5 athlètes comme exemple pour l'expliquer. Afin de mieux refléter les caractéristiques du tri rapide, nous ajouterons 3 autres athlètes ici. Les 8 athlètes et leurs informations sur l'exemple sont les suivants (F, G, H sont de nouveaux athlètes): A (181), B (169), C (187), D (172), E (163), F (191), G (189), H (182)
Dans l'algorithme de tri précédent, ces tri ont tous été réalisés par l'entraîneur. Maintenant que le nombre d'athlètes a augmenté, l'entraîneur veut également profiter de l'occasion pour faire une pause, alors l'entraîneur a appelé deux assistants et a demandé aux deux assistants de trier les hauteurs des 8 athlètes de gauche à droite et bas à haut de manière rapide.
Selon le principe de l'algorithme de la méthode de tri rapide, les deux assistants se tiennent des deux côtés de la disposition de l'athlète, comme indiqué sur la figure ci-dessous:
Tout d'abord, Assistant 1 sélectionne un athlète dans l'arrangement (sélectionne généralement le premier athlète à gauche ou l'athlète du milieu), et sélectionne ici l'athlète A (181). Étant donné que le tri est de gauche à droite et de bas à haut, l'assistant 1 nécessite un athlète qui est plus petit que A (181) (le A sélectionné (181) est utilisé comme référence pour la comparaison. Toutes les comparaisons dans ce tour sont comparées à l'athlète initialement sélectionné A (181)):
Continuons à nous référer au schéma détaillé du premier cycle de tri rapide.
Lorsque les deux assistants se réunissent pendant le processus de tri et de recherche, la comparaison du tour actuel est arrêtée et l'athlète A (181) initialement sélectionné est placé dans l'espace vide où les deux assistants se rencontrent:
En cas rapide, ce cycle de tri se termine lorsque deux assistants se rencontrent. À l'heure actuelle, nous avons constaté qu'en utilisant la position A (181) où les deux athlètes se sont rencontrés comme point de division, ceux de gauche sont des athlètes plus petits qu'un (181), et ceux à droite sont des athlètes plus grands que A (181). À l'heure actuelle, nous séparerons les deux types sur le côté gauche et droit de A (181). Si nous continuons à trier les arrangements des deux côtés en utilisant les méthodes de tri des deux assistants ci-dessus, puis après plusieurs arrangements, nous obtiendrons enfin les résultats de tri dont nous avons besoin.
Ce qui précède est l'ensemble du processus d'implémentation de tri du tri rapide. Le tri rapide consiste à utiliser les règles de tri ci-dessus pour diviser un arrangement en deux arrangements, et les deux arrangements en quatre arrangements jusqu'à ce qu'il n'y ait pas d'arrangement à diviser, et enfin nous obtenons le résultat de tri dont nous avons besoin.
Maintenant, nous programmons toujours le code Java pour trier les hauteurs des 8 athlètes ci-dessus en utilisant un tri rapide:
/ ** * Tri rapide des éléments dans le tableau spécifié du début à la fin * * @param tableau le tableau spécifié * @param Démarrez le point résultant de l'enquête de tableau qui doit être rapidement triée * @param finir la fin de l'indice de tableau qui doit être trié * / public static Void QuidSort (int [] Array, int start, {// i est l'équivalent pour la position de la position 1, JE IS équivalent à la position de l'assistant 2 int i = start, j = end; int pivot = array [i]; // Prenez le premier élément comme l'élément de référence int videIndex = i; // L'indice de position de l'espace vide est indiqué, et la valeur par défaut est la position de l'élément de référence récupéré // S'il y a plus de 1 éléments à trier, entrez un tri rapide (tant que i et j sont différents, cela signifie qu'au moins 2 éléments de tableau doivent être triés) tandis que (i <j) {// Assistant 2 commence à rechercher des éléments plus petits que l'élément de référence de droite à gauche (i <j & & g pIvot; if (i <j) {// Si l'assistant 2 trouve l'élément correspondant avant de rencontrer l'assistant 1, il donne l'élément aux "postes vacants" de l'assistant 1, j devient un tableau d'espace vide [videIndex] = array [videIndex = j]; } // Assistant 1 commence à chercher des éléments plus grands que l'élément de référence de gauche à droite (i <j && array [i] <= pivot) i ++; if (i <j) {// Si l'assistant 1 trouve l'élément correspondant avant de rencontrer l'assistant 2, il donnera l'élément aux "postes vacants" de l'assistant 2, et je devient un tableau vacant [videIndex] = array [videIndex = i]; }} // Après l'assistant 1 et l'assistant 2 Rencontre, la boucle s'arrête et la valeur de référence initiale est prise au dernier tableau vacant [videIndex] = pivot; // ===== Cette série de tri rapide est terminée ===== // S'il y a plus de 2 éléments sur le côté gauche du point de division I, l'appel récursif continue de le trier rapidement si (i - start> 1) {QuickSort (array, 0, i - 1); } // S'il y a plus de 2 éléments sur le côté droit du point divisé J, l'appel récursif continue de le trier rapidement if (end - j> 1) {Quicksort (array, j + 1, end); }} // Méthode principale Public statique void main (String [] args) {// ===== Tri de faible à haut en utilisant la méthode de tri rapide pour représenter les hauteurs de 8 athlètes ===== // a (181), b (169), c (187), d (172), e (163), f (191), g (189), h (182) int [] = {181, G (189), H (182) 187, 172, 163, 191, 189, 182}; // Appelez la méthode Quick Tri Quicksort (Heights, 0, Height.Length - 1); // Résultat trié de sortie pour (int hauteur: hauteurs) {System.out.println (hauteur); }}Les résultats d'exécution de code Java ci-dessus sont sortis comme suit:
163169172181182187189191
Remarque: En raison des différences de réflexion locales, il peut y avoir plusieurs variations dans l'implémentation de code triée rapide ci-dessus. Cependant, peu importe les variantes, l'idée principale du tri rapide ne changera pas.
Une autre implémentation: numérisation unidirectionnelle
Il existe une autre version de balayage unidirectionnel pour le tranchant de tri rapide. L'étape spécifique consiste à sélectionner le dernier élément du tableau comme l'élément de tranchage et à définir deux pointeurs. Le pointeur I pointe vers une position devant le premier élément du tableau, et J pointe vers le premier élément du tableau. J scanne de l'avant vers la droite et à droite. Lors de la rencontre d'un élément de tranchage inférieur ou égal à, ajoutez-moi à un, puis échangez les éléments pointés par i et j. Enfin, échangez les éléments en position I + 1 et les éléments de tranchage pour compléter la division du tableau. L'implémentation du code est la suivante:
int partition (int [] a, int lo, int hi) {int i = lo - 1, j = lo; int v = a [hi]; while (j <hi) {if (a [j] <= v) {swap (a, ++ i, j); } j ++; } swap (a, i + 1, hi); retour i + 1;}