Wie man zwei sortierte Arrays in Java zusammenführt / Baeldung

Einführung

In diesem Tutorial lernen wir, wie man zwei sortierte Arrays zu einem einzigen sortierten Array zusammenführt.

Problem

Lassen Sie uns das Problem verstehen. Wir haben zwei sortierte Arrays und möchten sie zu einem zusammenführen.

Sortierte Arrays zusammenführen

Algorithmus

Wenn wir das Problem analysieren, ist es ziemlich einfach zu beobachten, dass wir dieses Problem lösen können, indem wir die Zusammenführungsoperation von Merge Sort verwenden.Nehmen wir an, wir haben zwei sortierte Arrays foo und bar der Länge fooLength bzw. Als nächstes können wir ein anderes Array deklarieren, das aus size Length + barLength besteht.

Wir sollten dann beide Arrays in derselben Schleife durchlaufen. Wir behalten jeweils einen aktuellen Indexwert für fooPosition und barPosition bei. Bei einer bestimmten Iteration unserer Schleife nehmen wir das Array mit dem kleinwertigen Element an seinem Index und bringen diesen Index voran. Dieses Element belegt die nächste Position im zusammengeführten Array.

Nachdem wir alle Elemente aus einem Array übertragen haben, kopieren wir die verbleibenden Elemente aus dem anderen Array in das zusammengeführte Array.

Lassen Sie uns nun den Prozess in Bildern sehen, um den Algorithmus besser zu verstehen.

Schritt 1:

Wir beginnen mit dem Vergleich der Elemente in beiden Arrays und wählen das kleinere aus.

Arrays zusammenführen Erster Schritt

Dann erhöhen wir die Position im ersten Array.

Schritt 2:

Arrays zusammenführen Zweiter Schritt

Hier erhöhen wir die Position im zweiten Array und fahren mit dem nächsten Element fort, das 8 ist.

Schritt 3:
Arrays zusammenführen Dritter Schritt

Am Ende dieser Iteration haben wir alle Elemente des ersten Arrays durchlaufen.

Schritt 4:

In diesem Schritt kopieren wir einfach alle verbleibenden Elemente aus dem zweiten Array nach result .

Arrays zusammenführen Vierter Schritt

Implementierung

Nun wollen wir sehen, wie es implementiert wird:

public static int merge(int foo, int bar) { int fooLength = foo.length; int barLength = bar.length; int merged = new int; int fooPosition, barPosition, mergedPosition; fooPosition = barPosition = mergedPosition = 0; while(fooPosition < fooLength && barPosition < barLength) { if (foo < bar) { merged = foo; } else { merged = bar; } } while (fooPosition < fooLength) { merged = foo; } while (barPosition < barLength) { merged = bar; } return merged;}

Und fahren wir mit einem kurzen Test fort:

@Testpublic void givenTwoSortedArrays_whenMerged_thenReturnMergedSortedArray() { int foo = { 3, 7 }; int bar = { 4, 8, 11 }; int merged = { 3, 4, 7, 8, 11 }; assertArrayEquals(merged, SortedArrays.merge(foo, bar));}

Komplexität

Wir durchqueren Sie beide Arrays und wählen Sie das kleinere Element aus. Am Ende kopieren wir den Rest der Elemente aus dem foo oder dem bar Array. Die Zeitkomplexität wird also zu O(fooLength + barLength) . Wir haben ein Hilfsarray verwendet, um das Ergebnis zu erhalten. Die Raumkomplexität ist also auch O(barLength + barLength).

Fazit

In diesem Tutorial haben wir gelernt, wie man zwei sortierte Arrays zu einem zusammenführt.