Schnellsortieralgorithmuskonzept
Die schnelle Sortierung basiert im Allgemeinen auf rekursiver Implementierung. Die Idee ist wie folgt:
1. Wählen Sie einen geeigneten Wert aus (der ideale Wert ist der beste, aber der erste Wert im Array wird in der Implementierung im Allgemeinen verwendet), was als "Pivot" bezeichnet wird.
2. Aufgrund dieses Wertes unterteilen Sie das Array in zwei Teile, den kleineren Teil links und den größeren Teil rechts.
3. Es ist sicher, dass nach einer solchen Runde die Position dieses Drehes an der endgültigen Position sein muss.
V.
5. Sortierung ist abgeschlossen.
Grundlegende Implementierungsmethode:
public static void QuickSort (int [] arr) {qsort (arr, 0, arr.length-1);} private statische void QSORT (int [] arr, int niedrig, int hoch) {if (niedrig <hoch <hoch) {int pivot = partition (arr, niedrig, hoch); // das Array in zwei Teile qsort (arr, niedrig, pivot-1) unterteilen; // Sortieren Sie die linke Subarray Qsort (arr, pivot+1, hoch); // Sortieren Sie das rechte SubaRray rekursiv // Pivot Record while (niedrig <hoch) {while (niedrig <hoch && arr [hoch]> = pivot) ---hoh; arr [niedrig] = arr [hoch]; // Swap -Aufzeichnungen kleiner als der Drehpunkt links (niedrig <hoch && arr [niedrig] <= pivot) ++ niedrig; arr [hoch] = arr [niedrig]; // Swap -Datensätze kleiner als der Drehpunkt am rechten Ende} // Scan ist abgeschlossen, und der Drehpunkt ist an Ort und Stelle angelegt [niedrig] = Pivot; // Die Position des Drehzahl auf die Rückgabe niedrig zurücksetzt;}Verwenden Sie Generics, um einen Algorithmus schneller Ordnung zu implementieren
Im Folgenden finden Sie eine QuickSort -Klasse, die die statische Funktionsart () enthält, die Arrays jeglicher Art sortieren kann. Wenn es sich um ein Array von Objekttypen handelt, muss der Objekttyp die vergleichbare Schnittstelle so implementieren, dass die Vergleichsfunktion zum Vergleich verwendet werden kann.
Der grundlegendste Fast-Row-Sortieralgorithmus wurde verwendet und es wurde keine Optimierungsverarbeitung durchgeführt.
Der Quellcode lautet wie folgt:
Import Java.util.LinkedList; Import Java.util.List; Import Java.util.Listiterator; Import Java.util.random; öffentliche Klasse Quicksort {@SuppressWarnings ("Deaktiviert") // den obigen Schnellrow-Funktionsprototyp so ändern, dass es Arrays eines beliebigen Objekttyps sortiert. Diese Funktion wird intern verwendet, und die externe Sortierungsfunktionsschnittstelle ist sort (). Die Sortierfunktion erfordert, dass das Objekt die vergleichbare Schnittstelle implementieren muss, die die Erkennung von Kompilierzeittypen liefern kann, siehe den folgenden Artikel. private statische void QuickSort (Objekt [] in, int begin, int end) {if (begin == Ende || begin == (end-1)) return; Objekt p = in [begin]; int a = beginnen +1; int b = a; für (; b <end; b ++) {// Dieses Objekttyp -Array muss die vergleichbare Schnittstelle so implementieren, dass Sie die Vergleichsfunktion zum Vergleich verwenden können, wenn ((vergleichbares <elements>) in [b]). Vergleiche (p) <0) {if (a == b) {a ++; Fortsetzung;} Objekt temp = in [a]; in [a] = in [b]; in [b] = temp; a ++; }} in [begin] = in [a-1]; in [a-1] = p; if (a-1> begin) {quicksort (in, begin, a); } if (end-1> a) {quicksort (in, a, end); } zurückkehren; } // Verwenden Sie Generics, um ein Objektarray zu sortieren, das Objekttyp -Array muss die vergleichbare Schnittstelle Public static <t vergleichbar <? super t >> void sort (t [] input) {quicksort (input, 0, input.length); } // Fügen Sie die Funktion der Sortierlisten -Objekte hinzu, siehe Sort () -Funktion der Java.util.Collections -Klasse in Java Public static <T erweitert vergleichbar <? Super t >> void sort (list <t> list) {Object [] t = list.toArray (); // Die Liste in ein Array QuickSort (t, 0, t.Length) konvertieren; // Sortieren Sie das Array // Nach Abschluss der Array -Sortierung schreiben Sie in die ListlistItiterator <T> i = list.listiterator () zurück; für (int j = 0; j <t.Length; j ++) {i.Next (); I.Set ((t) t [j]); }} // Da Generika nicht in Java, primitiven Datentypen (int, doppelte, byte usw.) verwendet werden können, können Sie den Funktionsüberladungsmechanismus nur verwenden, um diese primitiven Arrays (int [], double [], byte [] usw.) zu sortieren. Um dieselbe Sortierfunktion zu teilen, wird der ursprüngliche Typ (Autoboxing, Unboxing) -Mechanismus verwendet, um ihn in den entsprechenden Objekttyp einzukapseln, ein neues Objektarray zu bilden, sie zu sortieren und dann zu decapsulatieren. Der Nachteil davon ist, dass zusätzliche Konvertierungsschritte und zusätzlichen Speicherplatz erforderlich sind, um das eingekapselte Array zu speichern. Eine andere Möglichkeit besteht darin, den Sortiercode in jede überlastete Funktion zu kopieren. Die Sort () -Funktion in der Klasse java.util.Arrays in der offiziellen API verwendet diese Methode, die aus dem Quellcode der Arrays -Klasse ersichtlich ist. public static void sort (int [] input) {Integer [] t = new Integer [input.length]; for(int i = 0; i < input.length; i++){ t[i] = input[i];//Encapsulation} quickSort(t,0,t.length);//Sorting for(int i = 0; i < input.length; i++){ input[i] = t[i];//Uncapsulation} } //Overload function of double[] array public static void sort(double[] input) {double [] t = new Double [input.length]; für (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); für (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Überlastungsfunktion von Byte [] Array public static void sort (byte [] input) {byte [] t = new byte [input.length]; für (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); für (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); für (int i = 0; i <input.length); Eingabe.Length; i ++) {input [i] = t [i]; }} // Short [] Überladungsfunktion public static void sortieren (kurz [] input) {Short [] t = new Short [input.length]; für (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); für (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Short [] Überladungsfunktion öffentliche statische void -Sortierung (char [] input) {Zeichen [] t = neues Zeichen [input.length]; für (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); für (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Überladungsfunktion von float [] Array public static void sortieren (float [] input) {float [] t = new float [input.length]; für (int i = 0; i <input.length; i ++) {t [i] = input [i]; } quicksort (t, 0, t.length); für (int i = 0; i <input.length; i ++) {input [i] = t [i]; }} // Die Hauptfunktion zum Testen öffentlicher statischer void main (String [] args) {// Erzeugen Sie ein int [] -Array, das aus zufälligen Zahlen besteht, um int len = 10 zu testen; int [] input = new int [len]; Random r = neu random (); System.out.print ("int [] vor dem Sortieren:"); für (int i = 0; i <input.length; i ++) {input [i] = r.Nextint (10*len); System.out.print (Eingabe [i] + ""); } System.out.println (); System.out.print ("int [] nach der Sortierung:"); sortieren (Eingabe); für (int i: input) {System.out.print (i + ""); } System.out.println (); // generieren Sie ein Array von Strings, um String [] S = new String [] {"B", "A", "E", "D", "F", "C"} zu testen; System.out.print ("String [] vor dem Sortieren:"); für (int i = 0; i <sength; i ++) {System.out.print (s [i]+""); } System.out.println (); System.out.print ("String [] nach der Sortierung:"); sortieren (s); für (int i = 0; i <sength; i ++) {System.out.print (s [i]+""); } System.out.println (); // generieren Sie eine Liste von Zeichenfolgen, um die Liste <string> l = new LinkedList <string> () zu testen; S = new String [] {"B", "A", "E", "D", "F", "C"}; System.out.print ("LinkedList <string> Bevor Sorting:"); für (int j = 0; j <sength; j ++) {l.add (s [j]); System.out.print (s [j] + ""); } System.out.println (); sortieren (l); System.out.print ("LinkedList <String> nach dem Sortieren:"); für (String ts: l) {System.out.print (ts + ""); } System.out.println (); }}Führen Sie den Hauptfunktionstest aus und können Sie aus der Ausgabe sehen, dass die QuickSort -Klasse normal funktioniert:
int [] vor dem Sortieren: 65 48 92 26 3 8 59 21 16 45Int [] Nach der Sortierung: 3 8 16 21 26 45 48 59 65 92String [] Vor dem Sortieren: Baedfc String [] Nach der Sortierung: ABCDEF LinkedList <string> vor dem Sortieren: Baedfc LinkedList <StRING> After Sorting: ABCDEF: ABCDEF: ABCDEF: ABCDEF: ABCDEf