Слияние двух отсортированных последовательностей
Проходите по обоим спискам отдельным указателем
«Слияние двух отсортированных последовательностей» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Шаг слияния
Даны два отсортированных списка. Объедините их в один отсортированный список. Это слияние лежит в основе сортировки слиянием и встречается повсюду. 🔗
Два входа, по одному указателю
Назначьте каждому списку собственный указатель, оба указателя должны начинать с индекса 0. Продвигайте их вместе только вперёд, никогда не возвращаясь назад.
i = 0
j = 0Всегда выбирайте меньший элемент
На каждом шаге сравнивайте два первых элемента. Добавляйте меньший в результат, поскольку именно он должен идти следующим в отсортированном порядке.
Продвигайте указатель выбранного элемента
После выбора значения продвиньте advance только тот указатель, из списка которого оно взято. В другом списке по-прежнему ожидает его наименьший элемент.
if a[i] <= b[j]:
out.append(a[i])
i += 1
else:
out.append(b[j])
j += 1Основной цикл
Продолжайте слияние, пока в обоих списках ещё есть элементы. Как только один список закончится, сравнение больше не имеет смысла.
while i < len(a) and j < len(b):
# compare and append
passДобавьте оставшиеся элементы
Когда один список опустеет, другой уже отсортирован, поэтому просто append его оставшийся хвост непосредственно к результату.
out.extend(a[i:])
out.extend(b[j:])Почему хвосты не требуют работы
Оставшийся хвост уже упорядочен, поэтому дальнейшие сравнения не нужны. Один из двух вызовов extend просто ничего не добавит.
Общая линейная сложность
Каждый элемент просматривается один раз, поэтому слияние списков размеров n и m занимает O(n + m) времени. Быстрее уже не получится.
Сохраняйте устойчивость
Использование <= при равных значениях сохраняет исходный порядок одинаковых элементов. Эта устойчивость важна, когда вместе с элементами хранятся дополнительные данные.
Слияние в обратном направлении
Чтобы выполнить слияние в буфер без свободного места, двигайтесь от конца, помещая наибольший элемент последним. Та же идея, отражённая наоборот.
От слияния к сортировке
Разделить, отсортировать половины, затем объединить — это рекурсивная сортировка слиянием. Освоенное Вами слияние с двумя указателями — её основной механизм.
Быстрая проверка
Вы объединяете два отсортированных списка, используя по одному указателю в каждом.
Повторение
Просматривайте два отсортированных списка, используя по одному указателю в каждом: всегда выбирайте меньший первый элемент, а затем добавляйте оставшийся хвост. Алгоритм работает за O(n + m) и лежит в основе сортировки слиянием. 🚀
Часто задаваемые вопросы
Урок «Слияние двух отсортированных последовательностей» бесплатный?
Да — полный текст урока «Слияние двух отсортированных последовательностей» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Слияние двух отсортированных последовательностей»?
Проходите по обоим спискам отдельным указателем Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.
Сколько времени занимает урок «Слияние двух отсортированных последовательностей»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Два указателя в отсортированном массиве
- Поиск пары с заданной суммой
- Удаление дубликатов на месте
- Слияние двух отсортированных последовательностей