Was ist Zusammenführungssortierung? Detaillierte Erklärung der Zusammenführungssortierung in Java

In Java implementierte Zusammenführungssortierung

Zusammenführungssortierung (MERGE-SORT) ist ein effektiver Sortieralgorithmus, der auf Zusammenführungsoperationen basiert. Dieser Algorithmus ist ein sehr typisches Beispiel für die Divide-and-Conquer-Methode (Pide and Conquer). Anwendung. 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 bidirektionalen Zusammenführung. Der Zusammenführungsprozess ist: Vergleichen Sie die Größen von a[i] und b[j], wenn a[i]≤b[j], kopieren Sie das Element a[i] in der ersten geordneten Liste nach r[k] und fügen Sie es hinzu 1 zu i bzw. k; andernfalls kopieren Sie das Element b[j] in der zweiten geordneten Liste nach r[k] und addieren 1 zu j bzw. k usw., bis Nach dem Abrufen einer geordneten Liste die verbleibende Elemente in der anderen geordneten Liste werden vom Index k bis zum Index t in die Zellen in r kopiert. Normalerweise verwenden wir Rekursion, um den Zusammenführungssortierungsalgorithmus zu implementieren. Wir teilen zuerst das zu sortierende Intervall [s, t] in der Mitte, sortieren dann den linken Teilbereich, dann den rechten Teilbereich und verwenden schließlich a Zusammenführungsvorgang zwischen dem linken Intervall und dem rechten Intervall. In geordnete Intervalle [s,t] zusammenführen.

Zwei Hauptpunkte:

1 Wie man zwei geordnete Sequenzen zu einer geordneten Sequenz zusammenführt

2 Wie man diese beiden Sequenzen in eine geordnete Sequenz umwandelt

Lösen Sie das erste Problem:

Wie füge ich zwei geordnete Serien zusammen? Das ist ganz einfach. Vergleichen Sie einfach die erste Nummer der beiden Sequenzen und nehmen Sie zuerst die kleinere. Löschen Sie dann die Nummer in der entsprechenden Sequenz. Vergleichen Sie sie dann. Wenn eine der Spalten leer ist, entnehmen Sie einfach die Daten der anderen Spalte einzeln.

public static void merge(int[] nums, int low, int mid, int high) {  
        int[] temp = new int[high - low + 1];  
        int i = low;// 左指针  
        int j = mid + 1;// 右指针  
        int k = 0;  
  
        // 把较小的数先移到新数组中  
        while (i <= mid && j <= high) {  
            if (nums[i] < nums[j]) {  
                temp[k++] = nums[i++];  
            } else {  
                temp[k++] = nums[j++];  
            }  
        }  
  
        // 把左边剩余的数移入数组  
        while (i <= mid) {  
            temp[k++] = nums[i++];  
        }  
  
        // 把右边边剩余的数移入数组  
        while (j <= high) {  
            temp[k++] = nums[j++];  
        }  
  
        // 把新数组中的数覆盖nums数组  
        for (int k2 = 0; k2 < temp.length; k2++) {  
            nums[k2 + low] = temp[k2];  
        }  
    }

Zweite Frage: Die Gruppen A und B können in zwei Gruppen unterteilt werden. Wenn die getrennte Gruppe nur einen Datenwert hat, kann analog davon ausgegangen werden, dass die Gruppe die Ordnung erreicht hat, und dann können die beiden benachbarten Gruppen zusammengeführt werden. Auf diese Weise wird die Zusammenführungssortierung abgeschlossen, indem das Array zunächst rekursiv zerlegt und dann zusammengeführt wird.

public static int[] sort(int[] nums, int low, int high) {  
        int mid = (low + high) / 2;  
        if (low < high) {  
            // 左边  
            sort(nums, low, mid);  
            // 右边  
            sort(nums, mid + 1, high);  
            // 左右归并  
            merge(nums, low, mid, high);  
        }  
        return nums;  
    }

Vollständiger Code:

package algorithm;import java.util.Arrays;public class MergeSort {	  public static int[] sort(int[] nums, int low, int high) {  
	        int mid = (low + high) / 2;  
	        if (low < high) {  
	              
	            sort(nums, low, mid);  
	             
	            sort(nums, mid + 1, high);  
	             
	            merge(nums, low, mid, high);  
	        }  
	        return nums;  
	    }  
	  
	    public static void merge(int[] nums, int low, int mid, int high) {  
	        int[] temp = new int[high - low + 1];  
	        int i = low;	        int j = mid + 1;  
	        int k = 0;  
	  
	        while (i <= mid && j <= high) {  
	            if (nums[i] < nums[j]) {  
	                temp[k++] = nums[i++];  
	            } else {  
	                temp[k++] = nums[j++];  
	            }  
	        }  
	  
	      
	        while (i <= mid) {  
	            temp[k++] = nums[i++];  
	        }  
	  
	      
	        while (j <= high) {  
	            temp[k++] = nums[j++];  
	        }  
	  
	        
	        for (int k2 = 0; k2 < temp.length; k2++) {  
	            nums[k2 + low] = temp[k2];  
	        }  
	    }  
	public static void main(String[] args) {		  int[] nums = { 29, 78, 800, 3, 551, 6, 97, 0, 5, 4 };  
		  
	        MergeSort.sort(nums, 0, nums.length-1);  
	        System.out.println(Arrays.toString(nums));  
	}

}

Das obige ist der detaillierte Inhalt vonWas ist Zusammenführungssortierung? Detaillierte Erklärung der Zusammenführungssortierung in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!