Rekursive Implementierung von Merge Sort in Java

Einführung

Merge Sort ist ein effizienter und stabiler Sortieralgorithmus, der die Divide-and-Conquer-Technik verwendet, um ein Array zu sortieren. In diesem Lab werden Sie lernen, wie Sie Merge Sort in Java mit einem rekursiven Ansatz implementieren.

Skills Graph

Erstellen einer Merge Sort-Methode

Erstellen Sie eine öffentliche statische Methode namens mergeSort(), die drei ganzzahlige Parameter hat: int arrToSort[], startIdx und endIdx. Sie müssen überprüfen, ob die Länge des Arrays kleiner als 2 ist. Wenn ja, geben Sie zurück. Andernfalls berechnen Sie den mittleren Index des Arrays und teilen Sie das Array in die linke und rechte Hälfte auf. Die linke und rechte Hälfte sollten ebenfalls rekursiv geteilt werden. Nachdem Sie sie geteilt haben, müssen Sie sie zusammenführen, um ein sortiertes Array zu bilden.

public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
    if (startIdx >= endIdx) {
        return;
    }

    int midIdx = startIdx + (endIdx - startIdx) / 2;
    mergeSort(arrToSort, startIdx, midIdx);
    mergeSort(arrToSort, midIdx + 1, endIdx);
    merge(arrToSort, startIdx, midIdx, endIdx);
}

Erstellen einer Merge-Methode

Erstellen Sie eine weitere öffentliche statische Methode namens merge(), die vier Parameter hat: int arrToSort[], startIdx, midIdx und endIdx. Sie müssen die linke und rechte Array initialisieren. Dann müssen Sie beide Arrays durch das Vergleichen der Elemente jedes Arrays und das Zusammenführen sie in ein einzelnes Array zusammenführen.

public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
    int[] leftArr = new int[midIdx - startIdx + 1];
    int[] rightArr = new int[endIdx - midIdx];

    for (int i = 0; i < leftArr.length; i++) {
        leftArr[i] = arrToSort[startIdx + i];
    }
    for (int i = 0; i < rightArr.length; i++) {
        rightArr[i] = arrToSort[midIdx + i + 1];
    }

    int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
    while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
        if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
            arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
            leftArrIdx += 1;
        } else {
            arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
            rightArrIdx += 1;
        }
        sortedArrIdx += 1;
    }

    while (leftArrIdx < leftArr.length) {
        arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
        leftArrIdx += 1;
        sortedArrIdx += 1;
    }

    while (rightArrIdx < rightArr.length) {
        arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
        rightArrIdx += 1;
        sortedArrIdx += 1;
    }
}

Testen von Merge Sort

Lassen Sie uns die mergeSort()-Methode testen, indem wir Code schreiben, um ein Eingabe-Array zu sortieren. Erstellen Sie eine main-Methode. Dann deklarieren Sie ein ganzzahliges Array mit einigen unsortierten Werten. Rufen Sie die mergeSort()-Methode auf und übergeben Sie das unsortierte Array an sie. Schließlich geben Sie das sortierte Array in der Konsole aus. Der Codeblock für diesen Schritt wird wie folgt aussehen:

public static void main(String[] args) {
    int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
    mergeSort(arrToSort, 0, arrToSort.length - 1);
    System.out.println(Arrays.toString(arrToSort));
}

Nachdem das Programm ausgeführt wurde, sollte die Ausgabe lauten: [0, 1, 2, 4, 6, 8].

Test mit einem leeren Array

Erstellen Sie einen weiteren Test für ein leeres Array. Deklarieren Sie ein leeres ganzzahliges Array. Rufen Sie die mergeSort()-Methode auf und übergeben Sie das leere Array an sie. Schließlich geben Sie das sortierte Array in der Konsole aus. Der Codeblock für diesen Schritt wird wie folgt aussehen:

int[] emptyArr = {};
mergeSort(emptyArr, 0, emptyArr.length - 1);
System.out.println(Arrays.toString(emptyArr));

Die Ausgabe sollte der Eingabe entsprechen.

Test mit einem Array mit einem Element

Erstellen Sie einen weiteren Test mit einem Array mit einem Element. Deklarieren Sie ein ganzzahliges Array mit einem Element. Rufen Sie die mergeSort()-Methode auf und übergeben Sie das Array mit einem Element an sie. Schließlich geben Sie das sortierte Array in der Konsole aus. Der Codeblock für diesen Schritt wird wie folgt aussehen:

int[] singleElementArr = {7};
mergeSort(singleElementArr, 0, singleElementArr.length - 1);
System.out.println(Arrays.toString(singleElementArr));

Die Ausgabe sollte der Eingabe entsprechen.

Test mit negativen Werten

Erstellen Sie einen weiteren Test für ein Array, das aus negativen ganzen Zahlen besteht. Deklarieren Sie ein ganzzahliges Array, das einige negative ganze Zahlen enthält. Rufen Sie die mergeSort()-Methode auf und übergeben Sie das Array als Argument. Schließlich geben Sie das sortierte Array in der Konsole aus. Der Codeblock für diesen Schritt wird wie folgt aussehen:

int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
System.out.println(Arrays.toString(arrWithNegatives));

Nachdem das Programm ausgeführt wurde, sollte die Ausgabe lauten: [-9, -7, -1, 0, 2, 6, 8].

Test mit nicht numerischen Elementen

Erstellen Sie einen weiteren Test, indem Sie ein Array aus nicht numerischen Elementen sortieren. Deklarieren Sie ein Array von Strings. Rufen Sie die mergeSort()-Methode auf und übergeben Sie das Array als Argument. Schließlich geben Sie das sortierte Array in der Konsole aus. Der Codeblock für diesen Schritt wird wie folgt aussehen:

String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
mergeSort(strsToSort, 0, strsToSort.length - 1);
System.out.println(Arrays.toString(strsToSort));

Nachdem das Programm ausgeführt wurde, sollte die Ausgabe lauten: ['Bob', 'Christine', 'David', 'Emily', 'John'].

需要说明的是，这里输出中的单引号在Java字符串中实际应该是双引号，即正确输出应该是 ["Bob", "Christine", "David", "Emily", "John"] 。

Endgültiger Quellcode

Hier ist der Endgültige Quellcode für Merge Sort:

import java.util.Arrays;

public class MergeSort {
   public static void mergeSort(int[] arrToSort, int startIdx, int endIdx) {
       if (startIdx >= endIdx) {
           return;
       }

       int midIdx = startIdx + (endIdx - startIdx) / 2;
       mergeSort(arrToSort, startIdx, midIdx);
       mergeSort(arrToSort, midIdx + 1, endIdx);
       merge(arrToSort, startIdx, midIdx, endIdx);
   }

   public static void merge(int[] arrToSort, int startIdx, int midIdx, int endIdx) {
       int[] leftArr = new int[midIdx - startIdx + 1];
       int[] rightArr = new int[endIdx - midIdx];

       for (int i = 0; i < leftArr.length; i++) {
           leftArr[i] = arrToSort[startIdx + i];
       }

       for (int i = 0; i < rightArr.length; i++) {
           rightArr[i] = arrToSort[midIdx + i + 1];
       }

       int leftArrIdx = 0, rightArrIdx = 0, sortedArrIdx = startIdx;
       while ((leftArrIdx < leftArr.length) && (rightArrIdx < rightArr.length)) {
           if (leftArr[leftArrIdx] < rightArr[rightArrIdx]) {
               arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
               leftArrIdx += 1;
           } else {
               arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
               rightArrIdx += 1;
           }
           sortedArrIdx += 1;
       }

       while (leftArrIdx < leftArr.length) {
           arrToSort[sortedArrIdx] = leftArr[leftArrIdx];
           leftArrIdx += 1;
           sortedArrIdx += 1;
       }

       while (rightArrIdx < rightArr.length) {
           arrToSort[sortedArrIdx] = rightArr[rightArrIdx];
           rightArrIdx += 1;
           sortedArrIdx += 1;
       }
   }

   public static void main(String[] args) {
       //create an unsorted integer array
       int[] arrToSort = { 4, 2, 8, 0, 1, 6 };
       //sort the integer array using Merge Sort
       mergeSort(arrToSort, 0, arrToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrToSort));

       //create an empty integer array
       int[] emptyArr = {};
       //sort the empty array
       mergeSort(emptyArr, 0, emptyArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(emptyArr));

       //create a single-element array
       int[] singleElementArr = {7};
       //sort the single-element array
       mergeSort(singleElementArr, 0, singleElementArr.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(singleElementArr));

       //create a negative integer array
       int[] arrWithNegatives = {-7, 2, -9, 0, -1, 6, 8};
       //sort the negative integer array
       mergeSort(arrWithNegatives, 0, arrWithNegatives.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(arrWithNegatives));

       //create a string array
       String[] strsToSort = {"John", "David", "Emily", "Bob", "Christine"};
       //sort the string array
       mergeSort(strsToSort, 0, strsToSort.length - 1);
       //print the sorted array
       System.out.println(Arrays.toString(strsToSort));
   }
}

Führen Sie das Programm aus

Kompilieren und führen Sie das Programm über die Kommandozeile aus:

javac MergeSort.java && java MergeSort

Zusammenfassung

In diesem Lab haben Sie gelernt, was Merge Sort ist, wie es funktioniert und wie es in Java implementiert wird. Sie haben zwei öffentliche statische Methoden, mergeSort() und merge(), erstellt, um das Eingabearray jeweils zu teilen und zu mergen. Nach der Implementierung haben Sie es mit verschiedenen Eingaben getestet, die Zeit- und Raumkomplexität diskutiert und seine Funktionalität verifiziert. Herzlichen Glückwunsch! Sie haben das Merge Sort Lab in Java erfolgreich abgeschlossen.