Acest blog se bazează pe abordarea divizării și cuceririi. Merge Sort este un algoritm de „împărțire și cucerire” în care problema este împărțită în subprobleme și apoi este fuzionată pentru a cuceri soluția. Acest blog pe Merge Sortează în vă va conduce în detaliu subiectele de mai jos -
- Ce este Merge Sort în Python?
- Abordarea Divide and Conquer
- Implementarea sortării Merge în Python
- Organigramă pentru implementarea sortării Merge
- Avantaje și utilizare
Ce este Merge Sort în Python?
Merge Sort se bazează pe algoritmul de divizare și cucerire în care matricea de intrare este împărțită în două jumătăți, apoi sortată separat și fuzionată înapoi pentru a ajunge la soluție. Funcția merge () este utilizată pentru îmbinarea sortatelor .
Abordarea Divide and Conquer
- Matricea este împărțită în jumătate și procesul se repetă cu fiecare jumătate până când fiecare jumătate are dimensiunea 1 sau 0.
- Matricea de mărimea 1 este sortată în mod banal.
- Acum cele două matrice sortate sunt combinate într-o matrice mare. Și acest lucru este continuat până când toate elementele sunt combinate și matricea este sortată.
Iată o vizualizare a sortării de îmbinare pentru a șterge imaginea pentru dvs.
Matrice de intrare = [3,1,4,1,5,9,2,6,5,4]
php convertește matricea în obiect
Acum, să trecem la implementare.
Implementarea sortării Merge în Python
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (half left) mergeSort (jumătatea dreaptă) i = j = k = 0 în timp ce i Ieșire:
$ python main.py
(„Împărțirea”, [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
(„Împărțirea”, [3, 1, 4, 1, 5])
(„Împărțirea”, [3, 1])
(„Împărțirea”, [3])
(„Fuziune”, [3])
(„Împărțirea”, [1])
(„Fuziune”, [1])
(„Fuzionarea”, [1, 3])
(„Împărțirea”, [4, 1, 5])
(„Împărțirea”, [4])
(„Fuziune”, [4])
(„Împărțirea”, [1, 5])
(„Împărțirea”, [1])
(„Fuziune”, [1])
(„Împărțirea”, [5])
(„Fuziune”, [5])
(„Fuzionarea”, [1, 5])
(„Fuzionarea”, [1, 4, 5])
(„Fuziune”, [1, 1, 3, 4, 5])
(„Împărțirea”, [9, 2, 6, 5, 4])
(„Împărțirea”, [9, 2])
(„Împărțirea”, [9])
(„Fuziune”, [9])
(„Împărțirea”, [2])
(„Fuziune”, [2])
(„Fuziune”, [2, 9])
(„Împărțirea”, [6, 5, 4])
(„Împărțirea”, [6])
(„Fuziune”, [6])
(„Împărțirea”, [5, 4])
(„Împărțirea”, [5])
(„Fuziune”, [5])
(„Împărțirea”, [4])
(„Fuziune”, [4])
(„Fuziune”, [4, 5])
(„Fuziune”, [4, 5, 6])
(„Fuziune”, [2, 4, 5, 6, 9])
(„Fuziune”, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
care sunt cele 6 moduri de a utiliza acest cuvânt cheie?
Diagramă pentru implementarea sortării Merge
Avantajele și utilizarea sortării Merge
Majoritatea celorlalți algoritmi funcționează prost cu structuri de date secvențiale, cum ar fi fișiere și liste legate. În aceste structuri accesarea unui element aleatoriu necesită timp liniar, nu timp constant constant. Și natura sortării de îmbinare o face ușoară și rapidă pentru astfel de structuri de date.Una dintre cele mai bune caracteristici ale sortării de îmbinare este numărul său redus de comparații. Face O (n * log (n)) numărul de comparații, dar factorul constant este bun în comparație cu quicksort, ceea ce îl face util atunci când funcția de comparare este o operație lentă.De asemenea, abordarea de divizare și cucerire a sortării fuziunii o face convenabilă pentru procesarea paralelă.
Cu aceasta, ajungem la sfârșitul acestui blog despre „Cum să implementăm Sortare Merge în Python”. Sper că conținutul a adăugat o oarecare valoare cunoștințelor dvs. în Python. Pentru a obține cunoștințe aprofundate despre Python împreună cu diferitele sale aplicații, vă puteți înscrie pentru live cu suport 24/7 și acces pe viață.