[Powered by Google Translate] [Zlúčiť Triediť] [Rob Bowden - Harvard University] [To je CS50. - CS50.TV] Poďme hovoriť o akejsi zlúčenie. Zatiaľ ste videli bubble sort, vloženie druhu, a výber radenie. Aj keď budem trochu vlny mojej ruky na to, čo tým myslím lepšie, zlúčiť druh všeobecne lepší ako niektorý z týchto 3 druhov. 

Ale skôr, než hovoriť o akejsi zlúčenie, poďme hovoriť o zlúčenie 2 triedené zoznamy. Zavoláme proces prijímania 2 triedené zoznamy, ako sú tieto, a robiť jeden zoradený zoznam z nich - zlúčenie zoznamov. Ako to môžeme urobiť? No, jeden nápad je len držať jeden zoznam na konci druhého zoznamu a potom triediť výsledný zoznam. 

Zatiaľ čo toto funguje, je to veľa zbytočnej práce. Môžeme to urobiť rýchlejšie, než len triedenie. Všimnite si, že jeden zlý nápad, je jednoducho vziať striedajúci poháre z každého zoznamu. Aj keď to môže vyzerať ako to funguje na prvý, robí, že sme skončili s 4, 8, 15, 23, 16 - oznámenie, že 16 a 23 sú z miesta. To je preto, že 2 prvky, ktoré by mali byť uvedené za sebou v zlúčenej zoznamu sú v rovnakej pôvodného zoznamu. Obaja 15 a 16 sú v zozname na ľavej strane. Trik je využiť skutočnosť, že oba zoznamy sú už zoradené. To znamená, že ak sa len pozrieť na prvé prvky oboch zoznamov - tu, 4 a 8 - musí byť jeden z nich byť aj prvý prvok zlúčeného zoznamu. No, prečo to je? Oba tieto zoznamy sú už zoradené, a tak buď 4 alebo 8, musí byť najmenší prvok, keď spojíme 2 zoznamy. V tomto prípade, najmenší je 4, takže môžeme vziať von 4 a robiť to prvý prvok našej zlúčené zoznamu. Teraz budeme pokračovať zlúčenie zvyšné 3 prvky prvého zoznamu a 4 prvky druhého zoznamu. 

Opäť sme Stačí sa pozrieť na prvý prvok oboch zoznamov. Menší z 2 musí byť druhý prvok našej zlúčené zoznamu. Tentoraz medzi 8 a 15 najmenších je 8, a tak sme sa vložiť, aby ako druhý prvok nášho triedeného zoznamu. Môžeme pokračovať v porovnaní prvých prvky oboch zoznamov a odstránenie menšie z 2. Porovnanie 15 a 23, 15 je menšie, a tak to je naša tretia element. Teraz porovnaní 16 a 23, 16, je menšia. Tak to je štvrtý element. 

Všimnite si, že 2 prvky pochádzajú z rovnakého zoznamu v rade. To je dôvod, prečo by nový zoznam nemôže len striedajú prvky od 2 zoznamov. Porovnanie 50 a 23, 23 je menší, tak sme sa rozhodli, že. Medzi 50 a 42, 42 je menší. Medzi 50 a 108, 50 je menší. A konečne, musíme len 108, tak to musí ísť na konci nášho zoznamu. Všimnite si, že máme pekný, zoradený zoznam. Zakaždým, keď sme porovnali prvé 2 prvky 2 zoznamov sme boli schopní určiť ďalší prvok zlúčeného zoznamu. To znamená, že v prípade, že konečný zoznam obsahuje n čísla, kde n je tu 8, potom musíme na väčšine n porovnaní dostať všetky z týchto čísel na správne miesto. Takýto algoritmus je povedal, aby spustenie v lineárnom čase, ale nebojte sa o tom tu. 

Pomocou nášho algoritmu pre zlučovanie, môžeme urobiť rýchly zlúčenie radenie algoritmus. Takže, poďme obnoviť naše zoznamy. K dispozícii sú 2 veľké kroky v procese druhu korešpondencie. Po prvé, neustále rozdelí zoznam šálok do polovice kým nebudeme mať veľa zoznamov iba s 1 šálkou v nich. Nebojte sa, ak zoznam obsahuje nepárny počet a nemôžete urobiť dokonale čistý rez medzi nimi. Len ľubovoľne vybrať, ktorú Zoznam zahrnúť ďalšie šálku dovnútra Takže, poďme rozdeliť tieto zoznamy. Teraz máme 2 zoznamy. Teraz máme 4 zoznamy. 

A teraz máme 8 zoznamov s jedným šálkou v každom zozname. Tak to je to v 1. kroku. Pre kroku 2, sme opakovane spojí dva zoznamy algoritmom zlúčenie sme sa naučili predtým. Zlúčenie 108 a 15, skončíme s prehľadom 15, 108. Zlúčenie 50 a 4, skončíme s 4, 50. Zlúčenie 8 a 42, skončíme s 8, 42. A zlúčenie 23 a 16, skončíme s 16, 23. Teraz sú všetky naše zoznamy sú veľkosti 2. Všimnite si, že každý z 4 zoznamoch zoradené. 

Takže môžeme začať zlúčením dvojice zoznamov znova. Zlúčenie 15 a 108 a 4 a 50 - prvý prijať 4, potom 15, potom 50, potom 108. Zlúčenie 8, 42 a 16, 23, najprv sa 8, potom 16, potom 23, potom 42. Takže teraz máme len 2 zoznamy veľkosti 4, je zoradená z ktorých každý. Takže teraz sme zlúčiť tieto 2 zoznamy. Najprv sme sa na 4. Potom budeme mať 8. Potom budeme mať 15 a 16, potom 23, potom 42, potom 50, potom 108. A sme hotoví. Teraz máme zoradený zoznam. Tak, ako rýchlo to bolo presne? Z technického hľadiska, zlúčenie sort je O (n log n), vzhľadom k tomu, všetky bubliny druhu, vloženie zoradiť, a výber druhu sú O (n ²). V skutočnosti, ako budete čoskoro naučí, nebudete schopní prísť s akýmsi že sú lepšie ako O (n log n) vo všeobecnom prípade. Opäť, nebojte sa o tejto veľkej O notácie, ak ste ho ešte nevideli ešte. 

Len viem, že to znamená, že ak by sme chceli usporiadať naozaj veľký zoznam bublina sort, vloženie sort, a výber sort by mohol mať podstatne dlhšie než zlúčenie radenie. To neznamená, že zlúčenie triedenie bude rýchlejší pre všetky zoznamy alebo dokonca pre každú jednotlivú zoznamu pod určitej veľkosti. Napríklad, môže vloženie druh najrýchlejší radenia pre všetkých zoznamov menšie ako 5 prvkov. V praxi, zlúčenie druh je zvyčajne rýchlejší zoznamy ako malý ako 50 prvkov. 

Ale to navyše rýchlosť nepríde bez ceny. Na rozdiel od našich ostatných druhov, ktoré sa v zozname a upraviť zoznam v mieste kým nebudeme mať usporiadaný zoznam, merge sort potrebuje ďalšie miesto zlúčiť 2 zoznamy dohromady. Nemôžeme ihneď používať zoznamy, ktoré sú zlúčené uložiť zlúčený zoznam pretože by sme mohli prepísať prvky, ktoré ešte potrebujú byť zlúčené. Tento priestor je trochu cenu, ale to zvyčajne nie je neprimerané. A to je pre druh korešpondencie. 

Moje meno je Rob Bowden, a to je CS50. [CS50.TV] - A výber druhu. [Smiech] Oh, musím vziať, že príliš, pretože som prešiel, ako som bol, že ho predstavuje. Zoznamu na ľavej strane. To bol preklep. [Misspoke] I podelal - [Smiech] Ja neviem, čo -