Überblick
Zusammenführende Sortiermethode besteht darin, zwei (oder mehr als zwei) geordnete Tabellen in eine neue geordnete Tabelle zusammenzuführen, dh die zu sortierte Sequenz in mehrere Subsequenzen, jede Subsequenz wird geordnet. Anschließend werden die geordneten Untersequenzen in die insgesamt geordnete Sequenz zusammengefasst.
Die Zusammenführungssortierung wird unter Verwendung von Rekursion implementiert, die zu "Division und Eroberer" gehört. Das Zielarray ist von der Mitte in zwei unterteilt, und dann werden die beiden Arrays separat sortiert. Nach Abschluss der Sortierung werden die beiden Arrays zusammen "zusammengeführt". Das Wichtigste bei der Sortierung von Merge ist der "Zusammenführungs" -Prozess. Im Zusammenarbeit ist ein zusätzlicher Raum erforderlich, der mit den beiden Arrays übereinstimmt, die zusammengeführt werden müssen.
Reproduktionsbild:
Schritt
Wenden Sie Platz so an, dass seine Größe die Summe von zwei sortierten Sequenzen ist. Dieser Raum wird verwendet, um die zusammengeführte Sequenz auf zwei Zeiger zu speichern. Die anfängliche Position ist die Ausgangsposition der beiden sortierten Sequenzen, vergleichen Sie die Elemente, auf die die beiden Zeiger vermerkt sind, relativ kleine Elemente auswählen und in den zusammengeführten Raum setzen und den Zeiger in die nächste Position verschieben. Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz erreicht. Kopieren Sie alle verbleibenden Elemente der anderen Sequenz direkt bis zum Ende der zusammengeführten Sequenz.
Rohdaten:
3 5 2 6 2
Die Voraussetzung für die Verschmelzung besteht darin, die Arrays zu trennen, sie in zwei Teile zu unterteilen und dann in zwei Teile zu teilen, und sie können nicht erneut geteilt werden und sie verschmelzen.
Die erste Runde ist getrennt, Index 2 ((0+4)/2 = 2) ist die Mitte
[3 5 2] [6 2]
Die zweite Trennungsrunde getrennt [3 5 2]
[3 5] [2] [6 2]
Die dritte Trennungsrunde getrennt [3 5]
[3] [5] [2] [6 2]
Zusammenführen [3] [5]
[3 5] [2] [6 2]
Zusammenführen [3 5] [2]
[2 3 5] [6 2]
Die vierte Runde ist getrennt, trennt [6 2]
[2 3 5] [6] [2]
Zusammenführen [6] [2]
[2 3 5] [2 6]
Zusammenführen [2 3 5] [2 6]
[2 2 3 5 6]
Code -Implementierung (Java)
Paket com.coder4j.main.arithhmetic.sorting; öffentliche Klasse merge {private static int mark = 0; / ** * SORGE SORGE * * @PARAM Array * @param low * @param hoch * @return * / private static int [] sort (int [] Array, int low, int hoch) {int Mid = (Low + High) / 2; if (niedrig <hoch) {mark ++; System.out.println ("Wurf in Bearbeitung" + Mark + "nachfolgende Trennung, get"); System.out.println ("[" + low + "-" + Mid + "] [" + (Mid + 1) + "-" + High + "]"); // die linke Array -Sortierung (Array, niedrig, mittel); // die rechte Array -Sortierung (Array, Mid + 1, hoch); // links und rechts verschmelzen (Array, niedrig, mittel, hoch); } return Array; } / ** * Fusion das Array * * @param Array * @param low * @param Mid * @param hoch * / private statische void merge (int [] array, int low, int mid, int hoch) {system.out.println ("merge: [" + low + "-" + Mid + ". int [] temp = new int [hoch - niedrig + 1]; int i = niedrig; // linker Zeiger int j = Mid + 1; // rechter Zeiger int k = 0; // Bewegen Sie die kleinere Zahl zuerst in das Neue Array (i <= Mid && j <= High) {if (Array [i] <array [j]) {temp [k ++] = array [i ++]; } else {temp [k ++] = array [j ++]; }} // kann in einem der beiden Arrays verbleibende Elemente geben // die verbleibende Zahl links in das Array (i <= mid) {temp [k ++] = Array [i ++]; } // Verschieben Sie die verbleibende Zahl rechts in das Array, wobei (j <= hoch) {temp [k ++] = Array [j ++]; } // Überschreiben Sie die Zahlen im neuen Array -Array für (int m = 0; m <temp.length; m ++) {Array [m+low] = temp [m]; }} / ** * SORGE SORT * * @PARAM Array * @return * / public static int [] sort (int [] Array) {return sort (array, 0, array.length - 1); } public static void main (String [] args) {int [] array = {3, 5, 2, 6, 2}; int [] sortiert = sort (array); System.out.println ("Endergebnis"); für (int i: sortiert) {System.out.print (i + ""); }}}Testergebnisse Ergebnisse:
Die erste Trennung wird durchgeführt, und die [0-2] [3-4] wird durchgeführt, und die zweite Trennung wird durchgeführt, und die [0-1] [2-2] wird durchgeführt, und die dritte Trennung wird durchgeführt, wird durchgeführt, und die [0-0] [1-1] verschmelzen: [0: 0] und [1-1] und [1-1]. [3-3] [4-4] Zusammenführen: [3-3] und [4-4] Zusammenführen: [0-2] und [3-4] Endergebnis 2 2 3 5 6
Nach dem Test stimmt es mit den Ergebnissen im Beispiel überein.