DOUG LLOYD: Nii CS50 me õppinud erinevaid sorteerimise ja otsimise algoritme. Ja mõnikord võib see olla natuke keeruline hoida lugu, mida algoritm teeb mida. Me oleme tõesti ainult kooritud pinda liiga, seal on palju muid otsimine ja sorteerimine algoritme. Nii see video olgem lihtsalt võtta paar minutit proovida ja ajama iga algoritmi alla selle põhielemendid nii et sa ei mäleta kõige Olulist teavet nende ja suutma väljendada erinevusi, kui vaja. 

Esimene on valikut omamoodi. Põhiidee valikut omamoodi on leida väikseim sorteerimata element massiivi ja vahetada see välja Esimene sorteerimata element, mis massiivi. Me ütlesime, et halvima käivitada ajal, mis oli n ruudus. Ja kui sa tahad meenutada, miks võtta Pilk valikut omamoodi video. Parim puhul töötamise ajal Samuti n ruudus. 

Bubble omamoodi, mõte, et üks on vahetada külgnevate paari. Nii et see võti, mis aitab teil mäletan siin midagi. Valik sorteerida on seni leida smallest-- mull sorteerida on swap kõrval paari. Me swap kõrval paari elementide kui nad on rikkis, mis tegelikult mullid suuremaid elemente paremale, ja samal ajal algab ka liikuda väiksemate elementide vasakule. Halvima juhtumis aeg mull omamoodi on n ruudus. Parim puhul töötamise ajal mull sorteerida on n. Kuna selles olukorras me ei actually-- Me ei pruugi vaja teha vahetustehinguid üldse. Meil on ainult teha üks läbida kõik n elementi. 

In sisestamise omamoodi, siis Põhiidee siin liigub. See on märksõna sisestamise omamoodi. Me läheme samm korraga läbi massiivi vasakult paremale. Ja kui me seda teeme, oleme hakkab nihkuma elemendid me oleme juba näinud, et teha ruumi väiksemad, mis vaja, et kusagil tagasi, et järjestatud osa. Nii me ehitame sorteeritud massiivi üks element korraga, vasakult paremale, ja muudame asju teha ruumi. Halvima run aeg sisestamise omamoodi on n ruudus. Parim puhul kestab aeg on n. 

Merge sort-- märksõna Siin on jagatud ja ühendada. Me jagada kogu massiivi, kas see on kuus elementi, kaheksa elemente, 10000 elements-- me jagada see alla poole, poole, poole, kuni meil on all massiivi n üks element massiivi. Komplekt n üks element massiivi. Nii me alustasime ühe 1000-element massiivi, ja me jõuame punkti, kus me on 1000 üks element massiivi. Siis hakkame ühendada need sub massiivid tagasi kokku õiges järjekorras. Nii me võtame kaks ühe elemendi massiivid ja luua kaks elementi massiivi. Võtame kaks kahe elemendi massiivid ja luua nelja elementi massiivi ja nii edasi ja nii edasi, kuni me oleme uuesti ümber ühe n element massiivi. 

Halvima run aeg ühendada sorteerida on n korda sisse n. Meil on n elementi, kuid Selle recombining protsessi võtab sisse n samme, et saada tagasi täis massiivi. Parimal juhul kestab aeg on ka n log n, sest see protsess ei ole tegelikult huvita, kas massiiv oli järjestatud või mitte alustada. Protsess on sama, seal on kuidagi lühise asju. Nii n log n halvimal juhul, n log n parimal juhul. 

Rääkisime kaks otsivad algoritme. Nii lineaarne otsing on umbes iterating. Lähtume kogu massiivi kord, vasakult paremale, püüdes leida number et me otsime. Halvima jooksuga on suur O n. See võib meid iterating üle iga element leida element ootame eest, kas viimasel positsioonil või üldse mitte. Kuid me ei saa kinnitada, et kuni me vaatasime kõike. olen parimal juhul leiame kohe. Parim puhul run aeg lineaarne otsing on omega 1. 

Lõpuks oli Kahendotsingupuu, mis nõuab assortii massiivi. Pea meeles, et on väga tähtsam töötamisel Kahendotsingupuu. See on eelduseks, et kasutades see-- massiivi, et te otsite läbi tuleb sorteerida. Muidu märksõna on jaga ja valitse. Split massiivi pooleks ja kõrvaldada pool elemendid iga kord, kui sa sõita läbi. Sellepärast jaga ja valitse ja jagamise asju poole lähenemist, halvima töötamise ajal kahekomponentsete otsing on log n, mis on praktiliselt parem kui lineaarne otsing on n. Parim puhul kestab ajad on ikka üks. 

Me võime leida see kohe Esimene kord, kui me jagunemine, kuid uuesti, pea meeles, et kuigi Kahendotsingupuu on oluliselt parem kui lineaarne otsing tõttu on samamoodi n versus n, sa oleks võinud minna läbi tööd sorteerimine oma massiivi esimene, mis võib teha vähem tõhusad sõltuvalt suurusest ning iterating järjestatud. 

Ma olen Doug Lloyd, see on CS50.