Zwei-Wege-Quicksort

Der Zwei-Wege-Quicksort-Algorithmus ist eine verbesserte Version des randomisierten Quicksort. Der Partitionierungsprozess verwendet zwei Indexwerte (i, j), um das Array zu durchlaufen, wobei<vElemente links von der durch Index i angegebenen Position platziert werden, und platziert>vElemente rechts von der durch Index j angegebenen Position,vStellt den Kalibrierungswert dar.

Anwendbarkeit

Die Zeit- und Raumkomplexität ist dieselbe wie beim randomisierten Quicksort. Für Arrays mit vielen doppelten Elementen ist die Verwendung des randomisierten Quicksort aus dem vorherigen Abschnitt sehr ineffizient, weil die Längen der Teilarrays nach der Partitionierung für Daten, die größer oder kleiner als das Pivot-Element sind, extrem unausgewogen ausfallen, und es kann sogar zu einem Algorithmus mitO(n*2)Zeitkomplexität. Für diese Situation kann der Zwei-Wege-Quicksort-Algorithmus verwendet werden.

Prozessdiagramm

Verwenden Sie zwei Indexwerte (i, j), um unsere Sequenz zu durchlaufen, wobei<=vElemente links von der durch Index i angegebenen Position platziert werden und>=vElemente rechts von der durch Index j angegebenen Position platziert werden, wodurch die linken und rechten Teilarrays ausgeglichen werden.

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

Code der Datei QuickSort2Ways.java:

package example;

/**
* Zwei-Wege-Quicksort
 */

public class QuickSort2Ways {

    // Kerncode --- Start
    private static int partition(Comparable[] arr, int l, int r){
        // Zufällig einen Wert als Pivot im Bereich arr[l...r] auswählen
        swap( arr, l , (int)(Math.random()*(r-l+1))+l );
        Comparable v = arr[l];
        // arr[l+1...i) <= v; arr(j...r] >= v
        int i = l+1, j = r;
        while( true ){
            while( i <= r && arr[i].compareTo(v) < 0 )
                i ++;
            while( j >= l+1 && arr[j].compareTo(v) > 0 )
                j --;
            if( i > j )
                break;
            swap( arr, i, j );
            i ++;
            j --;
        }
        swap(arr, l, j);
        return j;
    }
    // Kerncode --- Ende

    // Quicksort rekursiv verwenden, um den Bereich arr[l...r] zu sortieren
    private static void sort(Comparable[] arr, int l, int r){
        if (l >= r) {
            return;
        }
        int p = partition(arr, l, r);
        sort(arr, l, p-1 );
        sort(arr, p+1, r);
    }

    public static void sort(Comparable[] arr){

        int n = arr.length;
        sort(arr, 0, n-1);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // QuickSort testen
    public static void main(String[] args) {

        // Der Zwei-Wege-Quick-Sort-Algorithmus ist ebenfalls ein Algorithmus mit O(nlogn)-Komplexität
        // Kann Daten in der Größenordnung von 1 Million problemlos innerhalb von 1 Sekunde verarbeiten

        // Quick Sort ist ebenfalls ein Algorithmus mit O(n log n)-Komplexität
        // Kann Daten in der Größenordnung von 1 Million problemlos innerhalb von 1 Sekunde verarbeiten
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        SortTestHelper.printArray(arr);

    }
}

Ausführliche Erklärung des Algorithmusprinzips

Der Kern des Zwei-Wege-Quicksorts liegt in seinerZwei-Zeiger-PartitionierungsmethodeIm Gegensatz zum Einweg-Quicksort (das nur von einem Ende aus scannt), verwendet es zwei Zeiger, die vom Anfang und Ende des zu sortierenden Teilarrays zur Mitte hin scannen, wodurch sichergestellt wird, dass gleiche Elemente nicht alle auf eine Seite geschoben werden.

Kern: der Zwei-Wege-Partitionierungsprozess

Angenommen, wir möchten das Array sortierenarrmittlerer Index vonleftaufrightTeil.

Pivot-Wert wählen: ausarr[left...right]Wähle zufällig ein Element daraus als Pivot-WertpivotRandomisierung wird verwendet, um den Worst Case bei sortierten Arrays zu vermeiden.

Zeiger initialisieren:

  • i = left + 1Ein Zeiger, der von links nach rechts läuft und nach dem erstengrößer oder gleich pivotElemente.
  • j = rightEin Zeiger, der von rechts nach links läuft und nach dem erstenkleiner oder gleich pivotElemente.

Schleife zum Scannen und Tauschen:

  • whileDie Schleife, wobei die Bedingung lauteti <= j。
  • innerewhileSchleife: letiWeiter nach rechts bewegen, bisarr[i] >= pivot。
  • innerewhileSchleife: letjWeiter nach links gehen, bisarr[j] <= pivot。
  • An diesem Punkt,arr[i]ist ein "großes" Element, das nicht in der linken Hälfte sein sollte,arr[j]ist ein "kleines" Element, das nicht in der rechten Hälfte sein sollte.
  • Wenn an diesem Punkti <= j, dann vertauschearr[i]undarr[j], danni++, j--dann die äußere Schleife fortsetzen.

Pivot-Wert platzieren und den Partitionspunkt zurückgeben:

  • Nach dem Ende der Schleife,iundjbereits gekreuzt (j < i). An diesem Punktarr[left](d. h. der Pivot) muss an der richtigen Position platziert werden.
  • wirdarr[left]undarr[j]swap. DennjDie Position, an der er schließlich stoppt, und das Element, auf das er zeigt, istdas letzte Element kleiner oder gleich dem Pivot-WertElemente.
  • returnjals neuen Partitionspunkt. An diesem Punkt,arr[left...j-1] <= pivot,arr[j+1...right] >= pivot, undarr[j] == pivot。

rekursiv sortieren

den Partitionspunkt ermittelnpDanach für das linke Teilarrayarr[left...p-1]und das rechte Teilarrayarr[p+1...right]Wiederholen Sie den obigen Prozess rekursiv, bis die Länge des Teilarrays 1 ist.


Code-Implementierung

Lassen Sie uns den Zwei-Wege-Quicksort anhand einer vollständigen Java-Implementierung konkret verstehen.

1. Hauptsortierfunktion

Beispiel

public class TwoWayQuickSort {

    // Öffentliche Sortierschnittstelle
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return; // Randbedingung behandeln: Array ist leer oder hat nur ein Element, keine Sortierung nötig
        }
        quickSort(arr, 0, arr.length - 1); // Aufruf der rekursiven Quick-Sort-Funktion
    }

    // Rekursive Quick-Sort-Funktion
    private static void quickSort(int[] arr, int left, int right) {
        // Abbruchbedingung der Rekursion: Wenn left >= right, ist das Teilarray bereits sortiert oder leer
        if (left >= right) {
            return;
        }
       
        // Schlüsselschritt: Zwei-Wege-Partitionierung durchführen und den Partitionsindex zurückgeben
        int p = partition(arr, left, right);
       
        // Rekursiv die linke Hälfte sortieren (left, p-1)
        quickSort(arr, left, p - 1);
        // Rekursiv die rechte Hälfte sortieren (p+1, right)
        quickSort(arr, p + 1, right);
    }
}

2. Kern: Zwei-Wege-Partitionierungsfunktion

Dies ist der Kern des Algorithmus. Bitte verstehen Sie ihn sorgfältig zusammen mit dem obenstehenden Flussdiagramm und den Kommentaren.

Beispiel

    // Zwei-Wege-Partitionierungsfunktion
    private static int partition(int[] arr, int left, int right) {
        // 1. Zufällig ein Pivot-Element auswählen und an die linke Position tauschen, um den Worst Case bei sortierten Arrays zu vermeiden
        int randomIndex = left + (int)(Math.random() * (right - left + 1));
        swap(arr, left, randomIndex);
        int pivot = arr[left]; // Pivot-Wert
       
        // 2. Initialisiere die beiden Zeiger
        // i: von links nach rechts scannen, um Elemente >= pivot zu finden
        // j: von rechts nach links scannen, um Elemente <= pivot zu finden
        int i = left + 1;
        int j = right;
       
        // 3. Hauptschleife: solange i und j sich nicht gekreuzt haben
        while (i <= j) {
            // 3.1 Linken Zeiger i verschieben: erstes Element >= pivot finden
            // Hinweis: Grenze i <= right, um Array-Grenzüberschreitung zu verhindern
            while (i <= right && arr[i] < pivot) {
                i++;
            }
            // 3.2 Rechten Zeiger j verschieben: erstes Element <= pivot finden
            // Hinweis: Grenze j >= left+1, weil die Position left das Pivot selbst ist
            while (j >= left + 1 && arr[j] > pivot) {
                j--;
            }
           
            // 3.3 Zeigerstatus prüfen
            // Wenn i > j, ist das Scannen abgeschlossen, die linken und rechten Partitionen sind bereit, kein Tausch erforderlich
            if (i > j) {
                break;
            }
           
            // 3.4 arr[i] und arr[j] vertauschen
            // Jetzt gilt arr[i] >= pivot, arr[j] <= pivot; vertausche sie, damit die Elemente auf beiden Seiten an der richtigen Stelle sind
            swap(arr, i, j);
            // Nach dem Vertauschen die Zeiger verschieben, um mit dem Scannen fortzufahren
            i++;
            j--;
        }
       
        // 4. Das Pivot an seiner endgültigen korrekten Position j platzieren
        // Nach dem Ende der Schleife zeigt j auf das letzte Element <= pivot
        swap(arr, left, j);
       
        // 5. Den Index j des Partitionspunkts zurückgeben
        return j;
    }
   
    // Hilfsfunktion: die Positionen zweier Elemente in einem Array vertauschen
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

3. Testen und Verifizierung

Lassen Sie uns unsere Implementierung mit einem Array testen, das doppelte Elemente enthält.

Beispiel

public class Main {
    public static void main(String[] args) {
        // Testfall 1: Array mit vielen doppelten Elementen
        int[] arr1 = {4, 2, 2, 8, 3, 3, 1, 5, 3, 2};
        System.out.println("Vor dem Sortieren: " + Arrays.toString(arr1));
        TwoWayQuickSort.sort(arr1);
        System.out.println("Nach dem Sortieren: " + Arrays.toString(arr1));
       
        // Testfall 2: großes zufällig generiertes Array
        int[] arr2 = new int[20];
        Random rand = new Random();
        for (int i = 0; i < arr2.length; i++) {
            arr2[i] = rand.nextInt(50); // Zufallszahlen von 0-49 generieren, Duplikate wahrscheinlich
        }
        System.out.println("\n"Vor dem Sortieren des Zufallsarrays: " + Arrays.toString(arr2));
        TwoWayQuickSort.sort(arr2);
        System.out.println("Nach dem Sortieren des Zufallsarrays: " + Arrays.toString(arr2));
       
        // Überprüfen, ob das Sortierergebnis korrekt ist
        for (int i = 1; i < arr2.length; i++) {
            if (arr2[i] < arr2[i-1]) {
                System.out.println("Sortierfehler!");
                return;
            }
        }
        System.out.println("Überprüfung des Sortierergebnisses bestanden!");
    }
}

Beispiel für die Ausgabe von Testdaten:

排序前: [4, 2, 2, 8, 3, 3, 1, 5, 3, 2]
排序后: [1, 2, 2, 2, 3, 3, 3, 4, 5, 8]

随机数组排序前: [17, 33, 12, 48, 8, 2, 41, ...]
随机数组排序后: [2, 8, 12, 17, 33, 33, 41, 48, ...]
排序结果验证通过!

Algorithmusanalyse und -vergleich

Zeitkomplexität

  • Durchschnittsfall:$O(n \log n)$. Zwei-Wege-Quicksort hält den Rekursionsbaum relativ ausgeglichen, indem doppelte Elemente gleichmäßig verteilt werden.
  • Schlechtester Fall:$O(n^2)$. Obwohl eine randomisierte Pivot-Auswahl die Wahrscheinlichkeit stark verringert, kann der schlechteste Fall immer noch auftreten, wenn jede Partition extrem unausgeglichen ist (zum Beispiel, wenn das Pivot-Element immer der aktuelle minimale oder maximale Wert ist).
  • Bester Fall:$O(n \log n)$. Jede Partition teilt das Array gleichmäßig auf.

Speicherkomplexität

  • Sie wird hauptsächlich durch den Speicherplatz des rekursiven Aufrufstapels bestimmt.
  • Die durchschnittliche Tiefe ist $O(\log n)$, und die Tiefe im schlechtesten Fall ist $O(n)$.
  • Daher,Die durchschnittliche Speicherkomplexität ist $O(\log n)$, und der schlechteste Fall ist $O(n)$.。

Stabilität

Quicksort (einschließlich Zwei-Wege-Quicksort) ist kein stabiles Sortierverfahren, weil beim Partitionieren das Vertauschen nicht benachbarter Elemente die ursprüngliche relative Reihenfolge gleicher Elemente stören kann.

Vergleich von Ein-Wege-, Zwei-Wege- und Drei-Wege-Quicksort

Funktionen Ein-Wege-Quicksort (Lomuto) Zwei-Wege-Quicksort Drei-Wege-Quicksort
Partitionierungsmethode Ein Zeiger durchläuft von links nach rechts Zwei Zeiger durchlaufen von beiden Enden zur Mitte Drei Zeiger, die das Array aufteilen in<pivot, =pivot, >pivotDrei Teile
Umgang mit doppelten Elementen Schlecht, kann zu unausgeglichener Partitionierung führen Gut, kann doppelte Elemente gleichmäßig verteilen Optimal, kann alle Elemente gleich dem Pivot auf einmal verarbeiten
Code-Komplexität Einfach Mittel Etwas komplex
Anwendbare Szenarien Unterricht, keine/wenige doppelte Elemente Allgemein einsetzbar, besonders geeignet für Szenarien, in denen doppelte Elemente vorkommen können Szenarien mit einer großen Anzahl doppelter Elemente

Mehr Codebeispiele

Weitere Erweiterungen