DOUG LLOYD: Takže CS50 sme sa dozvedeli o rôzne triedenie a vyhľadávanie algoritmy. A niekedy to môže byť trochu zložitejšie udržať sledovať, čo robí, čo algoritmus. Máme naozaj len sušeného povrchu príliš, existuje mnoho ďalších vyhľadávanie a triedenie algoritmy. Takže v tomto videu poďme len trvať niekoľko minút vyskúšať a destilovať každý algoritmus až na jeho kľúčové prvky takže si môžete pamätať najviac dôležité informácie o nich a byť schopný formulovať rozdiely, pokiaľ je to nutné. 

Prvý z nich je výber triediť. Základnou myšlienkou výberom Triediť je nájsť najmenší netriedeného prvok v poli a vymeniť ich s Prvý netriedený prvok tejto matice. Povedali sme, že najhorší prípad bežať doba, ktorá bola n na druhú. A ak si chcete pripomenúť, prečo, prijať Pozrite sa na výber triedenie videu. Najlepšie-case run time je tiež n na druhú. 

Bubble sort, myšlienka, že jeden je swap priľahlých párov. Tak to je kľúč, ktorý vám pomôže spomenúť na rozdiel tu. Výberom Triediť ich, tak ďaleko, nájsť smallest-- bublinu Triedenie je swap priľahlých párov. My swap priľahlých párov prvkov v prípade, že sú mimo prevádzky, ktorý účinne bubliny väčší prvky na pravej strane, a súčasne tiež začne pre pohyb menších prvkov na ľavej strane. Najhorší prípad run time bublinkové druhu je n na druhú. Najlepšie-case run time Bubble sort je n. Pretože v tejto situácii nemáme actually-- by sme mohli nie je potreba žiadne swapy vôbec. Máme len urobiť jednu prejsť cez všetky n prvkov. 

V vloženie radenie, Základnou myšlienkou je tu mení. To je kľúčové slovo pre vkladanie druhu. Budeme krok raz prostredníctvom poľa zľava doprava. A ako my, my sme sa k posunu prvkov sme už videli, aby sa priestor pre tie menšie, ktoré potrebujú, aby sa zmestili niekde späť v tomto zoradené časti. Takže sme budovať zoradené poľa jedného prvok v čase, zľava doprava, a posunieme veci, aby miestnosť. Najhoršie run time of insertion sort je n na druhú. Najlepšie-case spustiť n. 

Zlúčiť sort-- kľúčové slovo Tu je rozdeliť a zlúčiť. Rozdelili sme celé palety, či to je šesť prvkov, osem elementov, 10000 elements-- sme to rozdeliť dole o polovicu, na polovicu, na polovicu, kým nebudeme mať v poli n jedného prvku poľa. Sada n jedného prvku poľa. Tak sme začali s jedným 1000-prvok poľa, a dostaneme do bodu, keď sme majú 1000 jeden prvok poľa. Potom sme začali zlúčiť tieto čiastkové polia dohromady v správnom poradí. Takže zoberieme dva jedného prvku poľa a vytvoriť dve prvok poľa. Berieme dva dva-prvkov poľa a vytvoriť štyri prvok poľa a tak ďalej, a tak ďalej, až kým máme prestavaná jeden n prvku poľa. 

Najhoršie run time of merge sort znamená n-krát log n. Máme n elementy, ale tento proces rekombinantným berie log n kroky na získanie späť na plnú pole. Najlepšie prípad behu je tiež n log n preto, že tento proces nie je naozaj jedno, či bol pole radené alebo nie začať. Tento proces je rovnaký, je tu žiadny spôsob, ako skratu veci. Takže n log n v najhoršom prípade, n log n v najlepšom prípade. 

Hovorili sme o dva vyhľadávanie algoritmy. Takže lineárne hľadanie je o iterácie. Pokračujeme cez pole Raz, zľava doprava, sa snaží nájsť číslo že hľadáme. Najhoršie behu je veľký O n. To môže trvať nás iterácie po každej jednotlivé súčasti nájsť prvok, čo hľadáme pre, a to buď na poslednej pozícii, alebo vôbec nie. Ale nemôžeme potvrdiť, že kým Pozerali sme sa na všetko. m najlepšie-prípad, nájdeme hneď. Najlepšie-case beh čas lineárne vyhľadávanie je omegou 1. 

Napokon, bolo binárne vyhľadávanie, ktorá vyžaduje rozmanité polia. Pamätajte si, že je to veľmi dôležitým aspektom Pri práci s binárne vyhľadávanie. To je nevyhnutným predpokladom na používanie to-- pole, ktoré hľadáte skrz musí byť radené. V opačnom prípade kľúčové slovo je rozdeľ a panuj. Rozdeľte pole do polovice a eliminovať polovica z prvkov zakaždým, keď, ako budete postupovať cez. Kvôli tejto rozdeľ a panuj a štiepanie veci v polovici prístupe, najhorší prípad run time binárnych vyhľadávanie log n, ktorá je v podstate lepšie ako lineárny hľadania v n. Najlepšie-case behu je ešte jeden. 

Mohli by sme ju okamžite nájsť Prvýkrát robíme divíziu, ale, Znovu si uvedomte, že aj keď je binárny vyhľadávanie podstatne lepší ako lineárny hľadanie z dôvodu, že log n oproti n, možno budete musieť ísť cez prácu triedenie svoje pole ako prvý, čo by mohol robiť to menej efektívne v závislosti o veľkosti iterácie zoradené. 

Som Doug Lloyd, je to CS50.