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("未排序數(shù)組: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序數(shù)組: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 將最后一個(gè)元素設(shè)置為樞軸
        int pivot = arr[end];
        // 創(chuàng)建指向下一個(gè)較大元素的指針
        int secondPointer = start-1;

        // 將小于樞軸的元素移動(dòng)到樞軸左側(cè)
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交換元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 將樞軸與第二個(gè)指針交換
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分區(qū)索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分區(qū)索引
            int partitionIndex = partition(arr, start, end);
            // 遞歸調(diào)用快速排序
            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(n2)): 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!