Einführung
QuickSort ist ein Divide-and-Conquer-Sortieralgorithmus. Er funktioniert, indem ein „Pivot“-Element aus dem Array ausgewählt und die anderen Elemente in zwei Teilarrays aufgeteilt werden, je nachdem, ob sie kleiner oder größer als das Pivot sind. Die Teilarrays werden dann rekursiv sortiert. Die durchschnittliche Zeitkomplexität von QuickSort ist O(n log n). Es sollte bemerkt werden, dass QuickSort keine stabile Sortierung ist, d. h., die relativen Positionen von gleichen Sortiergegenständen können nicht beibehalten werden.
Importiere die Arrays-Klasse
In diesem Schritt müssen Sie die Klasse java.util.Arrays importieren. Diese Klasse enthält mehrere Methoden zur Manipulation von Arrays, die verwendet werden, um int-Arrays in Strings umzuwandeln.
import java.util.Arrays;
Definiere die partition()-Methode
Definieren Sie eine Hilfsmethode namens partition(). Die partition()-Methode nimmt ein Array arr, einen Startindex low und einen Endindex high als Eingabe. Die partition()-Methode wird ein Element als Pivot auswählen und die Elemente so aufteilen, dass alle Elemente, die kleiner als das Pivot-Element sind, links vom Pivot liegen, und alle Elemente, die größer als das Pivot sind, rechts vom Pivot liegen. Das Pivot-Element wird an seine richtige Position platziert.
Die partition()-Methode wird den Index des partitionierten Elements zurückgeben. Das partitionierte Element ist die Position, an der das Pivot-Element platziert wird.
public static int partition(int[] arr, int low, int high) {
// Wählen Sie das Pivot-Element
int pivot = arr[high];
int i = (low - 1); // Index des kleineren Elements und gibt die rechte Position des bisher gefundenen Pivots an
for (int j = low; j <= high - 1; j++) {
// Wenn das aktuelle Element kleiner oder gleich dem Pivot ist
if (arr[j] <= pivot) {
i++; // Inkrementieren Sie den Index des kleineren Elements
// Tauschen Sie arr[i] und arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Tauschen Sie arr[i + 1] und arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // Geben Sie den Partitionierungsindex zurück
}
Definiere die quicksort()-Methode
Definieren Sie eine Sortier-Methode namens quicksort(). Die quicksort()-Methode nimmt ein Array arr, einen Startindex low und einen Endindex high als Eingabe. Die quicksort()-Methode wird das Array arr[] rekursiv sortieren.
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi ist der Partitionierungsindex, arr[p] ist jetzt
// an der richtigen Stelle
int pi = partition(arr, low, high);
// Sortieren Sie die Elemente rekursiv vor
// der Partitionierung und nach der Partitionierung
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
Erstelle und weise einem Integer-Array zu
Erstellen Sie und weisen Sie ganzzahlige Arrays, die sortiert werden sollen, dem Feld arr zu.
int[] arr = {7, 9, 1, 2, 10, 15, 6};
Implementiere QuickSort
Rufen Sie die quickSort()-Methode mit dem Feld arr als Eingabe auf, zusammen mit dem Anfangs- und Endindex des Arrays. Sortieren Sie und geben Sie das Array mithilfe der Methode Arrays.toString(arr) aus.
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
Teste mit mehreren Arrays
Testen Sie Ihre QuickSort-Implementierung mit Arrays mit verschiedenen Eigenschaften.
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
Wähle das Pivot zufällig
In diesem Schritt müssen wir in jeder Iteration den Pivot-Wert zufällig auswählen, um den schlechtesten Fall zu vermeiden. Um dies zu erreichen, werden wir die partition()-Methode aktualisieren und die folgende Zeile ersetzen:
int pivot = arr[high];
durch diese Zeile:
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
Teste mit einem zufällig ausgewählten Pivot-Element
Testen Sie Ihre QuickSort-Implementierung mit zufälligen Pivot-Elementen.
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
Behandle Randfälle
In diesem Schritt werden wir die Sonderfälle behandeln, die QuickSort abdecken kann. Definieren Sie diese Sonderfälle als ganzzahlige Arrays.
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
Vollständiger Code
Der vollständige Code für QuickSort in Java Lab ist unten angegeben.
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Quick Sort Implementation in Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}
Zusammenfassung
In diesem Lab wurde ein schrittweise Leitfaden zur Implementierung des QuickSort-Algorithmus in Java bereitgestellt. Wir haben gelernt, dass das Auswählen des Pivot-Werts ein entscheidender Schritt bei QuickSort ist und dass verschiedene Techniken zum Auswählen des Pivot-Werts die Leistung des Algorithmus beeinflussen können. QuickSort eignet sich am besten zum Sortieren großer Datenmengen. Die schlechteste Zeitkomplexität von QuickSort beträgt O(N^2), während seine durchschnittliche und beste Zeitkomplexität O(NLogN) ist.
