Этот блог основан на подходе «разделяй и властвуй». Сортировка слиянием - это алгоритм «разделяй и властвуй», в котором проблема делится на подзадачи, а затем объединяется для получения решения. Этот блог о сортировке слиянием в подробно расскажет о следующих темах -
- Что такое сортировка слиянием в Python?
- Подход «разделяй и властвуй»
- Реализация сортировки слиянием в Python
- Блок-схема реализации сортировки слиянием
- Преимущества и использование
Что такое сортировка слиянием в Python?
Сортировка слиянием основана на алгоритме «разделяй и властвуй», в котором входной массив делится на две половины, затем сортируется отдельно и объединяется для достижения решения. Функция merge () используется для объединения отсортированных .
Подход «разделяй и властвуй»
- Массив делится пополам, и процесс повторяется с каждой половиной, пока каждая половина не будет иметь размер 1 или 0.
- Массив размера 1 сортируется тривиально.
- Теперь два отсортированных массива объединены в один большой массив. И так продолжается до тех пор, пока все элементы не будут объединены и массив не будет отсортирован.
Вот визуализация сортировки слиянием, чтобы прояснить для вас картину
Входной массив = [3,1,4,1,5,9,2,6,5,4]
Теперь перейдем к реализации.
какие функции в sql
Реализация сортировки слиянием в Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (правая половина) i = j = k = 0, а i Вывод:
$ python main.py
(«Разделение», [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(«Разделение», [3, 1, 4, 1, 5])
(«Разделение», [3, 1])
(«Разделение», [3])
(«Слияние», [3])
(«Разделение», [1])
(«Слияние», [1])
(«Слияние», [1, 3])
(«Разделение», [4, 1, 5])
(«Разделение», [4])
(«Слияние», [4])
(«Разделение», [1, 5])
(«Разделение», [1])
(«Слияние», [1])
(«Разделение», [5])
(«Слияние», [5])
(«Слияние», [1, 5])
(«Слияние», [1, 4, 5])
(«Слияние», [1, 1, 3, 4, 5])
(«Разделение», [9, 2, 6, 5, 4])
(«Разделение», [9, 2])
(«Разделение», [9])
(«Слияние», [9])
(«Разделение», [2])
(«Слияние», [2])
(«Слияние», [2, 9])
(«Разделение», [6, 5, 4])
(«Разделение», [6])
(«Слияние», [6])
(«Разделение», [5, 4])
(«Разделение», [5])
(«Слияние», [5])
(«Разделение», [4])
(«Слияние», [4])
(«Слияние», [4, 5])
(«Слияние», [4, 5, 6])
(«Слияние», [2, 4, 5, 6, 9])
(«Слияние», [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
преобразование двоичного в десятичное в Java
Блок-схема для реализации сортировки слиянием
Преимущества и использование сортировки слиянием
Большинство других алгоритмов плохо работают с последовательными структурами данных, такими как файлы и связанные списки. В этих структурах доступ к случайному элементу занимает линейное время, а не регулярное постоянное время. А природа сортировки слиянием делает ее простой и быстрой для таких структур данных.Одна из лучших особенностей сортировки слиянием - это небольшое количество сравнений. Он выполняет O (n * log (n)) количество сравнений, но постоянный коэффициент хорош по сравнению с быстрой сортировкой, что делает его полезным, когда функция сравнения является медленной операцией.Кроме того, подход сортировки слиянием по принципу «разделяй и властвуй» делает ее удобной для параллельной обработки.
На этом мы подошли к концу этого блога «Как реализовать сортировку слиянием в Python». Я надеюсь, что этот контент повысил ценность ваших знаний о Python. Чтобы получить более глубокие знания о Python и его различных приложениях, вы можете зарегистрироваться в режиме реального времени. с круглосуточной поддержкой и пожизненным доступом.