DOUG LLOYD: Takže CS50 jsme se dozvěděli o různé třídění a vyhledávání algoritmy. A někdy to může být trochu složitější udržet sledovat, co dělá, co algoritmus. Máme opravdu jen sušeného povrchu příliš, existuje mnoho dalších vyhledávání a třídění algoritmy. Takže v tomto videu pojďme jen trvat několik minut vyzkoušet a destilovat každý algoritmus až na jeho klíčové prvky takže si můžete pamatovat nejvíce důležité informace o nich a být schopen formulovat rozdíly, pokud je to nutné. 

První z nich je výběr třídit. Základní myšlenkou výběrem Třídit je najít nejmenší netříděného prvek v poli a vyměnit je s První netříděný prvek této matice. Řekli jsme, že nejhorší případ běžet doba, která byla n na druhou. A pokud si chcete připomenout, proč, přijmout Podívejte se na výběr třídění videu. Nejlepší-case run time je také n na druhou. 

Bubble sort, myšlenka, že jeden je swap přilehlých párů. Tak to je klíč, který vám pomůže vzpomenout na rozdíl zde. Výběrem Třídit je, tak daleko, najít smallest-- bublinu Třídění je swap přilehlých párů. My swap přilehlých párů prvků v případě, že jsou mimo provoz, který účinně bubliny větší prvky na pravé straně, a současně také začne pro pohyb menších prvků na levé straně. Nejhorší případ run time bublinkové druhu je n na druhou. Nejlepší-case run time Bubble sort je n. Protože v této situaci nemáme actually-- bychom mohli není potřeba žádné swapy vůbec. Máme jen udělat jednu projít přes všechny n prvků. 

V vložení řazení, Základní myšlenkou je zde mění. To je klíčové slovo pro vkládání druhu. Budeme krok jednou prostřednictvím pole zleva doprava. A jako my, my jsme se k posunu prvků jsme již viděli, aby se prostor pro ty menší, které potřebují, aby se vešly někde zpět v tomto seřazené části. Takže jsme budovat seřazené pole jednoho prvek v době, zleva doprava, a posuneme věci, aby místnost. Nejhorší run time of insertion sort je n na druhou. Nejlepší-case běhu n. 

Sloučit sort-- klíčové slovo Zde je rozdělit a sloučit. Rozdělili jsme celé palety, zda to je šest prvků, osm elementů, 10000 elements-- jsme to rozdělit dolů o polovinu, na polovinu, na polovinu, dokud nebudeme mít v poli n jednoho prvku pole. Sada n jednoho prvku pole. Tak jsme začali s jedním 1000-prvek pole, a dostaneme do bodu, kdy jsme mají 1000 jeden prvek pole. Pak jsme začali sloučit tyto dílčí pole dohromady ve správném pořadí. Takže vezmeme dva jednoho prvku pole a vytvořit dvě prvek pole. Bereme dva dva-prvků pole a vytvořit čtyři prvek pole a tak dále, a tak dále, dokud máme přestavěna jeden n prvku pole. 

Nejhorší run time of merge sort znamená n-krát log n. Máme n elementy, ale tento proces rekombinantním bere log n kroky k získání zpět na plnou pole. Nejlepší případ běhu je také n log n proto, že tento proces není opravdu jedno, jestli byl pole řazeny nebo ne začít. Tento proces je stejný, je tu žádný způsob, jak zkratu věci. Takže n log n v nejhorším případě, n log n v nejlepším případě. 

Mluvili jsme o dva vyhledávání algoritmy. Takže lineární hledání je o iterace. Pokračujeme přes pole Jednou, zleva doprava, se snaží najít číslo že hledáme. Nejhorší běhu je velký O n. To může trvat nás iterace po každé jednotlivé součásti najít prvek, co hledáme pro, a to buď na poslední pozici, nebo vůbec ne. Ale nemůžeme potvrdit, že dokud Dívali jsme se na všechno. m nejlepší-případ, najdeme hned. Nejlepší-case běh čas lineární vyhledávání je omegou 1. 

A konečně, bylo binární vyhledávání, která vyžaduje rozmanité pole. Pamatujte si, že je to velmi důležitým aspektem Při práci s binární vyhledávání. To je nezbytným předpokladem k používání to-- pole, které hledáte skrz musí být řazeny. V opačném případě klíčové slovo je rozděl a panuj. Rozdělte pole do poloviny a eliminovat polovina z prvků pokaždé, když, jak budete postupovat přes. Kvůli této rozděl a panuj a štípání věci v polovině přístupu, nejhorší případ run time binárních vyhledávání log n, která je v podstatě lepší než lineární hledání v n. Nejlepší-case běhu je ještě jeden. 

Mohli bychom ji okamžitě najít Poprvé děláme divizi, ale, Znovu si uvědomte, že i když je binární vyhledávání podstatně lepší než lineární hledání z důvodu, že log n oproti n, možná budete muset jít přes práci třídění své pole jako první, což by mohl dělat to méně efektivní v závislosti o velikosti iterace seřazeny. 

Jsem Doug Lloyd, je to CS50.