Zwei sortierte Sequenzen zusammenführen
Durchlaufen Sie beide Listen mit jeweils einem Zeiger
Zwei sortierte Sequenzen zusammenführen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Der Merge-Schritt
Führen Sie zwei sortierte Listen zu einer sortierten Liste zusammen. Dieser Merge ist das Herzstück von Mergesort und taucht überall auf. 🔗
Zwei Eingaben, je ein Zeiger
Geben Sie jeder Liste einen eigenen Zeiger, der jeweils bei Index 0 beginnt. Sie bewegen beide gemeinsam vorwärts, niemals rückwärts.
i = 0
j = 0Immer das kleinere Element nehmen
Vergleichen Sie bei jedem Schritt die beiden Anfangselemente. Fügen Sie das kleinere Element zum Ergebnis hinzu, weil es in der sortierten Reihenfolge als Nächstes kommen muss.
Den Gewinner weiterschieben
Nachdem Sie einen Wert übernommen haben, verschieben Sie nur den Zeiger, aus dessen Liste er stammt. In der anderen Liste wartet weiterhin ihr kleinstes Element.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1Die Hauptschleife
Führen Sie das Zusammenführen solange fort, wie beide Listen noch Elemente enthalten. Sobald eine Liste leer ist, ergibt der Vergleich keinen Sinn mehr.
while i < len(a) and j < len(b):
# compare and append
passDie übrigen Elemente anhängen
Wenn eine Liste leer ist, ist die andere bereits sortiert. Fügen Sie ihren verbleibenden Rest einfach direkt mit append an das Ergebnis an.
out.extend(a[i:])
out.extend(b[j:])Warum die Reste keine Arbeit machen
Der verbleibende Rest ist bereits sortiert, daher sind keine weiteren Vergleiche nötig. Einer der beiden extend-Aufrufe fügt einfach nichts hinzu.
Insgesamt lineare Laufzeit
Jedes Element wird einmal betrachtet. Daher benötigt das Zusammenführen zweier Listen der Größen n und m O(n + m) Zeit. Schneller geht es nicht.
Die Stabilität bewahren
Wenn Sie bei gleichen Werten <= verwenden, behalten gleiche Elemente ihre ursprüngliche Reihenfolge bei. Diese Stabilität ist wichtig, wenn Sie zusätzliche Daten mitführen.
Auch rückwärts mergen
Um in einen Puffer ohne freien Speicher zusammenzuführen, durchlaufen Sie ihn stattdessen vom hinteren Ende aus und setzen das größte Element zuletzt ein. Dieselbe Idee, nur gespiegelt.
Vom Merge zum Sortieren
Aufteilen, die Hälften sortieren, dann zusammenführen: Diese Rekursion ist Mergesort. Das soeben gelernte Zusammenführen mit zwei Zeigern ist sein Kernmechanismus.
Kurzer Check
Sie führen zwei sortierte Listen zusammen und verwenden jeweils einen Zeiger.
Zusammenfassung
Durchlaufen Sie zwei sortierte Listen mit jeweils einem Zeiger, nehmen Sie immer das kleinere Anfangselement und hängen Sie anschließend den Rest an. Das Verfahren benötigt O(n + m) Zeit und bildet die Grundlage von Mergesort. 🚀
Häufig gestellte Fragen
Ist die Lektion „Zwei sortierte Sequenzen zusammenführen“ kostenlos?
Ja — der vollständige Text von „Zwei sortierte Sequenzen zusammenführen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Zwei sortierte Sequenzen zusammenführen“?
Durchlaufen Sie beide Listen mit jeweils einem Zeiger Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Zwei sortierte Sequenzen zusammenführen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Zwei Zeiger in einem sortierten Array
- Ein Paar mit einer gegebenen Summe finden
- Duplikate direkt entfernen
- Zwei sortierte Sequenzen zusammenführen