Основы понимания и реализации сортировки слиянием
Алгоритмы сортировки — отличный способ погрузиться в мир структур данных и алгоритмов. Сортировка слиянием была первой, которую я изучил и которая заставила меня осознать, что методы, которые мы выбираем как разработчики для развертывания в наших программах, могут в огромной степени определять производительность нашего кода.
Интуиция
Я разобью процесс на два этапа:
- раздел
- стежок
да, это так просто. Вроде.
Раздел
рекурсивно разделите массив из середины на 2 массива, пока вы больше не сможете разделять.
Сшить (или объединить)
Итак, теперь у нас много сломанных деталей. Начинаем сшивать их обратно. Мы меняем раздел, но с изюминкой. Мы устанавливаем счетчик для двух массивов, которые мы сшиваем, и помещаем меньший элемент в массив. Таким образом, наша сшивка будет представлять собой слияние двух разделов, но отсортированное, следовательно, сортировка слиянием.
Представление
Время выполнения: O(n⋅log(n))
разделив массивы пополам и спускаясь вниз, мы спустимся вниз по log(n), чтобы достичь массива размера 1. На каждом уровне мы будем объединять n элементов независимо от количества разделов. с n разделами мы делаем слияния n/2 раз, которые становятся размером 2 ( n/2 * 2 = n), и на последнем шаге мы объединяемся один раз, но получаем размер n (2 * n/2 = n)
Пробел: O(n)
Выполнение
Теперь давайте реализуем это на C++.
Сделайте шаг вперед
мы рассмотрели реализацию сортировки слиянием для массива чисел. Однако сортировку слиянием можно реализовать для любой коллекции, которую можно сравнить. Группа слов, например, может быть упорядочена в алфавитном порядке. Или даже структуру со своим методом сравнения.
- Мы можем реализовать код, который берет сопоставимый массив любого типа и объединяет его с помощью сортировки слиянием.
Дополнительные ресурсы:
если вам понравилась эта статья, не стесняйтесь поделиться. Если у вас есть какие-либо отзывы или вопросы, напишите мне по адресу [email protected].
