Concept d'algorithme de tri rapide
Le tri rapide est généralement basé sur une implémentation récursive. L'idée est la suivante:
1. Sélectionnez une valeur appropriée (la valeur idéale est la meilleure, mais la première valeur du tableau est généralement utilisée dans l'implémentation), ce qui est appelé "pivot".
2. En fonction de cette valeur, divisez le tableau en deux parties, la partie plus petite à gauche et la plus grande partie à droite.
3. Il est certain qu'après un tel tour, la position de ce pivot doit être en position finale.
4. Répétez le processus ci-dessus pour les deux sous-réseaux jusqu'à ce qu'il n'y ait qu'un seul élément par tableau.
5. Le tri est terminé.
Méthode d'implémentation de base:
public static void QuickSort (int [] arr) {qsort (arr, 0, arr.length-1);} private static void qsort (int [] arr, int low, int high) {if (low <high) {int pivot = partition (arr, low, high); // Divisez le tableau en deux parties QSORT (arr, bas, pivot-1); // trie le sous-réseau gauche QSORT (arr, pivot + 1, haut); // trie le bon sous-réseau récursivement}} partition statique privée intatique (int [] arr, int low, int high) {int pivot = arr [Low]; // Pivot Record While (Low <High) {while (Low <High && arr [high]> = pivot) --high; arr [Low] = arr [high]; // échange des enregistrements plus petits que le pivot vers la gauche tandis que (faible <high && arr [bas] <= pivot) ++ bas; arr [high] = arr [bas]; // échange des enregistrements plus petits que le pivot à l'extrémité droite} // Le scan est terminé, et le pivot est en place arr [bas] = pivot; // Renvoie la position du pivot au niveau bas;}Utilisez des génériques pour implémenter un algorithme d'ordre rapide
Vous trouverez ci-dessous une classe QuickSort, qui contient la fonction statique Sort (), qui peut trier les tableaux de tout type. S'il s'agit d'un tableau de types d'objets, le type d'objet doit implémenter l'interface comparable afin que la fonction Comparisonto puisse être utilisée à titre de comparaison.
L'algorithme de tri à ligne rapide le plus basique a été utilisé et aucun traitement d'optimisation n'a été effectué.
Le code source est le suivant:
Importer java.util.linkedList; import java.util.list; import java.util.listiterator; import java.util.random; classe publique Quicksort {@SuppressWarnings ("Unchecked") // modifie le prototype de fonction à rang rapide ci-dessus afin qu'il puisse trier les tableaux de n'importe quel type d'objet. Cette fonction est utilisée en interne et l'interface de fonction de tri externe est tri (). La fonction de tri nécessite que l'objet doit implémenter l'interface comparable, qui peut fournir une détection de type à temps de compilation, voir l'article suivant. private static void QuickSort (objet [] in, int begin, int end) {if (begin == end || begin == (end-1)) return; Objet p = dans [begin]; int a = begin +1; int b = a; pour (; b <end; b ++) {// Ce tableau de type d'objet doit implémenter l'interface comparable afin que vous puissiez utiliser la fonction compareto pour la comparaison if (((comparable <objet>) dans [b]). compareto (p) <0) {if (a == b) {a ++; continuer;} objet temp = dans [a]; Dans [a] = dans [b]; Dans [b] = temp; a ++; }} dans [begin] = dans [a-1]; Dans [A-1] = P; if (a-1> begin) {Quicksort (in, begin, a); } if (end-1> a) {Quicksort (in, a, end); } retour; } // Utiliser des génériques pour trier n'importe quel tableau d'objets, le tableau de type d'objet doit implémenter l'interface comparable publique statique <t étend comparable <? super t >> void tri (t [] input) {Quicksort (input, 0, input.length); } // Ajouter la fonction des objets de trieur de liste, reportez-vous à la fonction tri () de la classe java.util.collections dans Java public static <t étend comparable <? super t >> void tri (list <t> list) {object [] t = list.toArray (); // convertir la liste en un tableau quicksort (t, 0, t.length); // trier le tableau // Une fois le tri du tableau terminé, réécrivez dans la liste ListIterator <T> i = list.ListIterator (); pour (int j = 0; j <t.length; j ++) {i.next (); i.set ((t) t [j]); }} // Parce que les génériques ne peuvent pas être utilisés en Java, types de données primitifs (int, double, octet, etc.), vous ne pouvez utiliser le mécanisme de surcharge de la fonction pour trier ces tableaux primitifs (int [], double [], octet [], etc.). Afin de partager la même fonction de tri, le mécanisme de type d'origine (autoboxing, déballage) est utilisé pour le résumer dans le type d'objet correspondant, former un nouveau tableau d'objets, le trier puis le désencapsuler. L'inconvénient est qu'il nécessite des étapes de conversion supplémentaires et un espace supplémentaire pour économiser le réseau encapsulé. Une autre façon consiste à copier le code de tri dans chaque fonction surchargée. La fonction tri () dans la classe java.util.arrays dans l'API officielle utilise cette méthode, qui peut être vue à partir du code source de la classe Arrays. public static void tri (int [] input) {entier [] t = new Integer [input.length]; pour (int i = 0; i <input.length; i ++) {t [i] = input [i]; // encapsulation} Quicksort (t, 0, t.length); // tri pour (int i = 0; i <input.length entrée) {double [] t = new double [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (T, 0, T.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Fonction de surcharge du byte [] Array public static void tri (byte [] entrée) {byte [] t = new Byte [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (T, 0, T.Length); for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (T, 0, T.Length); for (int i = 0; i <input.length); input.length; i ++) {input [i] = t [i]; }} // Fonction de surcharge courte [] public static void tri (court-circuit) {short [] t = new short [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (T, 0, T.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // court [] fonction de surcharge public static void tri (char [] input) {caractères [] t = new Caracter [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (T, 0, T.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Fonction de surcharge de float [] array public static void tri (float [] input) {float [] t = new float [input.length]; for (int i = 0; i <input.length; i ++) {t [i] = input [i]; } Quicksort (T, 0, T.Length); for (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // La fonction principale pour tester le public static void main (String [] args) {// produit un tableau int [] composé de nombres aléatoires pour tester int len = 10; int [] input = new int [len]; Random r = new Random (); System.out.print ("int [] avant de trier:"); for (int i = 0; i <input.length; i ++) {input [i] = r.Nextint (10 * len); System.out.print (entrée [i] + ""); } System.out.println (); System.out.print ("int [] après tri:"); tri (entrée); for (int i: input) {System.out.print (i + ""); } System.out.println (); // générer un tableau de chaînes pour tester la chaîne [] s = new String [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("String [] avant de trier:"); for (int i = 0; i <s.length; i ++) {System.out.print (s [i] + ""); } System.out.println (); System.out.print ("String [] après tri:"); tri (s); for (int i = 0; i <s.length; i ++) {System.out.print (s [i] + ""); } System.out.println (); // Générez une liste de chaînes pour tester la liste <string> l = new LinkedList <string> (); s = new String [] {"b", "a", "e", "d", "f", "c"}; System.out.print ("LinkedList <string> avant le tri:"); pour (int j = 0; j <s.length; j ++) {l.add (s [j]); System.out.print (S [J] + ""); } System.out.println (); tri (l); System.out.print ("LinkedList <string> après tri:"); for (String ts: l) {System.out.print (ts + ""); } System.out.println (); }}Exécutez le test de fonction principale et à partir de la sortie, vous pouvez voir que la classe Quicksort fonctionne normalement:
int [] avant le tri: 65 48 92 26 3 8 59 21 16 45int [] APRÈS TROI: 3 8 16 21 26 45 48 59 65 92STRING [] Avant le tri: Baedfc String [] après tri: ABCDEF LinkedList <string>