Mergesort

Merge Sort (englisch: Merge sort, oder mergesort) ist ein effizienter Sortieralgorithmus, der auf der Merge-Operation basiert.

Merge Sort ist eine sehr typische Anwendung des Divide-and-Conquer-Ansatzes (Teile und Herrsche). Er führt bereits geordnete Teilfolgen zusammen, um eine vollständig geordnete Sequenz zu erhalten; das heißt, zuerst jede einzelne Folge ordnen, dann die Abschnitte zwischen den Teilfolgen ordnen. Das Zusammenführen zweier geordneter Listen zu einer geordneten Liste wird als Zwei-Wege-Merge bezeichnet.

Stellen Sie sich vor, Sie müssen ein völlig durchmischtes Kartendeck sortieren. Eine Möglichkeit ist: Zuerst das Deck in zwei kleinere Stapel aufteilen, jeden Stapel separat sortieren und schließlich diese beiden geordneten Stapel zu einem vollständig geordneten Deck zusammenführen.Merge SortEs ist genau der klassische Sortieralgorithmus, der auf diesemDivide-and-Conquer-Gedanken basiert.

Seine Kernoperationen lassen sich in zwei Schritten zusammenfassen:

  • Teilen: Eine ungeordnete Liste rekursiv immer wieder von der Mitte aus teilen, sie in viele kleine Unterlisten zerlegen, bis jede Unterliste nur ein Element enthält (eine Liste mit einem Element ist natürlich geordnet).
  • Erobern: Diese geordneten Teillisten rekursiv paarweise zusammenführen, während des Zusammenführens sortieren und schließlich zu einer vollständigen geordneten Liste zusammenführen.

Anwendbarkeit

Mergesort eignet sich für Szenarien mit großen Datenmengen und bei denen Stabilität erforderlich ist.

Mergesort ist ein stabiler Sortieralgorithmus (d. h. die relative Reihenfolge gleicher Elemente bleibt nach dem Sortieren unverändert). Seine Zeitkomplexität ist in allen Fällen O(n log n), was ihn bei der Verarbeitung großer Datenmengen sehr effizient macht, aber seine Speicherkomplexität ist O(n), weil der Zusammenführungsprozess zusätzliche Arrays benötigt, um Daten vorübergehend zu speichern.

Das folgende Flussdiagramm zeigt deutlich den gesamten Prozess des Teile-und-Herrsche-Prinzips beim Mergesort:

Prozessdiagramm

Mergesort ist ein Beispiel für einen rekursiven Algorithmus. Die grundlegende Operation in diesem Algorithmus ist das Zusammenführen zweier sortierter Arrays: Sie erhält zwei Eingabearrays A und B, ein Ausgabearray C und drei Zähler i, j, k, die anfänglich an den Anfängen ihrer jeweiligen Arrays positioniert sind.

Der kleinere von A[i] und B[j] wird an die nächste Position in C kopiert, und der entsprechende Zähler rückt einen Schritt vor.

Wenn eines der beiden Eingabearrays erschöpft ist, wird der verbleibende Teil des anderen Arrays nach C kopiert.

Top-down-Mergesort, rekursives Gruppierungsdiagramm:

Führen Sie Mergesort für die Daten in der dritten Zeile durch, gruppiert in Paaren.

Führen Sie Mergesort für die Daten in der zweiten Zeile durch, in Vierergruppen gruppiert.

Gesamter Mergesort

Java-Beispielcode

Quellcode-Paket-Download:Herunterladen

Code der Datei MergeSort.java:

public class MergeSort {

    // Die beiden Teile arr[l...mid] und arr[mid+1...r] zusammenführen
    private static void merge(Comparable[] arr, int l, int mid, int r) {

        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        // Initialisieren: i zeigt auf den Startindex l der linken Hälfte; j zeigt auf den Startindex mid+1 der rechten Hälfte
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {

            if (i > mid) {  // Wenn alle Elemente in der linken Hälfte verarbeitet wurden
                arr[k] = aux[j - l];
                j++;
            } else if (j > r) {   // Wenn alle Elemente in der rechten Hälfte verarbeitet wurden
                arr[k] = aux[i - l];
                i++;
            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // Das Element, auf das in der linken Hälfte gezeigt wird < das Element, auf das in der rechten Hälfte gezeigt wird
                arr[k] = aux[i - l];
                i++;
            } else {  // Das Element, auf das in der linken Hälfte gezeigt wird >= das Element, auf das in der rechten Hälfte gezeigt wird
                arr[k] = aux[j - l];
                j++;
            }
        }
    }

    // Rekursiv Mergesort verwenden, um den Bereich arr[l...r] zu sortieren
    private static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        // Im Fall arr[mid] <= arr[mid+1] den Merge überspringen
        // Dies ist sehr effektiv für fast sortierte Arrays, aber für allgemeine Fälle gibt es einen gewissen Performanceverlust
        if (arr[mid].compareTo(arr[mid + 1]) > 0)
            merge(arr, l, mid, r);
    }

    public static void sort(Comparable[] arr) {

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

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

        int N = 1000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        // Array ausgeben
        SortTestHelper.printArray(arr);
    }
}

Prinzipien des Algorithmus und detaillierte Schritte

Die Implementierung von Mergesort stützt sich hauptsächlich auf zwei Kernfunktionen:merge_sort(verantwortlich für das "Teilen") undmerge(verantwortlich für "Governance").

1. Zerlegungsfunktionmerge_sort

Diese Funktion arbeitet rekursiv:

Basisfall: Wenn die aktuelle Array-Länge kleiner oder gleich 1 ist, ist sie bereits sortiert, direkt zurückgeben.

Rekursiver Fall：

  • Finde die mittlere Position des Arraysmid。
  • Für die linke Hälftearr[:mid]Rekursiver Aufrufmerge_sort。
  • Für die rechte Hälftearr[mid:]Rekursiver Aufrufmerge_sort。
  • Schließlich aufrufenmergeDie Funktion führt die bereits sortierten linken und rechten Teile zusammen.

2. Merge-Funktionmerge

Dies ist der Kern des Algorithmus; er ist dafür verantwortlich, zweibereits sortiertekleine Arrays zu einem großen sortierten Array zusammenzuführen. Der Vorgang ähnelt dem Durchblättern von zwei bereits alphabetisch sortierten Telefonbüchern und sie zu einem zusammenzuführen.

  1. Erstelle ein temporäres Arraytemp, und drei Zeiger:i(zeigt auf das aktuelle Element des linken Arrays),j(zeigt auf das aktuelle Element des rechten Arrays),k(zeigt auf die Füllposition des temporären Arrays).
  2. Vergleichenleft[i]undright[j], danndas kleinerelege dieses Element intemp[k], dann den entsprechenden Zeiger undkEinen Schritt vorwärts bewegen.
  3. Schritt 2 wiederholen, bis alle Elemente eines der Arrays in das temporäre Array eingefügt wurden.
  4. Alle verbleibenden Elemente des anderen Arrays (die naturgemäß größer als die bereits platzierten Elemente und bereits geordnet sind) direkt der Reihe nach an das Ende des temporären Arrays anhängen.
  5. das temporäre ArraytempDie geordnete Sequenz in ... wird zurück in die entsprechenden Positionen des ursprünglichen Arrays kopiert.

Code-Implementierung und zeilenweise Analyse

Lass uns Merge Sort in Python implementieren. Wir stellen eine vollständige, ausführlich kommentierte Version bereit.

Testdaten

Zuerst bereiten wir eine ungeordnete Liste als Testdaten vor:

Beispiel

# Testdaten: eine ungeordnete Liste von Ganzzahlen
test_array = [38, 27, 43, 3, 9, 82, 10]
print("Ursprüngliches Array:", test_array)

Vollständige Implementierung

Beispiel

def merge_sort(arr):
    """
Die Hauptfunktion für Merge Sort.
Parameter:
arr (list): Die zu sortierende Liste.
Rückgabe:
list: die neue sortierte Liste (der Klarheit halber gibt diese Implementierung eine neue Liste zurück).
    """
    # Basisfall: Wenn die Arraylänge 0 oder 1 ist, ist es bereits sortiert
    if len(arr) <= 1:
        return arr

    # 1. Teilen: Finde den Mittelpunkt und teile das Array in zwei Hälften
    mid = len(arr) // 2
    left_half = arr[:mid]  # Linke Hälfte
    right_half = arr[mid:] # Rechte Hälfte

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

    # 2. Herrschen: die beiden sortierten Teilarrays zusammenführen
    return merge(left_sorted, right_sorted)


def merge(left, right):
    """
Zwei sortierte Listen zusammenführen.
Parameter:
left (list): Die erste sortierte Liste.
right (list): Die zweite sortierte Liste.
Rückgabe:
list: Die zusammengeführte sortierte Liste.
    """
    sorted_list = []  # Temporäre Liste zum Speichern des Merge-Ergebnisses
    i = j = 0         # i und j sind Zeiger, die jeweils left bzw. right durchlaufen

    # 3. Vergleichen und zusammenführen: solange beide Listen noch Elemente haben
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:  # Hinweis: <= verwenden, um die Sortierstabilität beizubehalten
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    # 4. Verbleibende Elemente behandeln: Alle verbleibenden Elemente aus der linken oder rechten Liste an das Ergebnis anhängen
    # Da left und right bereits sortiert sind, müssen die verbleibenden Elemente alle größer als die bereits zusammengeführten Elemente sein
    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])

    return sorted_list


# Algorithmus mit Testdaten ausführen
sorted_array = merge_sort(test_array.copy())  # copy verwenden, um das ursprüngliche Array nicht zu verändern
print("Nach dem Merge Sort:", sorted_array)

Codeausführung und Ausgabe

Wenn Sie den obigen Code ausführen, sehen Sie die folgende Ausgabe:

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

Analyse der Algorithmuskomplexität

Die Effizienz eines Algorithmus zu verstehen, ist entscheidend. Wir fassen die Leistung von Merge Sort in der folgenden Tabelle zusammen:

Metrik Komplexität Beschreibung
Zeitkomplexität O(n log n) Dies ist der bedeutendste Vorteil von Merge Sort.log nEr ergibt sich aus der Anzahl der Rekursionsebenen (Aufteilen des Arrays in zwei Hälften),nSie resultiert daraus, dass jede Ebene der Zusammenführungsoperationen alle Elemente durchlaufen muss. Unabhängig vom Ausgangszustand der Daten (bester, schlechtester, durchschnittlicher Fall) ist die Zeitkomplexität O(n log n).
Speicherkomplexität O(n) Der Zusammenführungsprozess benötigt zusätzlichen Speicherplatz in der Größe des ursprünglichen Arrays, um temporäre Arrays zu speichern. Dies ist der Hauptnachteil von Merge Sort.
Stabilität Stabil InmergeIn der Funktion, wennleft[i] == right[j]Wenn dies geschieht, nehmen wir bevorzugtleft[i](mithilfe eines<=Vergleichs), was sicherstellt, dass die ursprüngliche relative Reihenfolge gleicher Elemente unverändert bleibt.
Ob es sich um In-Place-Sortierung handelt nein Es benötigt zusätzlichen Speicherplatz.

Weitere Code-Demonstrationen

Weitere Erweiterungen