Den Merge-Sortier-Algorithmus verstehen (mit Beispielen in Java)

Merge Sort: Eine umfassende Anleitung

Merge Sort ist ein hocheffizienter Sortieralgorithmus, der häufig in verschiedenen Programmiersprachen verwendet wird, entweder unabhängig oder als Teil eines Hybridansatzes. Seine Grundlage liegt im Divide-and-Conquer-Paradigma: Ein Problem wird in kleinere Teilprobleme zerlegt, einzeln gelöst und ihre Lösungen für das Endergebnis kombiniert. Merge Sort teilt die Eingabeliste rekursiv in Hälften, sortiert jede Hälfte und führt dann die sortierten Hälften zusammen, um eine vollständig sortierte Liste zu erstellen.

Den Zusammenführungssortierungsprozess verstehen

Lassen Sie uns den Merge-Sort-Prozess anhand eines Beispielarrays veranschaulichen:

Dieses Bild zeigt die rekursive Aufteilung des Arrays.

Dieses Bild zeigt die Zusammenführung sortierter Subarrays.

Zusammenführungssortierung implementieren

Unten ist eine Java-Implementierung des Merge-Sort-Algorithmus:

import java.util.Arrays;

public class MergeSortTest {
    public static void main(String[] args){
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length-1);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    static void mergeSort(int arr[], int start, int end){
        if (start < end){
            int mid = (start + end) / 2;
            mergeSort(arr, start, mid);
            mergeSort(arr, mid + 1, end);
            merge(arr, start, mid, end);
        }
    }

    static void merge(int arr[], int start, int mid, int end){
        int[] left = new int[(mid - start) + 1];
        int[] right = new int[end - mid];

        for(int i = 0; i <= mid - start; i++)
            left[i] = arr[start + i];
        for(int j = 0; j < end - mid; j++)
            right[j] = arr[mid + 1 + j];

        int i = 0, j = 0;
        int k = start;

        while (i < left.length && j < right.length){
            if(left[i] <= right[j]){
                arr[k] = left[i];
                i++;
            }
            else{
                arr[k] = right[j];
                j++;
            }
            k++;
        }

        while (i < left.length){
            arr[k] = left[i];
            i++;
            k++;
        }

        while (j < right.length){
            arr[k] = right[j];
            j++;
            k++;
        }
    }
}

Code-Erklärung

Die mergeSort-Methode teilt das Array rekursiv, bis Unterarrays nur noch ein Element enthalten. Die merge-Methode ist entscheidend; Es nimmt die sortierten Unterarrays und führt sie effizient zu einem einzigen sortierten Array zusammen. Der Zusammenführungsprozess umfasst den Vergleich von Elementen aus beiden Unterarrays und die Platzierung des kleineren Elements im Hauptarray.

Dieses Bild veranschaulicht den Zusammenführungsschritt.

Die Ausgabe des Codes ist:

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

Algorithmuskomplexität

• Zeitkomplexität: O(n log n) in allen Fällen (am besten, durchschnittlich und schlechtesten). Dies liegt daran, dass der Divide-and-Conquer-Ansatz unabhängig von der ursprünglichen Reihenfolge des Eingabearrays konsistent bleibt.
• Platzkomplexität: O(n) aufgrund des zusätzlichen Platzbedarfs für temporäre Arrays während des Zusammenführungsvorgangs.

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