[Powered by Google Translate] [Zlivanjem] [Rob Bowden - Harvard University] [To je CS50. - CS50.TV] Pogovorimo se o datumu spajanja. Do sedaj ste videli mehurček razvrščanje, razvrščanje in vstavljanje izbiro vrste. Čeprav bom nekako val mojo roko na kaj mislim s bolje, združiti sortiranje na splošno opravlja bolje kot kateri koli od teh 3 vrst. 

Toda preden govorimo o neke spajanja, kaj je govoril o združitvi 2 razvrščena seznamov. Poklicali bomo proces sprejemanja 2 razvrščena seznamov, kot so te, in kar sam urejen seznam iz njih - združitev seznamov. Kako lahko to storimo? No, ena ideja je, da ostanemo en seznam na koncu drugega seznama nato pa razvrstite izhaja seznam. 

Medtem ko ta deluje, je veliko nepotrebnega dela. Mi lahko to storite hitreje kot le usmerjanje. Obvestilo, da ena napačna ideja je, da vzemite izmenično skodelic iz vsakega seznama. Čeprav se lahko zdi, da deluje na prvi pogled, tem, da smo na koncu s 4, 8, 15, 23, 16 - obvestilo, da 16 in 23 so na pravem mestu. To je zato, ker 2 elementi, ki se navedejo zaporedno v združenega seznama v istem prvotnega seznama. Oba 15 in 16 so na seznamu na levi strani. Trik je v tem, da izkoristijo dejstvo, da se oba seznama že sortirane. To pomeni, da če bomo le pogled na prvih elementov obeh seznamov - Tukaj, 4 in 8 - mora biti eden izmed njih je tudi prvi element novega seznama. Torej, zakaj je to? Oba od teh seznamov so že razporejene, in zato morajo bodisi 4 ali 8 je najmanjši element, ko združimo 2 seznamov. V tem primeru je najmanjša 4, da bomo lahko ven 4 in da je prvi element našega novega seznama. Zdaj bomo še naprej združuje preostale 3 dele prvega seznama in 4 elementi drugem seznamu. 

Še enkrat, potrebujemo le, da pogled na prvi element obeh seznamov. Manjše od 2 mora biti drugi element našega novega seznama. Tokrat je med 8 in 15 najmanjših je 8, zato smo vstaviti, da kot drugi element našega razvrščene seznama. Lahko nadaljujemo primerjavo prve elemente obeh seznamih in odpravo manjši od 2. Primerjava 15 in 23, 15, je manjša in da je naš tretji element. Zdaj primerjavo 16 in 23, 16, je manjša. Torej, to je četrti element. 

Obvestilo, da 2 elementi izvirajo iz istega seznama zapored. To je razlog, zakaj združeni seznam ne more samo nadomestne elemente iz 2 seznamov. Primerjava 50 in 23, 23, je manjša, zato smo se odločili, da. Med 50 in 42, 42, je manjša. Med 50 in 108, 50 pa je manjša. In končno, imamo samo 108, tako da mora iti na koncu našega seznama. Obvestilo, da imamo lepo, razvrščen seznam. Vsakič, ko smo primerjali 1. 2 elemente 2 seznamov smo lahko določili naslednji element združenega seznama. To pomeni, da če je končni seznam vsebuje n številk, pri čemer je n tukaj je 8, potem moramo v večini n primerjav, da bi dobili vse te številke na pravem mestu. Tak algoritem je dejal, da deluje v linearnem času, vendar ne skrbite o tem tukaj. 

Z uporabo našega algoritma za združitev, lahko naredimo hiter razvrščanja algoritem za spajanje. Torej, kaj je prikrivati ​​svoje sezname. Obstajata 2 velik korak v procesu vrste spajanja. Prvič, ves čas po delih seznam skodelic na polovici dokler ne bomo imeli kup seznamov s samo 1 skodelico v njih. Ne skrbite, če seznam vsebuje liho število in ne moreš narediti popolnoma čisti rez med njimi. Samo samovoljno izbirati, katere seznam vključiti dodatno skodelico noter Torej, kaj je razdeljen teh seznamov. Zdaj imamo 2 seznamov. Zdaj imamo 4 seznamov. 

In zdaj imamo 8 sezname z eno skodelico na vsakega seznama. Tako da je za 1. koraku. Za 2. koraku, smo večkrat združi pare seznamov s pomočjo algoritma za spajanje smo se naučili prej. Združitev 108 in 15, smo na koncu s seznama 15, 108. Združitev 50 in 4, smo na koncu s 4, 50. Združitev 8 in 42, smo na koncu z 8, 42. In združuje 23 in 16, smo na koncu z 16, 23. Zdaj so vsi naši seznami velikosti 2. Obvestilo, da je razvrščena vsaka od 4 seznamov. 

Torej, lahko začnemo združuje parov seznamov znova. Združitev 15 in 108 ter 4 in 50 - 1. sprejme 4, nato 15, nato 50, nato 108. Združitev 8, 42 in 16, 23, najprej sprejme 8, nato 16, nato 23, nato 42. Torej, zdaj imamo samo 2 seznamov velikosti 4, so razvrščeni od katerih vsaka. Zdaj smo združiti teh 2 seznamov. Najprej vzamemo 4. Nato vzamemo 8. Nato vzamemo 15 in 16, nato 23, nato 42, nato 50, nato 108. In končamo. Zdaj imamo urejen seznam. Torej, kako hitro je to točno? V tehničnem smislu zlivanjem je O (n log n) ker vse vrste mehurčkov, vstavljanja vrste in izbor razvrstite so O (n ²). V bistvu, kot boste izvedeli kmalu ne boste mogli prišli do neke ki opravlja bolje kot O (n log n) V splošnem primeru. Še enkrat, ne skrbi, ta velik zapis o Če še niste videli. 

Samo vem, da to pomeni, da če bi želeli rešiti res velik seznam bubble sort, vstavljanje sortiranje, izbira sort, lahko potencialno lahko bistveno daljši od zlivanjem. To ne pomeni, da bo z zlivanjem hitrejši za vse sezname ali celo za posamezno seznamu pod določeno velikostjo. Na primer, vključitev neke vrste bil najhitrejši na vseh seznamih, manjših od 5 elementov. V praksi zlivanjem je ponavadi hitrejši za sezname kot majhne kot 50 elementov. 

Vendar pa to dodatno hitrost ne prihaja brez ceno. Za razliko od naših drugih vrst, ki sprejme seznam in spremeni seznam na mestu dokler ne bomo dobili urejen seznam, zlivanjem potrebuje nekaj dodatnega prostora združiti 2 seznamov skupaj. Mi ne more takoj uporabi sezname, ki se združila za shranjevanje združeno seznam saj bomo morda prednost elemente, ki jih je še treba združiti. Ta prostor je malo ceni, vendar običajno ni nerazumna. In to je to za razvrščanje spajanja. 

Moje ime je Rob Bowden, in to je CS50. [CS50.TV] - Izbor in razvrščanje. [Smeh] Oh, moram vzeti ven, da tudi zato, ker sem zamenjal, kako sem jo predstavlja. Seznam na levi strani. To je bila tipkarska napaka. [Misspoke] sem zamočil - [Smeh] Ne vem kaj -