[Powered by Google Translate] [Merge Rūšiuoti] [Rob Bowden - Harvardo universiteto] [Tai CS50. - CS50.TV] Pakalbėkime apie Merge sort. Iki šiol jūs matėte bubble rūšiuoti, įterpimo rūšiuoti, ir pasirinkimo rūšiuoti. Nors aš tipo bangos mano ranka, ką reiškia geriau, sujungti rūšiuoti paprastai veikia geriau nei bet kuris iš šių 3 rūšių. 

Bet prieš pradedant kalbėti apie sujungti rūšiuoti, pakalbėkime apie sujungti 2 surūšiuoti sąrašus. Mes paskambinsime atsižvelgiant 2 surūšiuoti sąrašus, kaip šie, ir padaryti vieną surūšiuoti sąrašą iš jų - sujungti sąrašus. Kaip mes galime tai padaryti? Na, viena idėja yra tiesiog klijuoti vieną sąrašą ant kito sąrašo pabaigoje ir tada rūšiuoti gautą sąrašą. 

Nors tai veikia, tai daug nereikalingo darbo. Mes galime padaryti tai greičiau ne tik rūšiavimo. Atkreipkite dėmesį, kad vienas neteisingas idėja yra tiesiog pakaitomis puodeliai iš kiekvieno sąrašo. Nors tai gali atrodyti, kad darbų, pirmiausia, tai, kad mes galų gale su 4, 8, 15, 23, 16 - Pranešimas, kad 16 ir 23 vietos. Taip yra todėl, 2 elementai, kad turėtų būti įtrauktos eilės susijungusio sąraše yra to paties pradinio sąrašą. Tiek 15 ir 16 sąrašo kairėje. Apgaulė yra pasinaudoti dėl to, kad abu sąrašai jau rūšiuotų. Tai reiškia, kad, jei mes tiesiog pažvelgti į abiejų sąrašų pirmųjų elementų - čia, 4 ir 8 - vienas iš jų taip pat turi būti susijungusio sąrašo pirmas elementas. Na, kodėl taip yra? Abi iš šių sąrašų jau rūšiuojamos, ir taip, bet 4 ar 8 turi būti mažiausias elementas, kai mes sujungti 2 sąrašus. Šiuo atveju, mažiausias yra 4, todėl mes galime imti 4 ir padaryti tai pirmasis elementas mūsų susijungusios sąrašą. Dabar mes ir toliau likusias 3 pirmojo sąrašo elementų sujungimą ir 4 elementai Antrame sąraše. 

Dar kartą, mes tik reikia pažvelgti į pirmojo elemento abiejų sąrašų. Su 2 turi būti mažesnis Antrasis elementas mūsų susijungusios sąrašą. Šį kartą, tarp 8 ir 15 mažiausias 8, ir todėl mes įterpti, kad kaip antrasis elementas mūsų rūšiuotų sąrašą. Mes galime tęsti lyginant abiejų sąrašų pirmųjų elementų ir pašalinti mažesnis iš 2. Lyginant 15 ir 23, 15, yra mažesnis ir kad mūsų Trečiasis elementas. Dabar lyginant 16 ir 23, 16, yra mažesnis. , Kad Ketvirtasis elementas. 

Atkreipkite dėmesį, kad 2 elementai iš eilės atėjo iš to paties sąrašo. Tai, kodėl susijungusi sąrašas gali ne tik pakaitiniai elementai iš 2 išvardijamos. Lyginant 50 ir 23, 23, yra mažesnis, todėl mes pasirinkti, kad. Tarp 50 ir 42, 42 yra mažesnė. Nuo 50 iki 108, 50 yra mažesnė. Ir, pagaliau, mes tiesiog turime 108, todėl turi eiti mūsų sąrašo pabaigoje. Atkreipkite dėmesį, kad mes gražus, surūšiuotas sąrašą. Kiekvieną kartą, kai mes palyginti pirmąsias 2 iš 2 sąrašų elementus mes galėjome nustatyti kito elemento susijungusio sąrašą. Tai reiškia, kad jei galutinis sąrašas yra n, kur n - čia yra 8, tada mes turime ne daugiau kaip n palyginimų gauti visų tų skaičių į reikiamą vietą. Toks algoritmas yra sakoma, kad paleisti į linijinės metu, bet nesijaudinkite apie tai čia. 

Naudojant mūsų algoritmas sujungti, mes galime padaryti greitai sujungti rūšiavimo algoritmą. Taigi, galime iš naujo mūsų sąrašuose. Merge sort proceso Yra 2 dideli žingsniai. Pirma, nuolat į dvi dalis padalinti puodelių sąrašą kol mes sąrašų krūva tik su 1 puodelis jais. Nesijaudinkite, jei sąraše yra nelyginis skaičius ir jūs negalite padaryti visiškai nupjauti tarp jų. Tiesiog savavališkai pasiimti, kurių sąrašas įtraukti papildomos puodelio in Taigi, galime padalinti šiuos sąrašus. Dabar mes turime 2 sąrašus. Dabar mes turime 4 sąrašus. 

Ir dabar mes turime 8 sąrašus su vienu puodelio kiekvieno sąrašo. Taip, kad jį atlikdami 1 veiksmą. 2 žingsnyje, mes pakartotinai sujungti poros suliejimo algoritmas mes sužinojome prieš naudojant sąrašų. Sujungimas 108 ir 15, mes galų gale su sąraše 15, 108. Sujungimas 50 ir 4, mes galų gale su 4, 50. Sujungimas 8 ir 42, baigti su 8, 42. Ir sujungti 23 ir 16, mes galų gale su 16, 23. Dabar visi mūsų sąrašai dydis 2. Atkreipkite dėmesį, kad kiekvienas iš 4 sąrašų yra rūšiuojamos. 

Taigi, mes galime pradėti vėl sujungti poros sąrašų. Sujungimas 15 ir 108 ir 4 ir 50 - pirmiausia reikia 4, tada 15, tada 50, tada 108. Sujungimas 8, 42 ir 16, 23, mes pirmą kartą 8, tada 16, tada 23, tada 42. Taigi dabar mes turime tik 2 sąrašus dydis 4, iš kurių kiekviena yra rūšiuojama. Taigi dabar mes sujungti šias 2 sąrašus. Pirmiausia mes 4. Tada mes 8. Tada mes 15 ir 16, tada 23, tada 42, tada 50, tada 108. Ir baigsime. Dabar mes turime surūšiuoti sąrašą. Taigi, kaip greitai buvo tai, tiksliai? Techniniu požiūriu, sujungti rūšiuoti yra O (n log n), kadangi visos burbulas rūšiuoti, įterpimo rūšiuoti ir atrankos rūšiuoti yra O (n ²). Iš tikrųjų, kaip jūs išmoksite greičiau, jums nebus galės sugalvoti rūšiuoti kad veikia geriau nei O (n log n) bendruoju atveju. Vėlgi, nereikia nerimauti tai didelis O notacijos, jei jūs dar nematėte, tai dar. 

Tiesiog žinau, kad tai reiškia, kad, jei norime rūšiuoti tikrai didelis sąrašą burbulas rūšiuoti, įterpimas rūšiuoti ir atranka Rūšiuoti potencialiai gali imtis daug ilgiau, nei sujungti rūšiuoti. Tai nereiškia, kad sujungti tarsi bus greitesnis visų sąrašų ar net nė vieno tam tikro dydžio sąrašą. Įterpimo rūšiuoti, pavyzdžiui, gali būti greičiausias rūšiuoti visų sąrašus mažesnėse kaip 5 elementai. Praktikoje dažniausiai yra greitesnis, sujungti rūšiuoti sąrašų, kaip mažas kaip 50 elementų. 

Tačiau šis papildomas greitis būtų ne be kainos. Skirtingai nuo mūsų kitų rūšių sąrašą ir keisti sąrašo vietoje kol mes gauti surūšiuoti sąrašą, sujungti rūšiuoti reikia šiek tiek papildomos erdvės sujungti 2 sąrašus kartu. Mes negalime iš karto naudoti sąrašus, kurie yra sujungtos laikyti susijungęs sąrašą nes mes gali panaikinti elementus, kurie vis dar turės būti sujungti. Ši erdvė yra tokia kaina, šiek tiek, tačiau ji paprastai nėra nepagrįsta. Ir štai Merge sort. 

My name is Rob Bowden, ir tai yra CS50. [CS50.TV] Ir atranka rūšiuoti. [Juokiasi] Oh, turite imtis, kad per daug, nes aš perėjo, kaip aš buvo pristatyti. Sąrašas kairėje. Kad buvo klaidos. [Misspoke] Aš įsukus [Juokiasi] Aš nežinau, ką -