1. Aperçu
Le tri et la recherche sont deux problèmes très fondamentaux en programmation, et il existe de nombreux algorithmes classiques utilisés pour résoudre ces deux types de problèmes. Cet article mène principalement une discussion de base sur l'implémentation des algorithmes de tri en Java, dans l'espoir de servir de point de départ. rôle. Avant cela, permettez-moi d'abord de vous poser quelques questions : pouvez-vous rédiger un tri rapide correct ? Dans quelles circonstances le tri rapide est-il vraiment rapide ? Votre file d'attente rapide est-elle assez rapide ? Peut-il être encore optimisé ? Avec ces questions, examinons comment le tri rapide est implémenté dans jre7.
La classe d'implémentation du tri dans Jre7 est DualPivotQuickSort.java. Par rapport à jre6, il y a quelques changements, principalement à deux endroits. L'un est l'implémentation du tri par insertion et l'autre est que le pivot dans l'implémentation de QuickSort passe de un à deux. . Prenons l'exemple d'un tableau de type int. Il existe une méthode de base pour l'implémentation du tri dans cette classe. Le prototype de cette méthode est.
Copiez le code comme suit :
void sort(int[] a, int gauche, int droit, booléen le plus à gauche)
Le paramètre a est le tableau qui doit être trié, la gauche représente l'index de l'élément le plus à gauche de la plage du tableau qui doit être trié, la droite représente l'index de l'élément le plus à droite de la plage et le plus à gauche indique si la plage est la plus à gauche. plage dans le tableau. Par exemple:
Tableau : [2, 4, 8, 5, 6, 3, 0, -3, 9] peut être divisé en trois intervalles (2, 4, 8){5, 6}<3, 0, -3, 9>
Pour l'intervalle (), gauche = 0, droite = 2, le plus à gauche = vrai
Pour l'intervalle {}, left=3, right=4, leftmost=false, les paramètres correspondants de l'intervalle <> peuvent être obtenus de la même manière.
Lorsque la longueur de l'intervalle est inférieure à 47, cette méthode utilisera le tri par insertion ; sinon, le tri rapide sera utilisé.
2. Implémentation du tri par insertion
Lorsque l'option la plus à gauche est vraie, le tri par insertion traditionnel est utilisé et le code est relativement simple. Le processus est similaire à la saisie et à l'insertion de cartes lors d'un jeu de cartes :
Copiez le code comme suit :
pour (int i = gauche, j = i; i < droite; j = ++i) {
int ai = a[i + 1];
tandis que (ai < a[j]) {
une[j + 1] = une[j];
si (j-- == gauche) {
casser;
}
}
une[j + 1] = ai;
}
Code de tri par insertion traditionnel
Lorsque l'élément le plus à gauche est faux, il utilise un nouveau type de tri par insertion (tri par insertion par paire). L'amélioration est que chaque fois qu'il parcourt le tableau précédemment trié, deux éléments doivent être insérés, alors que le tri par insertion traditionnel nécessite uniquement de trouver un emplacement approprié pour. un élément à insérer. Pour le tri par insertion, la clé est de trouver une position d'insertion appropriée pour l'élément à insérer. Afin de trouver cette position, il est nécessaire de parcourir le sous-tableau précédemment trié, donc pour le tri par insertion, les éléments qu'il traverse pendant tout le tri. processus Le nombre détermine sa performance. Évidemment, l'insertion de deux éléments dans chaque parcours peut réduire le nombre d'éléments parcourus lors du processus de tri. Le code d'implémentation est le suivant :
Copiez le code comme suit :
pour (int k = gauche; ++gauche <= droite; k = ++gauche) {
int a1 = a[k], a2 = a[gauche];
si (a1 < a2) {
a2 = a1 ; a1 = a[gauche] ;
}
tandis que (a1 < a[--k]) {
une[k + 2] = une[k];
}
une[++k + 1] = a1;
tandis que (a2 < a[--k]) {
une[k + 1] = une[k];
}
une[k + 1] = une2;
}
Il y a maintenant une question : pourquoi la plage la plus à gauche utilise-t-elle le tri par insertion traditionnel et les autres utilisent-elles le tri par insertion par paire ? Quels problèmes surgiront si nous remplaçons le code de tri par insertion traditionnel par le code de tri par insertion par paire ci-dessus ? J'espère que vous y répondrez tous vous-même. . .
3. Implémentation du tri rapide
Le tri rapide a également été amélioré dans Jre7. Le tri rapide traditionnel sélectionne un pivot (les méthodes jre6 de sélection du pivot consistent à sélectionner les éléments aux positions les plus à gauche, au milieu et à l'extrême droite du tableau et à classer les éléments avec les valeurs du milieu comme suit. pivot), puis traverser des deux extrémités vers le milieu, et mettre les objets rencontrés lors du parcours à gauche La valeur supérieure au pivot est échangée avec la valeur inférieure ou égale au pivot rencontrée dans le parcours à droite. Lorsque le parcours se rencontre, la valeur du pivot est insérée, ce qui rend les valeurs à gauche du pivot inférieures à ou. est égal au pivot et la valeur à droite du pivot est supérieure au pivot ; continuez Ensuite, utilisez la récursivité pour trier respectivement les côtés gauche et droit.
Grâce à l'analyse ci-dessus, nous pouvons voir que : chaque étape du tri par insertion consiste à rendre une sous-plage du tableau absolument ordonnée, et l'essence de chaque cycle est d'étendre continuellement cette sous-plage, nous pouvons donc voir que la direction de l'optimisation est de make Chaque parcours de boucle étend la sous-plage le plus rapidement possible, de sorte que l'optimisation ci-dessus consistant à insérer un élément par parcours en insérant deux éléments à la fois est optimisée. Bien sûr, quelqu’un se demandera certainement : pourquoi ne pas augmenter ce nombre ? Par exemple, 5 ou 10 sont insérés à chaque fois qu'il est parcouru. . . Évidemment, cela n'est pas possible. Un cas extrême consiste à insérer n éléments (n est la longueur du tableau) à chaque fois qu'il est parcouru. . . Quant au pourquoi, chacun peut répondre par lui-même.
Pour un tri rapide, chaque récursion fait en sorte que les sous-plages qui doivent être triées deviennent plus ordonnées, plutôt qu'absolument ordonnées ; donc pour un tri rapide, ses performances dépendent de la façon dont chaque opération récursive rend la sous-plage à trier plus ordonnée. Le facteur déterminant dans la mesure dans laquelle un sous-intervalle devient ordonné est, bien entendu, le nombre de récursions. La clé d'un tri rapide pour rendre le sous-intervalle relativement ordonné est le pivot, donc la direction de notre optimisation devrait également être le pivot. Ensuite, augmentez le nombre de pivots, et nous pouvons constater que l'augmentation du nombre de pivots n'affecte pas le nombre de pivots. récursions. Cela aura un impact important, et parfois cela peut même réduire le nombre de récursions. Une question similaire pour le tri par insertion est la suivante : combien de pivots doivent être augmentés ? Évidemment, la valeur du pivot ne peut pas être trop grande ; rappelez-vous que toute optimisation a un coût, et le coût de l'augmentation du pivot est caché dans le processus d'échange de position des éléments à chaque fois. Guanzi semble être un peu trop vendu. . . Jetons un coup d'œil à la façon dont le tri rapide est implémenté lorsque la valeur pivot est 2. Son processus de mise en œuvre n’est en fait pas difficile à comprendre :
1. Sélectionnez d'abord deux pivots. La méthode de sélection des pivots consiste à diviser le tableau en six segments de longueur égale. Ces six segments sont en fait séparés par 5 éléments, de petit à grand, et de supprimer le second. 4ème, comme pivot1 et pivot2 respectivement ;
2. Une fois le pivot sélectionné, traversez depuis les extrémités gauche et droite jusqu'au milieu. La condition d'arrêt pour le parcours gauche est de rencontrer une valeur supérieure ou égale à pivot1 et de marquer cette position comme étant inférieure à la condition d'arrêt pour la droite ; la traversée consiste à rencontrer une valeur inférieure ou égale à la valeur de pivot2 et à marquer cette position comme étant grande
3. Traversez ensuite en arrière à partir de la position inférieure. La position parcourue est représentée par k. Vous rencontrerez les situations suivantes :
a. Si la valeur de la position k est inférieure à pivot1, alors échangez les valeurs de la position k et de la position less, et ajoutez 1 à la valeur de less, cela fera les valeurs à gauche de la ; moins de position plus petite que pivot1, et les valeurs entre la position moins et la position k seront La valeur est supérieure ou égale à pivot1
b. Si la valeur à la position k est supérieure à pivot2, alors déplacez-vous de la grande position vers la gauche. La condition d'arrêt pour la traversée est de rencontrer une valeur inférieure ou égale à pivot2, écrivez. cette valeur à la position la plus petite, et écrivez la valeur à la position la plus petite. La valeur est écrite comme la position k, et la valeur de la position k est écrite comme la position la plus grande, et enfin less++, great--; pour être supérieur ou égal à pivot1, échanger la position k et la grande position, puis grand-
4. Après avoir terminé le processus ci-dessus, le sous-intervalle trié est divisé en trois segments (<pivot1, pivot1<=&&<=pivot2,>pivot2 Enfin, la récursivité est utilisée pour ces trois segments).
Copiez le code comme suit :
/*
*Partitionnement :
*
* partie gauche partie centrale partie droite
* +------------------------------------------------ ---------------+
* | < pivot1 | pivot1 <= && <= pivot2 > pivot2 |
* +------------------------------------------------ ---------------+
* ^ ^ ^
* |
* moins k super
*
*Invariants :
*
* all in (gauche, moins) < pivot1
* pivot1 <= tout en [moins, k) <= pivot2
* all in (super, à droite) > pivot2
*
* Le pointeur k est le premier index de la partie ?.
*/
Le contenu principal de l'implémentation du tri dans Jre7 est celui mentionné ci-dessus. Pour des détails spécifiques, veuillez vous référer au code de la classe correspondante. Si vous trouvez des erreurs ou des insuffisances, veuillez les corriger.