Sort rapide normal
Trouvez une base de valeur de base, puis triez-la en un seul voyage afin que les nombres à gauche de la base soient plus petits que la base, et les nombres à droite de la base sont supérieurs ou égaux à la base. Puis divisez-le en triage de sous-réseaux. Récursif comme ça.
classe publique Quicksort {public static <t étend comparable <? super t >> void tri (t [] arr) {tri (arr, 0, arr.length - 1);} public statique <t étend comparable <? super t >> void tri (t [] arr, int gauche, int droit) {if (gauche> = droit) retour; int p = partition (arr, gauche, droite); tri (arr, gauche, p - 1); tri (arr, p + 1, droit);} privé statique <t étend comparable <? super t >> int partition (t [] arr, int Left, int droit) {t base = arr [gauche]; int j = gauche; pour (int i = gauche + 1; i <= droit; i ++) {if (base.compareto (arr [i])> 0) {j ++; swap (arr, j, i);}} swap (arr, gauche, j); renvoie j; // renvoyer le coin inférieur de la base de la base de la base (arrondie, gauche, j); Tri} public static void swap (objet [] arr, int i, int j) {if (i! = j) {object temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} private static printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t");} System.out.println ();} public static void main (String args []) {Integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printr (arr); // 3 5 1 7 2 9 8 0 4 6Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Optimisation rapide du tri: sélectionnez au hasard la base de valeur de base
Lorsque le tableau est presque commandé, les performances d'ordre rapide sont médiocres (car après chaque commande, la taille récursive des sous-marins gauche et droite est très différente, et la plus grande partie est susceptible d'atteindre O (n ^ 2) à la fin).
Solution: La valeur de référence est sélectionnée au hasard, plutôt que de prendre le premier numéro à chaque fois. Cela ne sera pas dérangé par des "tableaux presque ordonnés". Mais les performances de tri des "tableaux presque hors service" peuvent baisser légèrement, au moins il y a plus de la partie échangée avant le tri. Cet échange n'a pas de sens dans l'ordre ... il y a beaucoup de composants "chance" ...
classe publique Quicksort {public static <t étend comparable <? super t >> void tri (t [] arr) {tri (arr, 0, arr.length - 1);} public statique <t étend comparable <? super t >> void tri (t [] arr, int gauche, int droit) {if (gauche> = droit) retour; int p = partition (arr, gauche, droite); tri (arr, gauche, p - 1); tri (arr, p + 1, droit);} privé statique <t étend comparable <? super t >> int partition (t [] arr, int Left, int droit) {// Avant de tri, laissez la valeur de référence être échangée avec un nombre aléatoire. De cette façon, la valeur de référence est aléatoire. // Cela ne fera pas que l'échelle récursive des côtés gauche et droite soit incohérente lorsque le tableau est relativement commandé, ce qui entraîne le pire échange de complexité de temps (arr, gauche, (int) (math.random () * (droite - gauche + 1) + gauche)); t base = arr [gauche]; int j = gauche; pour (int i = gauche + 1; i <= droit; > 0) {j ++; swap (arr, j, i);}} swap (arr, gauche, j); return j; // renvoie le coin inférieur de la valeur de référence après un tri mensonge} public static swap (objet [] arr, int i, int j) {if (i! = J) {objet temp = arr [i]; arr [i] = arr [j]; atr [j] = temp = Temp; printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t");} system.out.println ();} public static void main (String args []) {enter [] arr = {3, 5, 1, 7, 9, 8, 0, 4, 6}; imprimer); 0 4 6Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Le tri rapide continue d'optimiser: utiliser le tri des inserts en conjonction
L'ordre rapide est de réduire en continu l'échelle du problème pour résoudre les sous-problèmes et nécessite une récursivité continue. Cependant, la récursivité est suffisamment petite, et si cette récursivité instable + continue d'être exécutée, l'efficacité peut ne pas être très bonne.
Ainsi, lorsque le problème est petit et presque ordonné, le tri de l'insertion fonctionne bien. Vous pouvez souvent voir de tels commentaires dans Arrays.Sort () qui est livré avec Java: "Utilisez un tri d'insertion sur de minuscules tableaux", "Tri d'insertion sur les plus petits tableaux"
classe publique Quicksort {public static <t étend comparable <? super t >> void tri (t [] arr) {tri (arr, 0, arr.length - 1, 16);} / ** * @param array array à tri * @param gauche à gauche * @param à droite à droite * @param k lorsque le tri rapide revient à l'échelle de la sous-pré-supplé étend comparable <? super t >> void tri (t [] arr, int gauche, int droit, int k) {// Les heures d'échelle sont triées par insertion if (droite - gauche <= k) {insertionSort (arr, arr, droite); return;} int p = partition (arr, gauche, droite); tri (arr, gauche, p - 1, k); super t >> void insertionsort (t [] arr, int l, int r) {for (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i - 1; for (j> = 0 && cur.compareto (arr [j]) <0; j--) {arr [j + 1] = arr [j]; <T étend comparable <? super t >> int partition (t [] arr, int Left, int droit) {// Avant de tri, laissez la valeur de référence échanger avec un nombre aléatoire. De cette façon, la valeur de référence est aléatoire. // Cela ne fera pas incohérent l'échelle récursive des côtés gauche et droit lorsque le tableau est relativement ordonné, ce qui entraîne le pire échange de complexité de temps (arr, gauche, (int) (math.random () * (droite - gauche + 1) + gauche)); t base = arr [gauche]; int j = gauche; pour (int i = gauche + 1; i <= droit; i ++) {if (bas. 0) {j ++; swap (arr, j, i);}} swap (arr, gauche, j); return j; // renvoie le coin inférieur de la valeur de base après le tri menti} public static Void swap (objet [] arr, int i, int j) {if (i! = J) {objet temp = arr [i]; arr [i] = arr [j]; printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t");} system.out.println ();} public static void main (String args []) {enter [] arr = {3, 5, 1, 7, 9, 8, 0, 4, 6}; imprimer); 0 4 6Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Le tri rapide continue d'optimiser: tri rapide à deux voies
Dans le tri rapide normal initial, il est dit que la valeur de base sur le côté gauche de la base est plus petite que la base, tandis que la base sur le côté droit est supérieure ou égale à la base. Celles-ci égales à la base se réuniront à droite (ou légèrement modifier la relation de taille se réunira à gauche). Quoi qu'il en soit, il se rassemblera de côté. Lorsque de nombreux nombres sont répétés dans le tableau, cela entraînera une énorme différence de taille des deux sous-marins. À l'heure actuelle, je veux attribuer les nombres égaux à la base aux deux côtés de la base, au lieu de les réunir.
(Remarque: Lors du test du code, il est préférable de détourner la partie du tri de l'insertion et de ressembler à mon code ci-dessous ... sinon, lorsque le volume de données est inférieur à K = 16, le tri d'insertion est effectué ...)
classe publique Quicksort {public static <t étend comparable <? super t >> void tri (t [] arr) {tri (arr, 0, arr.length - 1, 16);} / ** * @param array array à tri * @param gauche à gauche * @param à droite à droite * @param k lorsque le tri rapide revient à l'échelle de la sous-pré-supplé étend comparable <? super t >> void tri (t [] arr, int Left, int droit, int k) {// insertionsort (arr, gauche, droite); // return; //} if (gauche> = droit) retour; int p = partition (arr, gauche, droite); tri (arr, gauche, droite); tri (arr, gauche, p - 1, k); super t >> void insertionsort (t [] arr, int l, int r) {for (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i - 1; for (j> = 0 && cur.compareto (arr [j]) <0; j--) {arr [j + 1] = arr [j]; <T étend comparable <? super t >> int partition (t [] arr, int Left, int droit) {// Avant de tri, laissez la valeur de référence échanger avec un nombre aléatoire. De cette façon, la valeur de référence est aléatoire. // Cela ne fera pas que les échelles récursives des côtés gauche et droite soient incohérentes lorsque le tableau est relativement ordonné, ce qui entraîne le pire échange de complexité de temps (Arr, gauche, (int) (math.random () * (droite - gauche + 1) + gauche)); t base = arr [gauche]; // valeur de base, lancer cette valeur de référence, voir It It It the to-to to-there de gauche + 1 ...... 1; // Pour l'intervalle [gauche + 1 ......... à droite] mentionné dans la ligne précédente, je signifie [gauche + 1 ...... i) l'intervalle ouvert fermé à droite gauche est inférieur ou égal à la base. int j = droit; // pour l'intervalle [gauche + 1 ...... à droite] mentionné dans les deux lignes précédentes, j signifie que les valeurs de (J ...... à droite] gauche ouverte et droite intervalles fermés sont plus importants ou égaux à la base. Out le premier élément plus petit que la base, puis j s'arrête là. statique void swap (objet [] arr, int i, int j) {if (i! = j) {objet temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} private static void printarr (objet [] arr) {for (objet o: arr) {System.out.print (o); System.out.print ("/ t");} System.out.println ();} public static void main (String args []) {Integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printr (arr); // 3 5 1 7 2 9 8 0 4 6Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Continuez à optimiser le tri rapide: deux tri rapides ne nécessitent pas d'échange, utilisez l'échange
Lorsque les deux chemins ci-dessus trouvent des valeurs supérieures à la base et des valeurs inférieures à la base, elles utilisent la méthode swap () pour échanger. L'échange à deux chiffres implique le fonctionnement de la troisième température variable, avec plus d'opérations de lecture et d'écriture. Ensuite, utilisez la méthode d'attribution directe pour placer moins que à droite et la plus grande que à gauche. Lorsque moi et J nous rencontrons, cette position est où la base doit être placée. Ce voyage est terminé. Juste recurser.
classe publique Quicksort {public static <t étend comparable <? super t >> void tri (t [] arr) {tri (arr, 0, arr.length - 1, 16);} / ** * @param array array à tri * @param gauche à gauche * @param à droite à droite * @param k lorsque le tri rapide revient à l'échelle de la sous-pré-supplé étend comparable <? super t >> void tri (t [] arr, int Left, int droit, int k) {// insertionsort (arr, gauche, droite); // return; //} if (gauche> = droit) retour; int p = partition (arr, gauche, droite); tri (arr, gauche, droite); tri (arr, gauche, p - 1, k); super t >> void insertionsort (t [] arr, int l, int r) {for (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i - 1; for (j> = 0 && cur.compareto (arr [j]) <0; j--) {arr [j + 1] = arr [j]; <T étend comparable <? super t >> int partition (t [] arr, int Left, int droit) {// Avant de tri, laissez la valeur de référence échanger avec un nombre aléatoire. De cette façon, la valeur de référence est aléatoire. // Cela ne fera pas que les échelles récursives des côtés gauche et droite soient incohérentes lorsque le tableau est relativement ordonné, ce qui entraîne le pire échange de complexité de temps (arrond, gauche (int) (math.random () * (droite - gauche + 1) + gauche)); t base = arr [gauche]; // valeur de base, lancement de cette valeur de référence, voir comme le type de [gauche + 1 ..... i = gauche; // Pour l'intervalle [gauche + 1 ......... à droite] mentionné dans la ligne précédente, je signifie [gauche + 1 ...... i) Les valeurs d'intervalle fermées à feuilles gauche sont inférieures ou égales à la base. int J = à droite; // pour l'intervalle [gauche + 1 ...... à droite] mentionné dans les deux lignes précédentes, j signifie que les valeurs de (J ...... à droite] à gauche et les intervalles à feuilles droits sont supérieures ou égales à la base. = arr [j]; // Scan de gauche à droite, scanner le premier élément plus grand que la base, puis je s'arrête là. (i! = j) {objet temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} private static void printarr (objet [] arr) {for (objet o: arr) {system.print (o); system.out.print ("/ t");} system.out.println ();} {Entier [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Le tri rapide continue d'optimiser: Lorsqu'une grande quantité de données et de nombreuses répétitions sont utilisées, utilisez un tri rapide à trois voies
Divisez le tableau en trois chemins. Le premier chemin est plus petit que la base, le deuxième chemin est égal à la base et le troisième chemin est supérieur à la base.
Utilisez un pointeur pour scanner de l'avant en arrière, si:
1. Le nombre indiqué par Cur est inférieur à la base, puis: échangez les valeurs de arr [Cur] et Arr [i], puis I ++, Cur ++.
2. Le nombre pointé par Cur est égal à la base, puis: Cur ++
3.
Lorsque Cur> J, cela signifie que les trois chemins ont été achevés.
classe publique Quicksort {public static <t étend comparable <? super t >> void tri (t [] arr) {tri (arr, 0, arr.length - 1, 16);} / ** * @param array array à tri * @param gauche à gauche * @param à droite à droite * @param k lorsque le tri rapide revient à l'échelle de la sous-pré-supplé étend comparable <? super t >> void tri (t [] arr, int gauche, int droit, int k) {// insertionsort (arr, gauche, droite); // return; //} if (gauche> = droit) return; int [] ret = partition (arr, gauche, droite); tri (arr, gauche, ret [0], k); tri (arr, ret [1], droit, k);} public static <t se compare <? super t >> void insertionsort (t [] arr, int l, int r) {for (int i = l + 1; i <= r; i ++) {t cur = arr [i]; int j = i - 1; for (j> = 0 && cur.compareto (arr [j]) <0; j--) {arr [j + 1] = arr [j]; * @param Array à trier * @param a gauche la limite gauche du tableau à tri * @param à droite la limite de droite du tableau à tri * @param <T> génériques * @return * / privé statique <t étend comparable <?? super t >> int [] partition (t [] arr, int Left, int droit) {// Avant de tri, laissez la valeur de référence être échangée avec un nombre aléatoire. De cette façon, la valeur de référence est aléatoire. // Cela ne fera pas que les échelles récursives sur les côtés gauche et droite soient incompatibles lorsque le tableau est relativement d'ordre, ce qui entraîne le pire échange de complexité de temps (arrond, gauche, (int) (math.random () * (valeur de base à droite + 1) + gauche)); t base = arr [gauche]; // valeur de base, lancer cette valeur de référence, voir le plus rapide de la gauche à gauche + sont divisés en les trois canaux (intervalles) suivants int i = gauche; // gauche indique que [lleft ... gauche) Les nombres dans l'intervalle ouvert fermé à droite gauche sont plus petits que la base int J = droite; // gauche indique que (Rright ... à droite] Les nombres à gauche et à droite intervalles fermés sont plus grands que la base int Cur = i; // Utiliser Cur pour traverser la base pour la base. j) {if (arr [cur] .compareto (base) == 0) {cur ++;} else if (arr [cur] .compareto (base) <0) {swap (arr, cur ++, i ++);} else {swap (arr, cur, j--);}} Sous-Problem n'a besoin que de résoudre la gauche et la droite de I et J} public static void swap (objet [] arr, int i, int j) {if (i! = j) {objet temp = arr [i]; arr [i] = arr [j]; arr [j] = temp;}} private static void printarr (objet [] arr) {pour (objet o: arr) {System.out.print (o); System.out.print ("/ t");} System.out.println ();} public static void main (String args []) {Integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printr (arr); // 3 5 1 7 2 9 8 0 4 6Sort (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}Résumer
Ce qui précède est toute l'explication détaillée du code de tri rapide et d'optimisation de la programmation Java. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!