Sortieralgorithmen

Ein Sortieralgorithmus ist ein Algorithmus, der eine Datenfolge nach einer bestimmten Sortiermethode anordnet; die sortierten Daten können dann in einem geordneten Array abgelegt werden.

SortierenEs bezeichnet den Prozess, eine Menge von Daten (wie ein Array oder eine Liste) in einer bestimmten Reihenfolge (aufsteigend oder absteigend) neu anzuordnen.

Die Grundlage der Sortierung ist normalerweise eine bestimmte Eigenschaft der DatenelementeSchlüsselwie die Größe von Zahlen, die lexikografische Reihenfolge von Zeichenketten usw.

Sortieren ist eines der grundlegendsten und zentralsten algorithmischen Probleme der Informatik. Ob es um die Organisation von Kontakten, die Analyse von Prüfungsergebnissen oder die Optimierung von Datenbankabfragen geht – Sortieralgorithmen sind überall.

Das Verständnis verschiedener Sortieralgorithmen hilft uns nicht nur, praktische Probleme zu lösen, sondern ist auch ein ausgezeichneter Weg, um Algorithmendesign- und Analyseideen tiefgehend zu verstehen.

Klassifizierung von Sortieralgorithmen

Sortieralgorithmen können anhand mehrerer Dimensionen klassifiziert werden, wobei die gebräuchlichste Klassifizierung auf ihrerZeitkomplexitätundSpeicherkomplexität basiert。

Klassifizierungsdimension Kategorie Beschreibung Typische Algorithmen
Zeitkomplexität O(n²)-Niveau einfach und intuitiv, aber wenig effizient, geeignet für kleine Datenmengen. Bubblesort, Selectionsort, Insertionsort
O(n log n)-Niveau relativ hohe Effizienz und ist die erste Wahl für die Verarbeitung großer Datenmengen. Quicksort, Mergesort, Heapsort
Speicherkomplexität In-place-Sortierung Verwendet während des Sortiervorgangs nur eine konstante Menge an zusätzlichem Speicherplatz. Bubblesort, Selectionsort, Insertionsort, Shellsort, Heapsort, Quicksort.
Out-of-place-Sortierung Während des Sortiervorgangs ist zusätzlicher Speicher proportional zur Datengröße erforderlich. Mergesort, Countingsort, Bucketsort, Radixsort.
Stabilität Stabile Sortierung Die relative Reihenfolge gleicher Elemente bleibt nach dem Sortieren unverändert. Bubblesort, Insertionsort, Mergesort, Countingsort, Bucketsort, Radixsort.
Instabile Sortierung Die relative Reihenfolge gleicher Elemente kann sich nach dem Sortieren ändern. Selectionsort, Shellsort, Heapsort, Quicksort

Erläuterung der Schlüsselkonzepte:

  • ZeitkomplexitätMisst den Trend der Ausführungszeit eines Algorithmus bei zunehmender Datengröße.
  • SpeicherkomplexitätMisst die Menge an zusätzlichem Speicherplatz, die während der Ausführung eines Algorithmus benötigt wird.
  • StabilitätBei Elementen mit gleichen Werten, ob ihre relative Reihenfolge nach dem Sortieren unverändert bleibt. Dies ist bei der Sortierung nach mehreren Schlüsseln sehr wichtig.

Das folgende Flussdiagramm zeigt, wie man je nach unterschiedlichen Anforderungsszenarien eine vorläufige Auswahl unter mehreren klassischen Algorithmen trifft:

Grundlegende Sortieralgorithmen auf O(n²)-Niveau

Diese Algorithmen sind vom Konzept her einfach und bilden den Ausgangspunkt zum Verständnis der Sortierlogik.

Blasensortierung

KernideeWiederholt die zu sortierende Sequenz „durchlaufen“, dabei jeweils zwei benachbarte Elemente vergleichen und sie vertauschen, wenn sie in der falschen Reihenfolge sind. Bei jedem Durchlauf steigt das größte (oder kleinste) Element im aktuell unsortierten Teil an seine richtige Position auf.

Algorithmusschritte：

  1. Benachbarte Elemente vergleichen. Wenn das erste größer als das zweite ist (für aufsteigende Reihenfolge), tausche sie.
  2. Dasselbe für jedes Paar benachbarter Elemente tun, vom ersten Paar am Anfang bis zum letzten Paar am Ende. Nach diesem Schritt ist das letzte Element die größte Zahl.
  3. Die obigen Schritte für alle Elemente außer dem letzten wiederholen (weil jede Runde ein endgültiges Element festlegt).
  4. Die obigen Schritte weiterhin für immer weniger Elemente wiederholen, bis es kein Paar von Zahlen mehr zu vergleichen gibt.

Code-Implementierung：

Beispiel

def bubble_sort(arr):
    """
Bubble Sort (aufsteigend)
:param arr: Die zu sortierende Liste
    """
    n = len(arr)
    # Die äußere Schleife steuert die Anzahl der benötigten Durchläufe (n-1 Durchläufe)
    for i in range(n - 1):
        # Die innere Schleife führt den Vergleich und das Vertauschen benachbarter Elemente durch
        # Nach jedem Durchlauf sind die letzten i+1 Elemente bereits sortiert, daher ist der Vergleichsbereich 0 bis n-1-i
        for j in range(0, n - 1 - i):
            if arr[j] > arr[j + 1]:  # Wenn das vorherige Element größer als das folgende Element ist
                # Tausche die Positionen der beiden Elemente
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Testdaten
test_data = [64, 34, 25, 12, 22, 11, 90]
print("Ursprüngliches Array:", test_data)
sorted_data = bubble_sort(test_data.copy()) # Verwende eine Kopie, um die ursprünglichen Daten nicht zu verändern
print("Nach dem Bubble-Sort:", sorted_data)

Ausgabe:

原始数组: [64, 34, 25, 12, 22, 11, 90]
冒泡排序后: [11, 12, 22, 25, 34, 64, 90]

Leistungsanalyse：

  • ZeitkomplexitätBester Fall O(n) (erreichbar mit Optimierung, wenn bereits sortiert), schlechtester und durchschnittlicher Fall O(n²).
  • Speicherkomplexität: O(1), es ist eine In-Place-Sortierung.
  • Stabilität: stabil.

Auswahlsortierung

GrundideeFinde das kleinste (oder größte) Element in der unsortierten Sequenz, platziere es am Anfang der sortierten Sequenz, suche dann weiter das kleinste (größte) Element aus den verbleibenden unsortierten Elementen und platziere es am Ende der sortierten Sequenz. Fahre auf diese Weise fort, bis alle Elemente sortiert sind.

Algorithmusschritte：

  1. Anfangszustand: Die gesamte Sequenz ist der unsortierte Bereich.
  2. In der i-ten Runde (i beginnt bei 0) der Sortierung ist der aktuelle unsortierte Bereicharr[i...n-1]Wähle aus diesem Bereich den Datensatz mit dem kleinsten Schlüsselarr[min_index]。
  3. wirdarr[min_index]Mit dem ersten Datensatz des unsortierten Bereichsarr[i]Tauschen. Auf diese Weise,arr[0...i]Dann wird der sortierte Bereich gebildet.
  4. Nach n-1 Runden ist das Array sortiert.

Code-Implementierung：

Beispiel

def selection_sort(arr):
    """
Selection Sort (aufsteigend)
:param arr: Die zu sortierende Liste
    """
    n = len(arr)
    for i in range(n):
        # Angenommen, das Element am aktuellen Index i ist das kleinste
        min_index = i
        # Finde ein kleineres Element im Bereich von i+1 bis n-1
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j # Aktualisiere den Index des kleinsten Elements
        # Tausche das gefundene kleinste Element mit dem Element an Position i
        arr[i], arr[min_index] = arr[min_index], arr[i]
    return arr

# Test
test_data = [64, 25, 12, 22, 11]
print("Ursprüngliches Array:", test_data)
print("Nach Selection Sort:", selection_sort(test_data.copy()))

Ausgabe:

原始数组: [64, 25, 12, 22, 11]
选择排序后: [11, 12, 22, 25, 64]

Leistungsanalyse：

  • ZeitkomplexitätImmer O(n²), da vollständige Vergleiche erforderlich sind, unabhängig davon, ob die Daten sortiert sind.
  • Speicherkomplexität: O(1), In-Place-Sortierung.
  • Stabilität：instabil. Zum Beispiel die Sequenz[5, 8, 5, 2, 9], in der ersten Runde wird das erste [Element]5und2getauscht, wodurch die beiden ihre5ursprüngliche Reihenfolge verlieren.

Insertionssortierung

KernideeDurch den Aufbau einer geordneten Sequenz werden für unsortierte Daten die sortierte Sequenz rückwärts durchsucht, die passende Position gefunden und dort eingefügt. Das ist wie das Anordnen von Spielkarten.

Algorithmusschritte：

  1. Behandle das erste Element als die sortierte Sequenz.
  2. Nimm das nächste Element und durchsuche die sortierte Elementfolge rückwärts.
  3. Wenn das sortierte Element größer als das neue Element ist, verschiebe das sortierte Element an die nächste Position.
  4. Wiederhole Schritt 3, bis du eine Position findest, an der das sortierte Element kleiner oder gleich dem neuen Element ist.
  5. Nach dem Einfügen des neuen Elements an dieser Position.
  6. Wiederhole die Schritte 2-5, bis alle Elemente verarbeitet sind.

Code-Implementierung：

Beispiel

def insertion_sort(arr):
    """
Insertionssortierung (aufsteigend)
:param arr: Die zu sortierende Liste
    """
    n = len(arr)
    # Beginne beim zweiten Element (Index 1), weil das erste Element standardmäßig bereits sortiert ist
    for i in range(1, n):
        key = arr[i]  # Das aktuelle Element, das eingefügt werden soll
        j = i - 1     # Index des letzten Elements in der sortierten Sequenz
        # Durchsuche die sortierte Sequenz von hinten nach vorne, um die Einfügeposition von key zu finden
        # Verschiebe gleichzeitig Elemente, die größer als key sind, um eine Position nach hinten
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # Schlüssel an der gefundenen korrekten Position einfügen
        arr[j + 1] = key
    return arr

# Test
test_data = [12, 11, 13, 5, 6]
print("Ursprüngliches Array:", test_data)
print("Nach Insertionsort:", insertion_sort(test_data.copy()))

Ausgabe:

原始数组: [12, 11, 13, 5, 6]
插入排序后: [5, 6, 11, 12, 13]

Leistungsanalyse：

  • ZeitkomplexitätBester Fall O(n) (bereits sortiert), schlechtester und durchschnittlicher Fall O(n²).
  • Speicherkomplexität: O(1), In-Place-Sortierung.
  • Stabilität: stabil.
  • Eigenschaften: Für kleine Datenmengen oder nahezu sortierte Daten ist Insertionsort sehr effizient. Er ist der Algorithmus, zu dem fortgeschrittene Sortieralgorithmen (wie Timsort) bei kleinen Datenmengen wechseln.

Effiziente Sortieralgorithmen auf O(n log n)-Niveau

Wenn die Datenmenge wächst, werden O(n²)-Algorithmen sehr langsam. Die folgenden effizienteren Algorithmen sind das Rückgrat der Ingenieurspraxis.

Quicksort

Kernidee：Teile und herrscheWähle ein Pivot-Element. Durch einen Sortierdurchlauf werden die zu sortierenden Datensätze in zwei unabhängige Teile partitioniert, wobei die Schlüssel des einen Teils alle kleiner sind als die Schlüssel des anderen Teils; dann werden diese beiden Teile separat sortiert, um die gesamte Sequenz zu ordnen.

Algorithmusschritte：

  1. Pivot auswählenWähle ein Element aus der Sequenz und nenne es das "Pivot".
  2. PartitionsoperationOrdne die Sequenz so um, dass alle Elemente, die kleiner als das Pivot sind, davor platziert werden und alle Elemente, die größer als das Pivot sind, dahinter platziert werden (gleiche Zahlen können auf beiden Seiten stehen). Nachdem diese Partition beendet ist, befindet sich das Pivot an seiner endgültigen Position in der Mitte der Sequenz. Dies wird als Partitionsoperation bezeichnet.
  3. rekursiv sortierenSortiere rekursiv die Teilsequenz mit Elementen, die kleiner als das Pivot sind, und die Teilsequenz mit Elementen, die größer als das Pivot sind.

Code-Implementierung：

Beispiel

def quick_sort(arr):
    """
Quick Sort (Aufsteigend) - Hauptfunktion
    """
    def _quick_sort(arr, low, high):
        if low < high:
            # pi ist der Partitionsindex, arr[pi] ist jetzt an der richtigen Position
            pi = partition(arr, low, high)
            # Teilarrays vor und nach der Partition rekursiv sortieren
            _quick_sort(arr, low, pi - 1)
            _quick_sort(arr, pi + 1, high)

    def partition(arr, low, high):
        """
Partitionsfunktion, das letzte Element als Pivot auswählen
:return: der endgültige korrekte Positionsindex des Pivot-Elements
        """
        pivot = arr[high]  # Wähle einen Pivot
        i = low - 1        # Verweist auf das Ende des Teilarrays der Elemente, die kleiner als das Pivot-Element sind
        for j in range(low, high):
            # Wenn das aktuelle Element kleiner oder gleich dem Pivot-Element ist
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i] # Tauschen
        # Platziere das Pivot-Element an der richtigen Position (i+1)
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        return i + 1

    _quick_sort(arr, 0, len(arr) - 1)
    return arr

# Test
test_data = [10, 80, 30, 90, 40, 50, 70]
print("Ursprüngliches Array:", test_data)
print("Nach Quick Sort:", quick_sort(test_data.copy()))

Ausgabe:

原始数组: [10, 80, 30, 90, 40, 50, 70]
快速排序后: [10, 30, 40, 50, 70, 80, 90]

Leistungsanalyse：

  • ZeitkomplexitätDurchschnittsfall O(n log n), Worst Case O(n²) (wenn das Array bereits sortiert oder umgekehrt sortiert ist und das Pivot-Element schlecht gewählt wird). Der Worst Case kann weitgehend vermieden werden, indem das Pivot-Element zufällig ausgewählt wird oder die "Median-of-Three"-Methode verwendet wird.
  • Speicherkomplexität: Durchschnittlich O(log n) (rekursiver Aufrufstapel), Worst-Case O(n).
  • Stabilität：instabil。

Mergesort

Kernidee：Teile und herrscheEine typische Anwendung. Bereits geordnete Teilfolgen zusammenführen, um eine vollständig geordnete Sequenz zu erhalten. Das heißt, zuerst jede Teilfolge ordnen und dann die Teilfolgensegmente relativ zueinander ordnen.

Algorithmusschritte：

  1. TeilenTeile das aktuelle Intervall in zwei Teile, d. h., finde den Teilungspunktmid = (low + high)/2。
  2. ErobernDie beiden Teilintervalle rekursiv [sortieren]arr[low...mid]undarr[mid+1...high]Führe Merge Sort aus. Die Abbruchbedingung für die Rekursion ist, dass die Länge des Teilintervalls 1 beträgt (ein Element gilt als natürlich geordnet).
  3. ZusammenführenZwei sortierte Teilintervalle zu einem geordneten Intervall zusammenführen.

Code-Implementierung：

Beispiel

def merge_sort(arr):
    """
Merge Sort (aufsteigend) - Hauptfunktion
    """
    if len(arr) > 1:
        mid = len(arr) // 2  # Mittelpunkt finden und das Array aufteilen
        left_half = arr[:mid]
        right_half = arr[mid:]

        # Die linken und rechten Hälften rekursiv sortieren
        merge_sort(left_half)
        merge_sort(right_half)

        # Die beiden sortierten Teilarrays zusammenführen
        i = j = k = 0
        # Vergleiche die Elemente der linken und rechten Teilarrays und setze das kleinere in das ursprüngliche Array
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # Prüfe, ob noch Elemente übrig sind (linke Hälfte oder rechte Hälfte)
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

# Test
test_data = [38, 27, 43, 3, 9, 82, 10]
print("Ursprüngliches Array:", test_data)
print("Nach Merge Sort:", merge_sort(test_data.copy()))

Ausgabe:

原始数组: [38, 27, 43, 3, 9, 82, 10]
归并排序后: [3, 9, 10, 27, 38, 43, 82]

Leistungsanalyse：

  • ZeitkomplexitätBest-, Worst- und Average-Fall sind alle O(n log n). Die Leistung ist sehr stabil.
  • SpeicherkomplexitätO(n), erfordert zusätzlichen Speicher, der dem ursprünglichen Array entspricht, für das Zusammenführen.
  • Stabilität: stabil.

Heap-Sortierung

Kernidee: unter Verwendung vonHeapEin für diese Datenstruktur entwickelter Sortieralgorithmus. Ein Heap ist eine nahezu vollständige Binärbaumstruktur, die zudem die Heap-Eigenschaft erfüllt: Der Wert eines Elternknotens ist stets größer oder gleich (Max-Heap) bzw. kleiner oder gleich (Min-Heap) dem Wert eines beliebigen Kindknotens.

Algorithmusschritte：

  1. Max-Heap aufbauenDie zu sortierende Sequenz zu einem Max-Heap umbauen. Zu diesem Zeitpunkt ist der maximale Wert der gesamten Sequenz der Wurzelknoten an der Spitze des Heaps.
  2. Das oberste Heap-Element mit dem letzten Element vertauschenDas oberste Element (das Maximum) mit dem letzten Element vertauschen; das letzte Element ist nun das Maximum.
  3. Heap-Struktur anpassen: für die verbleibendenn-1Die verbleibenden Elemente wieder zu einem Max-Heap aufbauen, was den nächstgrößten Wert ergibt. Diesen mit dem neuen letzten Element (Position n-1) vertauschen.
  4. Wiederholung ausführenSchritte 2 und 3 wiederholen, bis die Heap-Größe 1 beträgt; die Sortierung ist abgeschlossen.

Code-Implementierung：

Beispiel

def heap_sort(arr):
    """
Heap-Sortierung (aufsteigend) - Verwendung eines Max-Heaps
    """
    n = len(arr)

    # Schritt 1: Den Max-Heap aufbauen. Beginne mit dem Anpassen nach oben vom letzten Nicht-Blattknoten
    # Index des letzten Nicht-Blattknotens = n//2 - 1
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # Schritte 2 & 3: Extrahiere das oberste Element (Maximum) nacheinander und passe den Heap an
    for i in range(n - 1, 0, -1):
        # Tausche das aktuelle oberste Element (Maximum) mit dem letzten Element
        arr[i], arr[0] = arr[0], arr[i]
        # Passe die verbleibenden Elemente an, um wieder einen Max-Heap zu bilden, wobei die Heap-Größe auf i gesetzt ist
        heapify(arr, i, 0)
    return arr

def heapify(arr, n, i):
    """
Passe den bei i verwurzelten Teilbaum an, um daraus einen Max-Heap zu machen
:param arr: Heap-Array
:param n: aktuelle Heap-Größe
:param i: Index der aktuellen Wurzel
    """
    largest = i         # Initialisiere den Maximalwert als Wurzel
    left = 2 * i + 1    # Index des linken Kindes
    right = 2 * i + 2   # Index des rechten Kindes

    # Wenn das linke Kind existiert und größer als die Wurzel ist
    if left < n and arr[left] > arr[largest]:
        largest = left
    # Wenn das rechte Kind existiert und größer als das aktuelle Maximum ist
    if right < n and arr[right] > arr[largest]:
        largest = right
    # Wenn das Maximum nicht die Wurzel ist, tausche und passe den defekten Teil-Heap rekursiv an
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

# Test
test_data = [4, 10, 3, 5, 1]
print("Ursprüngliches Array:", test_data)
print("Nach dem Heap-Sort:", heap_sort(test_data.copy()))

Ausgabe:

原始数组: [4, 10, 3, 5, 1]
堆排序后: [1, 3, 4, 5, 10]

Leistungsanalyse：

  • ZeitkomplexitätBest-, Worst- und Average-Case sind alle O(n log n).
  • Speicherkomplexität: O(1), In-Place-Sortierung.
  • Stabilität：instabil。

Zusammenfassung des Leistungsvergleichs der Algorithmen

Um die Eigenschaften der oben genannten Algorithmen intuitiver zu vergleichen, fassen wir sie in der folgenden Tabelle zusammen:

Algorithmen Durchschnittliche Zeitkomplexität Zeitkomplexität im schlechtesten Fall Speicherkomplexität Stabilität Hauptfunktionen
Blasensortierung O(n²) O(n²) O(1) Stabil Einfach, geringe Effizienz, für den Unterricht geeignet.
Auswahlsortierung O(n²) O(n²) O(1) instabil Weniger Vertauschungen, aber eine feste große Anzahl von Vergleichen.
Insertionssortierung O(n²) O(n²) O(1) Stabil Effizient für kleine Datenmengen oder nahezu sortierte Daten.
Quicksort O(n log n) O(n²) O(log n) instabil Beste durchschnittliche Leistung, ist der am weitesten verbreitete Sortieralgorithmus.
Mergesort O(n log n) O(n log n) O(n) Stabil Stabile Leistung, benötigt aber zusätzlichen Speicher. Wird häufig für externes Sortieren verwendet.
Heap-Sortierung O(n log n) O(n log n) O(1) instabil In-Place-Sortierung und O(n log n) selbst im schlechtesten Fall.

Übungsaufgaben

Nach dem theoretischen Lernen ist praktische Übung der beste Weg, das Wissen zu festigen.

Übung 1: Algorithmusauswahl und -implementierung

Welchen Sortieralgorithmus würden Sie in den folgenden Szenarien wählen? Erklären Sie kurz Ihre Gründe.

  1. Sortiere ein Array mit 10 Zahlen.
  2. Sortiere eine verkettete Liste von 1 Million Studierendenobjekten nach Studierenden-ID, wobei Stabilität erforderlich ist.
  3. Sortiere ein großes Array in einem eingebetteten System mit begrenztem Speicher.
  4. Es müssen in Echtzeit die K größten Elemente aus einem Datenstrom ermittelt werden.

Ansatz der Referenzantwort：

  1. Insertion SortGeringe Datenmenge; Insertion Sort ist einfach, vorteilhaft bei nahezu sortierten Daten und hat einen kleinen konstanten Faktor.
  2. Merge SortGroße Datenmenge, stabile Sortierung ist erforderlich, und die Struktur der verketteten Liste ermöglicht es, die Merge-Operation von Merge Sort in O(1)-Speicher abzuschließen (nur durch Ändern von Zeigern).
  3. Heap SortBegrenzter Speicher, In-Place-Sortierung ist erforderlich, und Heap Sort garantiert O(n log n)-Laufzeit auch im schlechtesten Fall.
  4. Einen Min-Heap der Größe K beibehaltenDurchlaufe den Datenstrom und verwende einen Heap, um die aktuellen K größten Elemente beizubehalten. Dies ist keine vollständige Sortierung, sondern nutzt die Eigenschaften eines Heaps aus.

Übung 2: Code-Debugging und Optimierung

Die folgende Bubble-Sort-Implementierung hat einen kleinen Fehler und eine Stelle, die optimiert werden kann; bitte finde und behebe sie.

Beispiel

def bubble_sort_buggy(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

Hinweis：

  • Vergleichsbedingungarr[j] > arr[j]Immer falsch.
  • Die Grenze der inneren Schleife kann optimiert werden, da nach jeder Runde die hinteren Elemente bereits sortiert sind.

Übung 3: Praktische Umsetzung

Versuchen Sie, es selbst von Grund auf zu implementierenQuicksort, und denken Sie:

  • Wenn der BenchmarkpivotWas passiert, wenn beim Sortieren eines bereits sortierten Arrays immer das erste Element als Pivot gewählt wird?
  • Wie Sie es ändernpartitionÄndern Sie die Partitionierungsfunktion so ab, dass sie zu einem "Drei-Wege-Quicksort" wird, der Arrays mit vielen Duplikaten effizienter verarbeiten kann.
Weitere Erweiterungen