Implementieren und optimieren Sie den Merge-Sort-Algorithmus von Java

Implementierung und Optimierung des Java-Merge-Sortieralgorithmus

Merge-Sortierung ist ein Sortieralgorithmus, der auf Vergleichen basiert. Seine Hauptidee besteht darin, die zu sortierende Sequenz in mehrere Teilsequenzen zu unterteilen, jede Teilsequenz zu sortieren und schließlich geordnete Teilsequenzen zu erstellen werden zu einer geordneten Gesamtfolge zusammengefügt.

1. Implementierung des Zusammenführungssortierungsalgorithmus:
   Die Implementierung des Zusammenführungssortierungsalgorithmus kann in zwei Schritte unterteilt werden: Teilen und Erobern und Zusammenführen.

(1) Teilen und erobern:
Teilen Sie zunächst die zu sortierende Sequenz in zwei Teile, bis jede Teilsequenz nur noch ein Element enthält. Anschließend werden diese Teilsequenzen zu geordneten Teilsequenzen zusammengeführt.

Das Folgende ist ein Beispielcode für eine rekursive Implementierung des Merge-Sort-Algorithmus:

public class MergeSort {
    // 归并排序
    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            // 递归地对左右两边进行归并排序
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            // 合并两个有序子序列
            merge(array, left, mid, right);
        }
    }

    // 合并两个有序子序列
    public void merge(int[] array, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left; // 左序列指针
        int j = mid + 1; // 右序列指针
        int k = 0; // 临时数组指针

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < temp.length; l++) {
            array[left + l] = temp[l];
        }
    }
}

(2) Merge:
Die Funktion der Merge-Funktion besteht darin, zwei geordnete Teilsequenzen zu einer geordneten Sequenz zusammenzuführen. In der spezifischen Implementierung müssen wir ein temporäres Array erstellen, um die zusammengeführten Ergebnisse zu speichern. Beim Durchlaufen einer Teilsequenz vergleichen wir die Elemente in der Teilsequenz, fügen das kleinere Element in ein temporäres Array ein und bewegen den entsprechenden Zeiger. Abschließend werden die Elemente im temporären Array zurück in das ursprüngliche Array kopiert.

2. Optimierung des Zusammenführungssortierungsalgorithmus:
   Der Zusammenführungssortierungsalgorithmus generiert während des rekursiven Prozesses viele temporäre Teilsequenzarrays, was zu einer häufigen Zuweisung und Freigabe von Speicher führt und die Speicherplatzkomplexität des Algorithmus erhöht. Um diesen Overhead zu reduzieren, kann die Effizienz des Zusammenführungssortierungsalgorithmus durch die folgenden Optimierungsmethoden verbessert werden:

(1) Verwenden Sie die Einfügungssortierung für kleine Teilsequenzen:
Wenn die Größe der Teilsequenz relativ klein ist, Einfügung Sortieren ist effizienter. Wenn daher während des rekursiven Prozesses der Zusammenführungssortierung die Größe der Teilsequenz unter einem bestimmten Schwellenwert liegt, kann die Einfügungssortierung verwendet werden, um den rekursiven Prozess zu ersetzen.

public void mergeSort(int[] array, int left, int right) {
    if (left < right) {
        if (right - left <= THRESHOLD) {
            // 子序列的规模小于阈值，采用插入排序
            insertionSort(array, left, right);
        } else {
            int mid = (left + right) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
}

(2) Optimieren Sie den Zusammenführungsprozess:
Während des Zusammenführungsprozesses können Sie zunächst die beiden Teilsequenzen in zwei temporären Arrays speichern und dann die beiden temporären Arrays mit dem ursprünglichen Array zusammenführen. Auf diese Weise vermeiden Sie, dass während des Zusammenführungsvorgangs wiederholt temporäre Arrays erstellt werden. Da die Größe des temporären Arrays fest ist, kann es gleichzeitig als Mitgliedsvariable der Klasse definiert werden, um eine wiederholte Erstellung während des rekursiven Prozesses zu vermeiden.

public class MergeSort {
    private int[] temp;

    public void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            if (right - left <= THRESHOLD) {
                insertionSort(array, left, right);
            } else {
                int mid = (left + right) / 2;
                mergeSort(array, left, mid);
                mergeSort(array, mid + 1, right);
                merge(array, left, mid, right);
            }
        }
    }

    public void merge(int[] array, int left, int mid, int right) {
        int i = left;
        int j = mid + 1;
        int k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int l = 0; l < k; l++) {
            array[left + l] = temp[l];
        }
    }
}

Zusammenfassend ist das Obige die Implementierung des Java-Merge-Sortieralgorithmus und seiner Optimierungsmethode. Durch die Optimierung des Zusammenführungsprozesses und die Verwendung der Einfügungssortierung für kleine Teilsequenzen kann die Effizienz des Zusammenführungssortierungsalgorithmus verbessert und der Platzaufwand reduziert werden. In praktischen Anwendungen kann die Auswahl geeigneter Optimierungsmethoden und das Treffen vernünftiger Entscheidungen basierend auf den Merkmalen der Sortierreihenfolge den Algorithmus effizienter machen.

Das obige ist der detaillierte Inhalt vonImplementieren und optimieren Sie den Merge-Sort-Algorithmus von Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!