Zusammenführungssortierung in Java

Jeder Programmierer muss zunächst das Schema/den Plan/die Architektur der zukünftigen Arbeit durchdenken, sonst endet alles im Chaos und in völliger Anarchie. Wie bei jedem Beitrag benötigen Sie zunächst einen Plan, fangen wir an.

1) Nehmen wir das Thema Merge-Sortierung für Anfänger.
2) Wir erstellen eine Architektur und einen Plan für die weitere Arbeit.
3) Wir werden alle Teile des Plans durcharbeiten und beschreiben.
4) Lassen Sie uns die Leistung und Qualität überprüfen.

2.1) Was ist Zusammenführungssortierung?

2.2) Beschreibung möglicher Signaturen.

2.3) Geben Sie ein Beispiel.

2.4) Beschreiben Sie die Implementierung in Java anhand eines Beispiels.

2.5) Alles Extra.

Sortierung zusammenführen Sortierung zusammenführen - 1

Sortierung zusammenführen Sortierung zusammenführen - 1

Zusammenführen – Zusammenführungssortierung in Java

Impliziert das Prinzip „Teile und herrsche“. Was ist die Idee und ihre Bedeutung?

Sortierung.

Wir teilen das Array in Teile auf, bis es einem Element entspricht. Jedes 1-Element wird sortiert.
Zusammenschluss.

Sortierte Elemente zusammenführen.
Basierend auf dem Prinzip von zwei Kartendecks. Wir legen 2 Kartenstapel mit ihren Werten nach oben auf den Tisch und die Karte mit dem niedrigsten Wert wird in den dritten resultierenden Kartenstapel gelegt. Wenn uns letztendlich die Karten in einem bestimmten Stapel ausgehen, verschieben wir sie einzeln in den resultierenden Stapel. Das Ergebnis ist eine Zusammenführung zweier sortierter Arrays, ein neues, sortiertes Array.

Die aufgewendete Zeit beträgt O(n log2 n). Das Sortieren gilt als recht schnell. Kurz zur algorithmischen Komplexität, falls jemand sie braucht. Oft sieht man Funktionen wie:

Sort(A, p, q);
Merge(A, p, q, r);

Das ist ungefähr das Gleiche, nur mit Indizes verknüpft. Die darin enthaltenen Variablen sind:

A = Array = Массив
p, q, r = индексы для массива
p - начало первого массива
q - конец первого массива
q + 1 - начало второго массива
r - конец второго массива

Wenn diese Variablen nicht beschrieben werden, weiß derjenige, der eine solche Funktion selbst erstellen möchte, nicht, was er will. Und Sie müssen Google durchsuchen, um herauszufinden, was es ist, wahrscheinlich werden Sie es finden, vielleicht. Lassen Sie uns ein Beispiel für unsere Sortierung geben. Es gibt ein Array {6, 1, 3, 5, 2, 4, 7, 8}. Wenn seine Länge größer als 1 ist, teilen wir es in zwei Teile und erhalten den linken Teil {6, 1, 3, 5}und den rechten Teil {2, 4, 7, 8}. Wir führen die Teilung in zwei Teile fort, bis die Länge größer als 1 ist. Als Ergebnis erhalten wir eine Reihe von Arrays mit einer Länge von 1 Element, nämlich: {6} {1} {3} {5} {2} {4} {7} {8}. Die Implementierung in Java sieht etwa so aus:

public int [] sortArray(int[] arrayA){ // Sortierung Массива который передается в функцию
        // проверяем не нулевой ли он?
        if (arrayA == null) {
            return null;
        }
        // проверяем не 1 ли элемент в массиве?
        if (arrayA.length < 2) {
            return arrayA; // возврат в рекурсию в строки ниже см комменты.
        }
        // копируем левую часть от начала до середины
        int [] arrayB = new int[arrayA.length / 2];
        System.arraycopy(arrayA, 0, arrayB, 0, arrayA.length / 2);

        // копируем правую часть от середины до конца массива, вычитаем из длины первую часть
        int [] arrayC = new int[arrayA.length - arrayA.length / 2];
        System.arraycopy(arrayA, arrayA.length / 2, arrayC, 0, arrayA.length - arrayA.length / 2);

        // рекурсией закидываем поделенные обе части обратно в наш метод, он будет крутится до тех пор,
        // пока не дойдет до 1 Element в массиве, после чего вернется в строку и будет искать второй такой же,
        // точнее правую часть от него и опять вернет его назад
        arrayB = sortArray(arrayB); // левая часть возврат из рекурсии строкой return arrayA;
        arrayC = sortArray(arrayC); // правая часть возврат из рекурсии строкой return arrayA;

        // далее опять рекурсия возврата слияния двух отсортированных массивов
        return mergeArray(arrayB, arrayC);
    }

Als nächstes müssen Sie diese Arrays zu 1 zusammenführen. Wie geht das? Um zu vermeiden, dass jedes Array mehrmals durchlaufen wird, geben wir Positionsindizes für jedes Array ein. Dann durchlaufen wir einmal eine Schleife, die der Länge der Summe dieser beiden Arrays entspricht. Nehmen Sie das erste Array und das zweite Array und nehmen Sie das erste Element. Vergleichen Sie Element Nummer 1 im ersten Array und Element Nummer 1 im zweiten Array . Der kleinere wird im resultierenden Array platziert. Hier ist es wichtig, dass, wenn wir ein Element aus dem ersten Array genommen haben, es sich beim Durchlaufen der Schleife auf das 2. Element des ersten Arrays und auf das 1. Element des zweiten Arrays beziehen sollte. Dazu müssen Sie den Index des zweiten Arrays um +1 erhöhen und ihn bei der Überprüfung von der Zyklusnummer subtrahieren, ähnlich wie beim ersten Array. Ist klar, warum man das tun sollte? Oder ist überhaupt nichts klar? :-) Zum Beispiel gibt es 2 Arrays: {1}{4}{8}und {3}{6}{7} Und es gibt eine Schleife:

for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i] < arrayB[i]) {
	arrayC[i] = arrayA[i];
	} else {
	arrayC[i] = arrayB[i];
	}
}

Beim ersten Durchlauf der Schleife stellt sich heraus arrayC[1] = {1}, dass wir dieses Element aus dem ersten Array übernommen haben. Wenn wir dann die zweite Schleife durchlaufen, müssen wir bereits das Element {4}und vergleichen {3}, aber dazu müssen wir die Positionsindizes und den Offset beider Arrays berücksichtigen, dazu geben wir sie ein.

int positionA = 0, positionB = 0;
for (int i = 0; i < arrayA.length + arrayB.length; i++) {
	if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}

Aber das ist noch nicht alles. Sie müssen berücksichtigen, dass einige Arrays möglicherweise früher enden. Es gibt zum Beispiel 3 Arrays: {1}{3}{5}und {6}{7}{9} Das erste Array endet, bevor das zweite eintrifft, dazu müssen Sie ein Häkchen setzen und im Prinzip ist die Merge-Funktion fertig.

public int [] mergeArray(int [] arrayА, int [] arrayB) {

int [] arrayC = int[arrayA.length + arrayB.length];
int positionA = 0, positionB = 0;

for (int i = 0; i < arrayC.length; i++) {
	if (positionA == arrayA.length){
	arrayC[i] = arrayB[i - positionB];
	positionB++;
	} else if (positionB == arrayB.length) {
	arrayC[i] = arrayA[i - positionA];
	positionA++;
	} else if (arrayA[i - positionA] < arrayB[i - positionB]) {
	arrayC[i] = arrayA[i - positionA];
	positionB++;
	} else {
	arrayC[i] = arrayB[i - positionB];
	positionA++;
	}
}
return arrayC;

Das Schwierigste an dieser Sortierung ist das Prinzip des rekursiven Übergangs. Diese. Wir werfen die linke Seite in die Rekursion, bis sie durch 2 teilbar ist, und wickeln sie dann zurück. In Worten ist es sehr kompliziert und verwirrend, aber wenn Sie versuchen, es sich vorzustellen, wenn es noch nicht klar ist, dann ist es ein völliges Durcheinander. Nehmen wir das Array: {2}{1}{4}{3}. Die erste Sortierrekursion teilt es in zwei Teile und führt die Funktion erneut mit den Elementen 2-1 aus , dann noch einmal mit den Elementen 2 und 1 und gibt sie der Reihe nach zurück, sodass sie zuerst in die Zusammenführungsfunktion gelangen und 1-2 kommt out , dann kehrt die Rekursion zurück und wirft 4-3 in die Zusammenführung , dann 4 und 3 , wonach die Zusammenführung 3-4 zurückgibt , und erst dann wird die Rekursion wieder abgewickelt und 1-2 und 3-4 werden sein in die Zusammenführung einbezogen und das sortierte Array wird 1-2-3-4 zurückgegeben . Das ist alles, das Sortieren besteht aus zwei Funktionen.

sortArray(array); 			// кладем массив который нужно отсортировать
mergeArray(arrayA, arrayB); 	// кладем 2 массива которые нужно слить в один

Wenn Sie eine Art Haupttext aufschreiben, erhalten Sie etwa Folgendes:

public static void main(String[] args) {
        Merge testMerge = new Merge();
        int [] result = testMerge.sortArray(new int[]{2,3,1,4});

        for (int i = 0; i < result.length ; i++) {
            System.out.print(result[i] + " ");
        }
    }

Für mich war diese Sortierung ein völliger Fehlschlag, es gab eine Million Fragen, aber keine Antworten, ich habe das gesamte Internet durchforstet, noch einmal gelesen, eine Menge Videos angeschaut, aber wie immer habe ich die Antworten nur selbst gefunden. Und erst als ich anfing, eine völlig andere Lösung zu schreiben als die, die überall aufblitzt) Aber am Ende ist es ähnlich geworden wie alle anderen))) Sortieren ist eigentlich das einfachste, die Hauptsache ist, es interaktiv in Aktion zu präsentieren, und Alles passt zusammen, wenn du den Dreh raus hast, ich mache ein Video)))) Bisher habe ich genug davon: Zusammenführen, Sortieren, Zusammenführen, Sortieren. Das Wichtigste ist, immer einen Plan daraus zu machen der Anfang. Es ist besser, ein wenig zu warten und nachzudenken, bevor Sie anfangen, etwas zu unternehmen. Es mag länger dauern, aber es wird ein Verständnis und eine Lösung entstehen, anstatt es ein paar Mal umschreiben und sich Krücken ausdenken zu müssen. Vielen Dank für Ihre Zeit, viel Glück und gute Laune. ) PS: Kritik, gute und schlechte, sowie Fragen sind herzlich willkommen. )))

Kommentare

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION