Този блог се основава на подхода „разделяй и владей“. Merge Sort е алгоритъм „разделяй и владей“, при който проблемът е разделен на подпроблеми и след това се обединява, за да завладее решението. Този блог в Merge Sort in ще ви преведе подробно през долните теми -
- Какво е Merge Sort в Python?
- Подходът „Разделяй и владей“
- Внедряване на Merge Sort в Python
- Блок-схема за внедряване на Merge Sort
- Предимства и употреба
Какво е Merge Sort в Python?
Merge Sort се основава на алгоритъма за разделяне и завладяване, където входният масив е разделен на две половини, след това сортиран поотделно и обединен обратно, за да достигне до решението. Функцията merge () се използва за обединяване на сортираното .
Подходът „Разделяй и владей“
- Масивът се разделя наполовина и процесът се повтаря с всяка половина, докато всяка половина е с размер 1 или 0.
- Масивът с размер 1 е тривиално сортиран.
- Сега двата сортирани масива се комбинират в един голям масив. И това продължава, докато всички елементи се комбинират и масивът се сортира.
Ето визуализация на сортиране на сливане, за да изчистите картината вместо вас
Входен масив = [3,1,4,1,5,9,2,6,5,4]
предпоставки за научаване на машинно обучение
Сега да преминем към изпълнението.
Внедряване на Merge Sort в 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]
пример за извикване на отдалечен методБлок-схема за прилагане на Сливане на сортиране
Предимства и използване на сортиране на обединяване
Повечето от другите алгоритми се представят лошо с последователни структури от данни като файлове и свързани списъци. В тези структури достъпът до случаен елемент отнема линейно време, а не редовно постоянно време. А естеството на сортирането на сливанията го прави лесно и бързо за такива структури от данни.Една от най-добрите характеристики на сортирането на сливанията е неговият малък брой сравнения. Това прави O (n * log (n)) брой сравнения, но постоянният коефициент е добър в сравнение с бързата сортировка, което го прави полезен, когато функцията за сравнение е бавна операция.Също така подходът „разделяй и владей“ при сортиране на сливания го прави удобен за паралелна обработка.
С това стигнахме до края на този блог на тема „Как да приложим Merge Sort в Python“. Надявам се, че съдържанието добави някаква стойност към вашите познания в Python. За да получите задълбочени познания за Python заедно с различните му приложения, можете да се регистрирате за живо с 24/7 поддръжка и доживотен достъп.