Eine Art Verbesserung der sprudelnden Sortierung besteht darin, dass die anfängliche Datensatzsequenz bestellt oder im Grunde genommen von Schlüsselwörtern bestellt wird, sie zu sprudelnden Sortierungen degeneriert. Das Rekursionsprinzip wird verwendet, und seine durchschnittliche Leistung ist am besten unter allen Sortiermethoden in der gleichen Größenordnung O (n longn). In Bezug auf die durchschnittliche Zeit gilt es derzeit als die beste interne Sortiermethode.
Die Grundidee ist: Teilen Sie die Daten, die zu zwei unabhängigen Teilen sortiert werden sollen, durch Lügensortier Das gesamte Sortierprozess kann rekursiv durchgeführt werden, um die gesamten Daten zu einer geordneten Sequenz zu erreichen.
Drei Zeiger: Der erste Zeiger wird als Pivotkey -Zeiger (Pivot) bezeichnet, der zweite Zeiger und der dritte Zeiger sind linker Zeiger bzw. rechten Zeiger, der auf den linken Wert und den rechts höchsten Wert hinweist. Der linke Zeiger und der rechte Zeigeransatz von beiden Seiten bis zur Mitte gleichzeitig. Pivot in das obere Ende.
Es sind zwei Funktionen erforderlich:
① Rekursive Funktion öffentliche statische Leere Quicksort (int [] n, int links, int rechts)
② Segmentfunktion (eine schnelle Sortierfunktion) öffentliche statische Int -Partition (int [] n, int links, int rechts)
Java -Quellcode (erfolgreich ausführen):
Die Codekopie lautet wie folgt:
Paket Testsortalgorithmus;
öffentliche Klasse Quicksort {
public static void main (String [] args) {
int [] array = {49,38,65,97,76,13,27};
QuickSort (Array, 0, Array.Length - 1);
für (int i = 0; i <array.length; i ++) {
System.out.println (Array [i]);
}
}
/*Schreiben Sie zuerst den Algorithmus als Datenprototyp entsprechend dem Array und schreiben Sie dann den Skalierbarkeitsalgorithmus. Array {49,38,65,97,76,13,27}
* *//
public static void Quicksort (int [] n, int links, int rechts) {
Int Pivot;
if (links <rechts) {
// Drehzahl als Drehzahl, das kleinere Element liegt links und das größere Element befindet sich rechts
pivot = partition (n, links, rechts);
// Rufen Sie die schnelle Sortierung in linken und rechten Arrays rekursiv auf, bis die Bestellung vollständig korrekt ist
QuickSort (N, links, Pivot - 1);
QuickSort (N, Pivot + 1, rechts);
}
}
öffentliche statische Int -Partition (int [] n, int links, int rechts) {
int pivotkey = n [links];
// Der Drehpunkt wird sich nach der Auswahl nie ändern, und er wird irgendwann in der Mitte sein, mit kleinem Front und großem Rücken
while (links <rechts) {
while (links <rechts && n [rechts]> = Pivotkey) -Right;
// Bewegen Sie das Element kleiner als der Dreh- und Angelpunkt.
n [links] = n [rechts];
while (links <rechts && n [links] <= pivotkey) ++ links;
// Bewegen Sie das Element größer als der Dreh- und Angelpunkt.
n [rechts] = n [links];
}
// Wenn links == rechts eine schnelle Sortierreise abschließt.
n [links] = Pivotkey;
links zurückkehren;
}
}