Scalanie dwóch posortowanych sekwencji
Przechodzenie po obu listach za pomocą po jednym wskaźniku
Scalanie dwóch posortowanych sekwencji to bezpłatna lekcja Competitive Programming Academy na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Etap scalania
Mając dwie posortowane listy, należy połączyć je w jedną posortowaną listę. To scalanie jest sercem sortowania przez scalanie i pojawia się w wielu miejscach. 🔗
Dwa wejścia, po jednym wskaźniku
Każdej liście należy przypisać własny wskaźnik, zaczynający się od indeksu 0. Wskaźniki będą przesuwane razem do przodu, nigdy do tyłu.
i = 0
j = 0Zawsze wybieraj mniejszy element
W każdym kroku należy porównać dwa pierwsze elementy. Mniejszy z nich należy dodać do wyniku, ponieważ musi pojawić się jako następny w posortowanej kolejności.
Przesuń zwycięski wskaźnik
Po pobraniu wartości należy przesunąć wyłącznie wskaźnik listy, z której pochodziła. W drugiej liście nadal czeka jej najmniejszy element.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1Główna pętla
Scalanie należy kontynuować, dopóki obie listy zawierają elementy. Gdy jedna z nich się wyczerpie, porównywanie przestaje mieć sens.
while i < len(a) and j < len(b):
# compare and append
passDołączanie pozostałych elementów
Gdy jedna lista się wyczerpie, druga jest już posortowana, więc wystarczy bezpośrednio dołączyć jej pozostałą końcówkę do wyniku.
out.extend(a[i:])
out.extend(b[j:])Dlaczego końcówki nie wymagają pracy
Pozostała końcówka jest już uporządkowana, więc nie trzeba wykonywać kolejnych porównań. Jedno z dwóch wywołań extend po prostu niczego nie doda.
Łączny czas liniowy
Każdy element jest oglądany raz, więc scalanie list o rozmiarach n i m kosztuje O(n + m). Szybciej już się nie da.
Zachowanie stabilności
Użycie operatora <= przy równych wartościach zachowuje ich pierwotną kolejność. Stabilność ma znaczenie, gdy wraz z wartościami przechowywane są dodatkowe dane.
Scalanie również od końca
Aby scalać do bufora bez wolnego miejsca, należy zamiast tego przechodzić od końca, umieszczając największy element na ostatniej pozycji. Ta sama idea, tylko odwrócona.
Od scalania do sortowania
Podział, sortowanie połówek, a następnie scalanie — ta rekurencja to sortowanie przez scalanie. Poznane przed chwilą scalanie za pomocą dwóch wskaźników jest jego głównym mechanizmem.
Szybkie sprawdzenie
Scalają Państwo dwie posortowane listy, używając po jednym wskaźniku w każdej z nich.
Podsumowanie
Należy przechodzić przez dwie posortowane listy, używając po jednym wskaźniku w każdej, zawsze wybierać mniejszy pierwszy element, a następnie dołączyć pozostałą końcówkę. Algorytm działa w O(n + m) i jest podstawą sortowania przez scalanie. 🚀
Często zadawane pytania
Czy lekcja „Scalanie dwóch posortowanych sekwencji” jest bezpłatna?
Tak — pełny tekst „Scalanie dwóch posortowanych sekwencji” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Scalanie dwóch posortowanych sekwencji”?
Przechodzenie po obu listach za pomocą po jednym wskaźniku Ćwiczysz Competitive Programming Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Scalanie dwóch posortowanych sekwencji”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Dwa wskaźniki w posortowanej tablicy
- Znajdowanie pary o zadanej sumie
- Usuwanie duplikatów w miejscu
- Scalanie dwóch posortowanych sekwencji