Den Schnellsortierungsalgorithmus verstehen (mit Beispielen in Java)

Detaillierte Erklärung des QuickSort-Algorithmus: ein effizientes Sortierwerkzeug

QuickSort ist ein effizienter Sortieralgorithmus, der auf der Divide-and-Conquer-Strategie basiert. Die Divide-and-Conquer-Methode zerlegt das Problem in kleinere Teilprobleme, löst diese Teilprobleme separat und kombiniert dann die Lösungen der Teilprobleme, um die endgültige Lösung zu erhalten. Bei der Schnellsortierung wird ein Array durch Auswahl eines Partitionselements geteilt, das den Teilungspunkt des Arrays bestimmt. Vor der Partitionierung wird die Position des Partitionierungselements neu angeordnet, sodass es vor dem Element liegt, das größer als es ist, und nach dem Element, das kleiner als es ist. Das linke und das rechte Subarray werden auf diese Weise rekursiv aufgeteilt, bis jedes Subarray nur noch ein Element enthält. An diesem Punkt wird das Array sortiert.

So funktioniert die Schnellsortierung

Lassen Sie uns als Beispiel das folgende Array in aufsteigender Reihenfolge sortieren:

Schritt 1: Wählen Sie das Pivot-Element aus

Wir wählen das letzte Element als Drehpunkt:

Schritt 2: Pivot-Elemente neu anordnen

Wir platzieren das Pivot-Element vor Elementen, die größer als es sind, und nach Elementen, die kleiner als es sind. Dazu durchlaufen wir das Array und vergleichen den Pivot mit jedem Element davor. Wird ein Element gefunden, das größer als der Pivot ist, erstellen wir einen zweiten Zeiger dafür:

Wenn ein Element gefunden wird, das kleiner als der Pivot ist, tauschen wir es mit dem zweiten Zeiger aus:

Wiederholen Sie diesen Vorgang, indem Sie das nächste Element, das größer als der Pivot ist, auf den zweiten Zeiger setzen und austauschen, wenn ein Element gefunden wird, das kleiner als der Pivot ist:

Setzen Sie diesen Vorgang fort, bis Sie das Ende des Arrays erreicht haben:

Nach Abschluss des Elementvergleichs wurde das Element, das kleiner als der Pivot ist, nach rechts verschoben, dann tauschen wir den Pivot mit dem zweiten Zeiger:

Schritt 3: Teilen Sie das Array

Teilen Sie das Array entsprechend dem Partitionsindex. Wenn wir das Array als arr[start..end] darstellen, können wir durch Teilen des Arrays durch Partition das linke Unterarray arr[start..partitionIndex-1] und erhalten das rechte Subarray arr[partitionIndex 1..end].

Fahren Sie mit der Aufteilung der Subarrays auf diese Weise fort, bis jedes Subarray nur noch ein Element enthält:

An diesem Punkt ist das Array sortiert.

Schnelle Sortiercode-Implementierung

import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 将最后一个元素设置为枢轴
        int pivot = arr[end];
        // 创建指向下一个较大元素的指针
        int secondPointer = start-1;

        // 将小于枢轴的元素移动到枢轴左侧
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交换元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 将枢轴与第二个指针交换
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分区索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分区索引
            int partitionIndex = partition(arr, start, end);
            // 递归调用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}

Codeinterpretation

quickSort-Methode: Rufen Sie zuerst die partition-Methode auf, um das Array in zwei Unterarrays zu unterteilen, und rufen Sie dann quickSort rekursiv auf, um das linke und das rechte Unterarray zu sortieren. Dieser Vorgang wird fortgesetzt, bis alle Unterarrays genau ein Element enthalten. An diesem Punkt wird das Array sortiert.

partition Methode: Verantwortlich für die Aufteilung des Arrays in zwei Unterarrays. Zuerst werden der Pivot und der Zeiger auf das nächstgrößere Element gesetzt, dann wird das Array durchlaufen, wobei Elemente, die kleiner als der Pivot sind, nach links verschoben werden. Danach tauscht es den Pivot mit dem zweiten Zeiger und gibt die Partitionsposition zurück.

Führen Sie den obigen Code aus. Die Konsole gibt Folgendes aus:

Unsortiertes Array: [8, 6, 2, 3, 9, 4] Sortiertes Array: [2, 3, 4, 6, 8, 9]

Zeitliche Komplexität

Bester Fall (O(n log n)): Der beste Fall tritt auf, wenn der Pivot das Array jedes Mal in zwei nahezu gleiche Teile aufteilt.

Durchschnittsfall (O(n log n)): Im Durchschnittsfall teilt der Pivot das Array in zwei ungleiche Teile, aber die Rekursionstiefe und die Anzahl der Vergleiche sind immer noch proportional zu n log n.

Schlimmster Fall (O(n²)): Der schlimmste Fall tritt auf, wenn der Pivot das Array immer in sehr ungleiche Teile aufteilt (z. B. hat ein Teil nur ein Element und der andere n-1 Elemente). Dies kann beispielsweise passieren, wenn ein Array in umgekehrter Reihenfolge sortiert wird und der Pivot schlecht gewählt wird.

Raumkomplexität (O(log n)): Die schnelle Sortierung wird normalerweise direkt implementiert und erfordert keine zusätzlichen Arrays.

Das obige ist der detaillierte Inhalt vonDen Schnellsortierungsalgorithmus verstehen (mit Beispielen in Java). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!