Einführung in den Quick Sort-Algorithmus
Sowohl Quick Sort als auch Merge Sort verwenden die Divide-and-Conquer-Methode zum Entwerfen von Algorithmen. Der Unterschied besteht darin, dass Merge Sort das Array nach dem Sortieren in zwei Unterarrays mit grundsätzlich gleicher Länge unterteilt , sie müssen zusammengeführt werden (Zusammenführen), und die schnelle Sortierung ist beim Aufteilen eines Benchmark-Elements kleiner als das Benchmark-Element Die rechten sind nicht kleiner als das Benchmark-Element. Auf diese Weise müssen Sie nur die beiden Unterarrays trennen und müssen keine Zusammenführungsoperationen wie die Zusammenführungssortierung mehr durchführen. Die Auswahl der Referenzelemente hat großen Einfluss auf die Effizienz des Algorithmus. Im besten Fall sind die beiden Subarrays grundsätzlich gleich groß. Der Einfachheit halber wählen wir das letzte Element aus. Ein fortgeschrittenerer Ansatz kann zunächst einen Median ermitteln und den Median mit dem letzten Element austauschen und dann die gleichen Schritte ausführen. Das Aufteilen ist der Kern von Quicksort. Die Laufzeit der Schnellsortierung im ungünstigsten Fall beträgt O(n2), die erwartete Laufzeit beträgt jedoch O(nlgn).
Java-Implementierung des Schnellsortierungsalgorithmus
1. Teilen Sie das Array in zwei Unterarrays plus ein Basiselement auf: Wählen Sie das letzte Element als Basiselement aus und die Indexvariable zeichnet die Position des aktuellsten auf Element, das kleiner als das Basiselement ist, wird auf start-1 initialisiert. Wenn ein neues Element gefunden wird, das kleiner als das Basiselement ist, wird der Index um 1 erhöht. Vom ersten bis zum vorletzten Element wird es nacheinander mit dem Basiselement verglichen. Wenn es kleiner als das Basiselement ist, wird der Index um 1 erhöht und der Positionsindex und das Element an der aktuellen Position ausgetauscht. Nachdem die Schleife beendet ist, ruft Index+1 die Position ab, an der sich das Basiselement befinden sollte, und tauscht Index+1 mit dem letzten Element aus.
2. Sortieren Sie die beiden Unterarrays [Start, Index] bzw. [Index+2, Ende]
Implementieren Sie zunächst wie bei der „Java-Implementierung von Insertsort“ eine Array-Tool-Klasse. Der Code lautet wie folgt:
public class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("{");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
public static void exchangeElements(int[] array, int index1, int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}Die Java-Implementierung und der Testcode der Schnellsortierung lauten wie folgt:
public class QuickSort {
public static void main(String[] args) {
int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3 };
System.out.println("Before sort:");
ArrayUtils.printArray(array);
quickSort(array);
System.out.println("After sort:");
ArrayUtils.printArray(array);
}
public static void quickSort(int[] array) {
subQuickSort(array, 0, array.length - 1);
}
private static void subQuickSort(int[] array, int start, int end) {
if (array == null || (end - start + 1) < 2) {
return;
}
int part = partition(array, start, end);
if (part == start) {
subQuickSort(array, part + 1, end);
} else if (part == end) {
subQuickSort(array, start, part - 1);
} else {
subQuickSort(array, start, part - 1);
subQuickSort(array, part + 1, end);
}
}
private static int partition(int[] array, int start, int end) {
int value = array[end];
int index = start - 1;
for (int i = start; i < end; i++) {
if (array[i] < value) {
index++;
if (index != i) {
ArrayUtils.exchangeElements(array, index, i);
}
}
}
if ((index + 1) != end) {
ArrayUtils.exchangeElements(array, index + 1, end);
}
return index + 1;
}
}Weitere Artikel zur Java-Implementierung des Schnellsortierungsalgorithmus (Quicktsort ), achten Sie bitte auf die chinesische PHP-Website!
