Ta spletni dnevnik temelji na pristopu deli in vladaj. Merge Sort je algoritem 'deli in osvoji', pri katerem je problem razdeljen na podprobleme in nato združen, da osvoji rešitev. Ta spletni dnevnik o spajanju Razvrsti v vas bo podrobno vodil skozi spodnje teme -
- Kaj je razvrščanje med spajanjem v Pythonu?
- Pristop Divide and Conquer
- Izvajanje sortiranja spajanja v Pythonu
- Diagram poteka za izvedbo razvrščanja med spajanjem
- Prednosti in uporaba
Kaj je razvrščanje med spajanjem v Pythonu?
Razvrščanje po združitvi temelji na algoritmu deli in vladaj, kjer je vhodno polje razdeljeno na dve polovici, nato razvrščeno ločeno in združeno nazaj, da pride do rešitve. Funkcija merge () se uporablja za spajanje razvrščenih .
Pristop Divide and Conquer
- Niz se razdeli na polovico in postopek se ponovi z vsako polovico, dokler ni vsaka polovica velikosti 1 ali 0.
- Niz velikosti 1 je trivialno razvrščen.
- Zdaj sta razvrščena polja združena v en velik niz. In to nadaljuje, dokler se vsi elementi ne kombinirajo in matrika ne razvrsti.
Tukaj je vizualizacija združevanja, da vam pokaže sliko
najboljši java ide za ubuntu
Vhodno polje = [3,1,4,1,5,9,2,6,5,4]
Zdaj pa pojdimo k izvedbi.
Izvajanje sortiranja spajanja v Pythonu
def mergeSort (nlist): print ('Splitting', nlist) if len (nlist)> 1: mid = len (nlist) // 2 lefthalf = nlist [: mid] righthalf = nlist [mid:] mergeSort (lefthalf) mergeSort (desno) i = j = k = 0, medtem ko i Izhod:
$ python main.py
('Razdelitev', [3, 1, 4, 1, 5, 9, 2, 6, 5, 4])
('Razdelitev', [3, 1, 4, 1, 5])
(„Razdelitev“, [3, 1])
(„Razdelitev“, [3])
(„Združevanje“, [3])
(„Razdelitev“, [1])
(„Združevanje“, [1])
(„Združevanje“, [1, 3])
(„Razdelitev“, [4, 1, 5])
(„Razdelitev“, [4])
(„Združevanje“, [4])
(„Razdelitev“, [1, 5])
(„Razdelitev“, [1])
(„Združevanje“, [1])
(„Razdelitev“, [5])
(„Združevanje“, [5])
(„Združevanje“, [1, 5])
(„Združevanje“, [1, 4, 5])
(„Združevanje“, [1, 1, 3, 4, 5])
('Razdelitev', [9, 2, 6, 5, 4])
(„Razdelitev“, [9, 2])
(„Razdelitev“, [9])
(„Združevanje“, [9])
(„Razdelitev“, [2])
(„Združevanje“, [2])
(„Združevanje“, [2, 9])
(„Razdelitev“, [6, 5, 4])
(„Razdelitev“, [6])
(„Združevanje“, [6])
(„Razdelitev“, [5, 4])
(„Razdelitev“, [5])
(„Združevanje“, [5])
(„Razdelitev“, [4])
(„Združevanje“, [4])
(„Združevanje“, [4, 5])
(„Združevanje“, [4, 5, 6])
(„Združevanje“, [2, 4, 5, 6, 9])
(„Združevanje“, [1, 1, 2, 3, 4, 4, 5, 5, 6, 9])
[1, 1, 2, 3, 4, 4, 5, 5, 6, 9]
faktorijel številke java
Diagram poteka za izvedbo razvrščanja med spajanjem
Prednosti in uporaba sortiranja spajanja
Večina drugih algoritmov deluje slabo z zaporednimi podatkovnimi strukturami, kot so datoteke in povezani seznami. V teh strukturah dostop do naključnega elementa traja linearni čas in ne reden konstanten čas. Narava vrste spajanja olajša in hitro omogoči takšne podatkovne strukture.Ena najboljših lastnosti razvrščanja med spajanjem je majhno število primerjav. Omogoča O (n * log (n)) število primerjav, vendar je konstantni faktor v primerjavi s hitrim sortiranjem dober, kar je koristno, če je funkcija primerjave počasno delovanje.Poleg tega je pristop razdeli in osvoji osredotoči razvrščanje, zato je primeren za vzporedno obdelavo.
S tem smo prišli do konca tega spletnega dnevnika o tem, kako v Pythonu implementirati razvrščanje med spajanjem. Upam, da je vsebina dodala nekaj vrednosti vašemu znanju v Pythonu. Če želite pridobiti poglobljeno znanje o Pythonu skupaj z različnimi aplikacijami, se lahko prijavite v živo s 24-urno podporo in življenjskim dostopom.