Wie funktioniert die Quicksort Technik in Java-Arbeit?
Hier erfahren Sie, wie eines der am häufigsten verwendeten Sortiertechniken in Java tatsächlich funktioniert. Diese Technik nennt man Schnelle Sorte, und es ist eine sehr raffinierte Verwendung von Rekursion.
Für die meisten von uns, herauszufinden, wie Sortieralgorithmen wie Quicksort Arbeit lediglich eine intellektuelle Übung ist. Die Java-API hat die Sortierung in bereits gebaut.
Die Quicksort Technik sortiert ein Array von Werten durch Rekursion. Die grundlegenden Schritte sind also:
Pick einen beliebigen Wert, der im Bereich von Werten in der Matrix liegt.
Dieser Wert ist der Drehpunkt. Der häufigste Weg, den Drehpunkt zu wählen ist, einfach den ersten Wert im Array auswählen. Die Leute haben geschrieben, Doktorgrade auf mehr entwickelte Möglichkeiten, um einen Drehpunkt zu wählen, die in schneller Sortierung führt. Stick mit dem ersten Element in dem Array verwendet wird.
Neuanordnen der Werte in dem Array, so dass alle Werte, die kleiner als der Drehpunkt auf der linken Seite der Anordnung sind und alle Werte, die größer oder gleich dem Drehpunkt sind, sind auf der rechten Seite der Anordnung.
Das Drehwert gibt die Grenze zwischen der linken Seite und der rechten Seite der Anordnung. Es wird wahrscheinlich nicht Totpunkt, aber das spielt keine Rolle. Dieser Schritt wird aufgerufen Partitionierung, und die linken und rechten Seiten der Arrays Partitionen.
Nun hat jeder der beiden Abschnitte des Arrays behandeln als separate Array, und von vorn beginnen mit Schritt 1 für diesen Abschnitt.
Das ist der rekursive Teil des Algorithmus.
Der schwierigste Teil des Quicksort-Algorithmus ist die Teilungsschritt, der die Partition neu anordnen müssen, damit alle Werte, die kleiner ist als der Drehpunkt sind auf der linken Seite und alle Elemente, die größer ist als der Drehpunkt sind auf der rechten Seite. Nehmen wir an, dass das Array diese zehn Werte:
38 17 58 22 69 31 88 28 86 12
Hier ist der Drehpunkt 38, und die Aufgabe des Unterteilungsschritt wird das Array zu so etwas zu ordnen:
17 12 22 28 31 38 88 69 86 58
Beachten Sie, dass die Werte immer noch nicht in Ordnung sind. Die Anordnung hat jedoch 38 um den Wert aufgeteilt: Alle Werte, die weniger als 38 auf der linken Seite von 38 sind, und alle Werte, die größer als 38 sind auf der rechten Seite von 38 sind.
Jetzt können Sie das Array in zwei Partitionen auf dem Wert teilen 38 und wiederholen Sie den Vorgang für jede Seite. Der Drehwert selbst geht mit der linken Partition, so dass die linke Partition ist dies:
17 12 22 28 31 38
Diese Zeit nimmt der Unterteilungsschritt 17 als Drehpunkt und ordnet die Elemente wie folgt:
12 17 22 28 31 38
Wie Sie sehen können, ist dieser Teil des Arrays jetzt sortiert. Leider hat realisieren Quicksort nicht an diesem Punkt, dass, so dass es noch ein paar Rekursion führt sicher zu sein. Aber das ist der grundlegende Prozess.