DOUG LLOYD: Tehát CS50 tanultunk a különböző válogatás és keresés algoritmusok. És néha lehet egy kicsit trükkös tartani követni, hogy mi algoritmus mit csinál. Már tényleg csak sovány a felület túl, sok más keresés és rendezési algoritmusok. Szóval ez a videó nézzük Csak egy pár percre hogy megpróbálja distill egyes algoritmus le központi elemének, így emlékszik a leginkább Fontos információkat róluk és képes legyen megfogalmazni a különbségek, ha szükséges. 

Az első szelekció egyfajta. Az alapgondolata kiválasztási sorrend találnunk a legkisebb szétválogatott elem egy tömbben, és cserélni azt a első válogatás nélkül eleme a tömb. Azt mondta, hogy a legrosszabb futási ideje, amit n négyzeten. És ha azt szeretnénk felidézni, miért, hogy Egy pillantás a kiválasztási sorrend videót. A legjobb esetben futási idő is n faragva. 

Bubble sort, az ötlet mögött, hogy az egyik az, hogy a csere szomszédos pár. Szóval ez a kulcs, amely segít emlékszik itt a különbség. Válogatás a sort, eddig megtalálni a smallest-- buborék rendezés swap szomszédos párokat. Mi swap szomszédos párok elemek, ha azok elfogyott a rend, amely hatékonyan buborékok nagyobb elemeket, hogy a jobb, és ugyanakkor azt is megkezdődik mozgatni kisebb elemeket a bal oldalon. A legrosszabb esetben futási idő buborék rendezés n faragva. A legjobb esetben futási idő buborék rendezés n. Mivel ebben a helyzetben mi nem actually-- talán nem kell semmilyen csereügyletek egyáltalán. Már csak, hogy egy át az összes n elemű. 

Beszúrási sort, a alapötlet itt tolódik. Ez a kulcsszó behelyezhető sort. Fogunk lépéssel egyszer át a tömb balról jobbra. És, mint mi vagyunk, fog váltani elemek már láttuk, hogy helyet adjon kisebb, hogy kell, hogy illeszkedjen valahol vissza, hogy válogatni része. Így építünk rendezett tömbben egy eleme egy időben, balról jobbra, és mi váltás dolgokat, hogy legyen hely. A legrosszabb futási ideje behelyezés rendezés n faragva. A legjobb esetben futási ideje n. 

Merge sort-- a kulcsszó Itt van osztva, és egyesíti. Mi osztott a teljes tömb, hogy ez hat elem, nyolc elem, 10.000 elements-- mi osztott meg a felére, felére, felére, amíg van értelmében tömb n egyik eleme tömbök. Egy sor n az egyik eleme tömbök. Így kezdődött az egyik 1000 tömböt, és mi kap az a pont, ahol hogy 1000 egyelemû tömbök. Aztán elkezdik egyesíteni azokat a sub tömbök Újra együtt a megfelelő sorrendben. Tehát, hogy két egyelemű tömböt és hozzon létre egy kételemű tömb. Vesszük két kételemű tömb és hozzon létre egy négy részből álló tömb és így tovább, és így tovább, amíg meg nem ismét átépítették egy n elem tömb. 

A legrosszabb futási ideje merge sort n-szerese log n. Van n elemek, de ez a rekombináció folyamatának tudomásul log n kap vissza a teljes tömb. A legjobb esetben üzemidejét is n log n, mert ez a folyamat nem igazán érdekel, hogy a tömb volt válogatni, vagy sem kezdeni. A folyamat ugyanaz, van nem lehet zárlat a dolgokat. Tehát n log n a legrosszabb esetben, n log n a legjobb esetben. 

Beszéltünk két keresőalgoritmust. Tehát lineáris keresés szól iterációjával. Mi jár az egész tömb Egyszer, balról jobbra, megpróbálja megtalálni száma hogy keresünk. A legrosszabb futási ideje nagy O n. Lehet, hogy minket ismételve szerte minden elemét megtalálni az elem keresünk A, vagy az utolsó pozícióban, vagy egyáltalán nem. De nem tudjuk megerősíteni, hogy amíg átnéztük mindent. vagyok a legjobb, a találunk azonnal. A legjobb esetben futási ideje lineáris keresés omegája 1. 

Végül ott volt a bináris keresés, amely előírja válogatott tömb. Ne feledje, hogy ez egy nagyon Fontos szempont ha dolgozik, bináris keresés. Ez előfeltétele annak, hogy a it-- A tömb, amit keres keresztül kell válogatni. Ellenkező esetben a kulcsszó ez Oszd meg és uralkodj. Osztott a tömb a felét és megszüntesse a fele az elemek minden alkalommal, ahogy halad előre. Emiatt Oszd meg és uralkodj és felosztása a dolgok fele megközelítést, A legrosszabb futási idő A bináris keresés log n, amely lényegében jobb, mint a lineáris keresés a n. A legjobb esetben futásidő még mindig az egyik. 

Lehet, hogy rögtön megtalálta a először teszünk egy részlege, de, Újra, ne feledje, hogy bár bináris keresés lényegesen jobb, mint a lineáris keresés annak révén, hogy log n versus n, lehet, hogy menjen át a munkát A válogatás a tömb első, amely Lehet, hogy kevésbé hatékony függően A méret a iterációjával rendezve. 

Én Doug Lloyd, ez CS50.