Zusammenführen sollen zwei (oder mehr als zwei) geordnete Tabellen in eine neue geordnete Tabelle zusammenführen, dh die zu sortierende Sequenz in mehrere Subsequenzen unterteilt, wobei jede Subsequenz geordnet ist. Dann werden die geordneten Untersequenzen in die geordnete Sequenz kombiniert.
Die Zusammenführungssortierung ist ein effektiver Sortieralgorithmus, der auf dem Zusammenführungsbetrieb basiert. Dieser Algorithmus ist eine sehr typische Anwendung von Kluft und Eroberung. Fusionieren Sie die geordneten Untersequenzen, um eine vollständig geordnete Sequenz zu erhalten. Wenn zwei bestellte Tische in eine bestellte Tabelle verschmolzen werden, wird dieser 2-Wege-Zusammenschluss bezeichnet.
Der Sortieralgorithmus ist stabil Nicht adaptiv und benötigt keine Daten.
Wie es funktioniert:
1. Bewerben Sie sich für Platz, damit seine Größe die Summe von zwei sortierten Sequenzen ist, mit denen die kombinierten Sequenzen gespeichert werden
2. Setzen Sie zwei Zeiger, die Anfangspositionen sind die Ausgangspositionen der beiden sortierten Sequenzen.
3. Vergleichen
4. Wiederholen Sie Schritt 3, bis ein Zeiger das Ende der Sequenz erreicht
5. Kopieren Sie alle verbleibenden Elemente einer anderen Sequenz direkt bis zum Ende der zusammengeführten Sequenz
Führen Sie den Code aus
Die Codekopie lautet wie folgt:
Paket com.zc.manythread;
import Java.util.random;
/**
* Bestellung
* @Author Ich bin
*
*/
öffentliche Klasse Mergesort {
public static void mergesort (int [] data) {
sortieren (Daten, 0, Data.Length - 1);
}
öffentliche statische Leerzeichen (int [] Daten, int links, int rechts) {
if (links> = rechts)
zurückkehren;
// den Zwischenindex finden
int center = (links + rechts) / 2;
// rekursiv das linke Array
sortieren (Daten, links, Mitte);
// rekursiv das rechte Array
sortieren (Daten, Zentrum + 1, rechts);
// Zusammenführen
zusammenführen (Daten, links, Mitte, rechts);
Druck (Daten);
}
/**
* Fucken Sie die beiden Arrays zusammen, verschmelzen die ersten beiden Arrays in Ordnung und bestellen Sie trotzdem nach der Verschmelzung
*
* @param Daten
* Array -Objekt
* @param links
* Index des ersten Elements des linken Arrays
* @param Center
* Der Index des letzten Elements des linken Arrays, Center+1, ist der Index des ersten Elements des rechten Arrays
* @param recht
* Index des letzten Elements des rechten Arrays
*/
public static void merge (int [] data, int links, int center, int rechts) {
// Temporäres Array
int [] tmparr = new int [data.length];
// Index des ersten Elements des rechten Arrays
int Mid = Center + 1;
// Dritter Aufzeichnung des Index des temporären Arrays
int dritter = links;
// zwischen dem Index des ersten Elements des linken Arrays zwischenstrichen
int tmp = links;
while (links <= center && mid <= rechts) {
// Nehmen Sie den kleinsten aus den beiden Arrays heraus und stecken Sie es in das temporäre Array
if (Data [links] <= data [Mid]) {
tmparr [dritter ++] = data [links ++];
} anders {
tmparr [dritter ++] = data [Mid ++];
}
}
// Geben Sie die verbleibenden Teile wiederum in das temporäre Array ein (tatsächlich wird nur einer der beiden ausgeführt)
while (Mid <= rechts) {
tmparr [dritter ++] = data [Mid ++];
}
while (links <= center) {
tmparr [dritter ++] = data [links ++];
}
// Kopieren Sie den Inhalt des temporären Arrays zurück zum ursprünglichen Array
// (Der Inhalt des ursprünglichen linken Rechtsbereichs wird zurück in das ursprüngliche Array kopiert)
while (tmp <= rechts) {
Daten [tmp] = tmparr [tmp ++];
}
}
public static void print (int [] data) {
für (int i = 0; i <data.length; i ++) {
System.out.print (Daten [i] + "/t");
}
System.out.println ();
}
/**
* Generieren Sie ein zufälliges Array
* @param count
* @zurückkehren
*/
private static int [] createdate (int count) {
int [] data = new int [count];
Random rand = new random ();
boolean [] bool = neuer boolean [100];
int num = 0;
für (int i = 0; i <count; i ++) {
Tun {
// Wenn die generierte Zahl gleich ist, werden Sie fortgesetzt, um weiter zu schleifen
Num = Rand.Nextint (100);
} while (bool [num]);
bool [num] = true;
Daten [i] = num;
}
Daten zurückgeben;
}
public static void main (String [] args) {
int [] data = createdate (10);
Druck (Daten);
mergesort (Daten);
System.out.println ("sortiertes Array:");
Druck (Daten);
}
}
Auslaufergebnisse:
Das obige dreht sich alles um diesen Artikel. Ich hoffe, Sie können es mögen.