Was ist das Prinzip des Merge-Sort-Algorithmus in Java und wie wird er implementiert?

1. Grundidee

Merge Sort ist ein effektiver Sortieralgorithmus, der auf Merge-Operationen basiert. Dieser Algorithmus ist eine sehr typische Anwendung der Divide-and-Conquer-Methode (Divide and Conquer). Führen Sie die bereits geordneten Teilsequenzen zusammen, um eine vollständig geordnete Sequenz zu erhalten. Ordnen Sie also zuerst jede Teilsequenz und dann die Teilsequenzsegmente. Wenn zwei geordnete Listen zu einer geordneten Liste zusammengeführt werden, spricht man von einer 2-Wege-Zusammenführung.

2. Algorithmusanalyse

1. Algorithmusbeschreibung

Teilen Sie die Eingabesequenz der Länge n in zwei Teilsequenzen der Länge n/2 ;Verwenden Sie Zusammenführung Sortieren der beiden Teilsequenzen; Zusammenführen der beiden sortierten Teilsequenzen zu einer endgültigen Sortiersequenz.

2. Prozessanalyse

(1) Jetzt werden wir die Begriffe [1] (Index von 0 bis 0, beide Seiten eingeschlossen) und [28] Index aufteilen 1 zu 1, beide inklusive) werden zusammengeführt.

(2), weil 1 (linke Teilung) <= 28 (rechte Teilung), kopieren wir {rightPart} in das neue Array.

(3) Da der linke Split leer ist, kopieren wir 28 (rechter Split) in das neue Array.

(4) Wir kopieren die Elemente im neuen Array zurück in das ursprüngliche Array.

(5), weil 3 (linke Teilung) <= 21 (rechte Teilung), kopieren wir {rightPart} in das neue Array.

(6) Da der linke Split leer ist, kopieren wir 21 (rechter Split) in ein neues Array.

(7), Jetzt werden wir die Begriffe [1,28] (Index von 0 bis 1, beide Seiten eingeschlossen) und [3, 21] Exponenten von 2 bis 3, beide Seiten eingeschlossen) werden zusammengeführt.

(8), weil 1 (linke Teilung) <= 3 (rechte Teilung), kopieren wir {rightPart} in das neue Array.

(9), weil 28 (links geteilt) > 3 (rechts geteilt), kopieren wir {rightPart} in ein neues Array.

(10), weil 28 (links geteilt) > 21 (rechts geteilt), kopieren wir {rightPart} in ein neues Array.

(11), da der rechte Split leer ist, kopieren wir 28 (linker Split) in das neue Array.

(12) kopieren wir die Elemente im neuen Array zurück in das ursprüngliche Array.

(13), jetzt werden wir die Terme [11] (mit Exponenten von 4 bis 4, beide Seiten eingeschlossen) und [7] mit aufteilen Exponent von 5 bis 5, beide inklusive) werden zusammengeführt.

(14), weil 11 (links geteilt) > 7 (rechts geteilt), kopieren wir {rightPart} in ein neues Array.

(15), da der rechte Split leer ist, kopieren wir 11 (linker Split) in das neue Array.

(16) kopieren wir die Elemente im neuen Array zurück in das ursprüngliche Array.

(17) und so weiter

(18), weil 1 (links geteilt) <= 6 ( rechts geteilt), kopieren wir {rightPart} in ein neues Array.

(19), da 3 (links geteilt) <= 6 (rechts geteilt) kopieren wir {rightPart} in das neue Array.

(20), weil 21 (links geteilt) > 6 (rechts geteilt), kopieren wir {rightPart} in ein neues Array.

(21), weil 21 (links geteilt) > 7 (rechts geteilt), kopieren wir {rightPart} in ein neues Array.

(22) usw. Wir kopieren die Elemente im neuen Array zurück in das ursprüngliche Array.

3. GIF-Demonstration

3. Algorithmusimplementierung# 🎜 🎜 #

package com.algorithm.tenSortingAlgorithm;

import java.util.Arrays;

public class MergeSort {
    private static void mergeSort(int[] arr, int low, int high) {
        if (low < high) { //当子序列中只有一个元素时结束递归
            int mid = (low + high) / 2; //划分子序列
            mergeSort(arr, low, mid); //对左侧子序列进行递归排序
            mergeSort(arr, mid + 1, high); //对右侧子序列进行递归排序
            merge(arr, low, mid, high); //合并
        }
    }

    private static void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[arr.length]; //辅助数组
        int k = 0, i = low, j = mid + 1; //i左边序列和j右边序列起始索引,k是存放指针
        while (i <= mid && j <= high) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        //如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        //同上
        while (j <= high) {
            temp[k++] = arr[j++];
        }
        //复制回原数组
        for (int t = 0; t < k; t++) {
            arr[low + t] = temp[t];
        }
    }

    public static void main(String[] args) {
        int[] arr = {1,28,3,21,11,7,6,18};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

Das obige ist der detaillierte Inhalt vonWas ist das Prinzip des Merge-Sort-Algorithmus in Java und wie wird er implementiert?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!