[Powered by Google Translate] [Merge Sort] [Rob Bowden - Harvard University] [Ez CS50. - CS50.TV] Beszéljünk merge sort. Eddig láttad buborék rendezés, beszúrásos rendezés, és a kiválasztás sort. Bár Majd egyfajta hullám kezem, mit gondolok a jobb, merge sort általában jobban teljesít, mint bármelyik a 3 fajta. 

De mielőtt beszélünk merge sort, beszéljünk egyesülő 2 rendezett listákat. Hívjuk a folyamat figyelembe 2 rendezett listákat, mint ezek, és így egy rendezett listát ki őket - összevonása a listák. Hogyan tudjuk ezt megtenni? Nos, az egyik cél az, hogy csak kibír egy lista rá a végén a másik lista sort, majd a kapott listát. 

Bár ez működik, ez egy csomó felesleges munka. Meg tudjuk csinálni gyorsabban, mint válogatás. Figyeljük meg, hogy egy rossz ötlet, hogy csak úgy váltakozó kupák minden listáról. Bár ez tűnhet, hogy a munkálatok az első, ezzel, hogy a végén a 4, 8, 15, 23, 16 - nyilatkozat, hogy 16 és 23 van a helyén. Ennek az az oka, hogy a 2 elem jelenjen meg egymás után az egyesített listán ugyanabban az eredeti listában. Mind a 15 és 16 van a listán a bal oldalon. A trükk az, hogy kihasználja azt a tényt, hogy mindkét lista már rendezve. Ez azt jelenti, hogy ha csak nézd meg az első elemeit egyaránt listák - Itt, 4 és 8 - egyikük is kell az első eleme az új lista. Nos, miért van ez? Mindkét listák már rendezve, és így 4 vagy 8 kell, hogy legyen a legkisebb elem, ha kombináljuk a 2 lista. Ebben az esetben, a legkisebb a 4, így tudjuk kivenni 4, és ez az első eleme egyesített listán. Most tovább egyesülő fennmaradó 3 elem az első lista és 4 elemeit a második listán. 

Még egyszer, csak meg kell nézni az első elemet mindkét listát. Minél kisebb a 2 kell, hogy legyen a második eleme egyesített listán. Ez alkalommal, 8 és 15 a legkisebb 8, és így be az a második eleme a rendezett lista. Mi továbbra is összehasonlítjuk az első elemeit egyaránt listák és eltávolítása a kisebb a 2. Összehasonlítása 15. és 23, 15 kisebb, és annak érdekében, hogy azon a harmadik elem. Most összehasonlítása 16. és 23., a 16 kisebb. Szóval ez a negyedik elem. 

Figyeljük meg, hogy 2 elem származik az ugyanazon a listán a sorban. Ezért az összefonódással lista nem csupán alternatív elemeket a 2 listákból. Összehasonlítva 50 és 23, 23 kisebb, ezért úgy döntünk, hogy. 50 és 42, 42 kisebb. Az 50 és 108, 50 kisebb. És végül már csak 108, így kell menni a végén a mi listáját. Figyeljük meg, hogy van egy szép, rendezett listát. Minden alkalommal, amikor összehasonlítottuk az első 2 elem a 2 listák tudtuk meghatározni a következő eleme az új lista. Ez azt jelenti, hogy amennyiben a végleges lista n szám, ahol n itt 8, akkor meg kell legfeljebb n összehasonlítást, hogy az összes ilyen számokat a megfelelő helyre. Egy ilyen algoritmus azt mondta, hogy fut a lineáris idő, de ne aggódj, hogy itt. 

Használd az algoritmus egyesülő, tudjuk, hogy egy gyors merge rendezési algoritmus. Nos, nézzük vissza a listákat. Van 2 nagy lépés a folyamat merge sort. Először is, folyamatosan szét a listáját cups figyelembe félidőt amíg van egy csomó listák csak 1 csésze őket. Ne aggódjon, ha a lista tartalmazza a páratlan számú és nem lehet, hogy egy teljesen tiszta vágás között. Csak önkényesen válasszon, amely lista tartalmazza az extra pohár be Szóval, most szét ezeket a listákat. Most van 2 listákat. Most már 4 listákat. 

És most már 8 listák egy csésze mindegyik listán. Szóval ez azt az 1. lépést. A 2. lépésben, akkor ismételten egyesítése pár listák segítségével az egyesítés algoritmus tudtuk korábban. Egyesítése 108 és 15, akkor a végén a listát 15, 108. Összevonása 50 és 4, a végén 4, 50. Egyesítése 8 és 42, a végén 8, 42. És egyesülő 23 és 16, a végén 16, 23. Most minden a mi listák a 2-es méret. Figyeljük meg, hogy mind a 4 listák rendezve. 

Így tudjuk kezdeni egyesülő pár listák újra. Összevonása 15. és a 108. és 4 és 50 - előbb a 4, akkor a 15, majd a 50, majd a 108. Összevonása 8, 42 és 16, 23, mi előbb a 8, akkor a 16, majd a 23, majd a 42. Így most már csak 2 listák 4 nagyság, amelyek mindegyike rendezve. Tehát most már eleget a 2 listákat. Először vegyük a 4. Akkor tegye meg a 8. Akkor vesszük a 15 és 16, majd 23, majd 42, majd 50, majd 108. És mi történt. Most már van egy rendezett listát. Szóval, milyen gyors volt ez pontosan? Műszaki szempontból egyesítés rendezés O (n log n), mivel az összes buborék rendezés, beszúrásos rendezés, és a kiválasztási sort az O (n ²). Valójában, ahogy megtudhatja hamarosan, akkor nem fogja tudni, hogy dolgozzon ki egy sort hogy jobban teljesít, mint a O (n log n) az általános esetben. Ismételten, ne aggódj ez a nagy O jelölést, ha még nem látta még. 

Csak tudom, hogy ez azt jelenti, ha azt akartuk, hogy rendezni egy igazán nagy listát buborék rendezés, beszúrásos rendezés, és a kiválasztási sorrend esetleg venni lényegesen hosszabb merge sort. Ez nem jelenti azt, hogy merge sort gyorsabb lesz az összes listák vagy akár egyetlen listán egy bizonyos méret alatt. Például a beszúrási sort lehet a leggyorsabb fajta összes listák kisebb, mint 5 elemeket. A gyakorlatban, merge sort általában gyorsabb listák kisebb, mint 50 elemét. 

De ez az extra sebesség nem jön nélkül ár. Ellentétben a többi fajta, amelyek figyelembe egy listát, és módosítsa a listát a helyére amíg nem kap egy rendezett lista merge sort igényel további helyet egyesíteni 2 listákat együtt. Nem azonnal használhatja a listákat, amelyek összevonták, hogy tárolja az új listát mert talán felülbírálhatja elemek kell még vonni. Ez a hely egy kicsit az ára, de ez általában nem ésszerűtlen. És ez azt merge sort. 

A nevem Rob Bowden, és ez CS50. [CS50.TV] - És kiválasztás sort. [Nevet] Ó, értem, hogy ezt ki is kapcsol, mert hogyan is bemutató. Sorolja fel a bal oldalon. Ez egy elírás. [Misspoke] Elcsesztem - [Nevet] Én nem tudom, mi -