Doug LLOYD: Tako je u CS50 smo naučili o razne sortiranje i pretraživanje algoritmi. A ponekad to može biti malo lukav da bi pratiti što algoritam što radi. Mi smo zapravo samo obrano površinu previše, postoje mnoge druge pretraživanje i sortiranje algoritama. Tako je u ovom videu ćemo samo uzeti nekoliko minuta pokušati destilirati svaki algoritam do njezinih temeljnih elemenata tako da možete se sjetiti najviše važne informacije o njima i biti u stanju artikulirati razlike, ako je potrebno. 

Prvi je izbor vrsta. Osnovna ideja za odabir vrste se naći najmanji nesortiranog elementa u niz i zamijeniti s Prvi Nesortirano element tog polja. Rekli smo da je najgori slučaj pokrenuti vrijeme da n je kvadrat. A ako želite podsjetiti zašto je, potrajati Pogled na izbor sortiranja video. Najbolji slučaja pokrenuti vrijeme također je n kvadrat. 

Mjehurić vrsta, ideja da jedna za swap susjedna parova. Dakle, to je ključ koji vam pomaže zapamtite razliku ovdje. Izbor vrste je, do sada, naći smallest-- mjehurić sorta je swap susjedna parova. Mi swap susjedna para elemenata ako su izvan reda, koji učinkovito mjehurići većih elemenata desno, a ujedno je i počinje premjestiti manje elemenata na lijevo. Najgorem slučaju slučaja pokrenuti vrijeme od mjehurića vrste n na kvadrat. Najbolji slučaja pokrenuti vrijeme Bubble sort n. Jer u toj situaciji ne actually-- nismo mogli trebati napraviti nikakve zamjene na sve. Imamo samo napraviti jedan proći kroz sve n elemenata. 

U unosa vrste, Osnovna ideja je ovdje prebacuje. To je ključna za umetanje vrste. Idemo korak po jednom Niz od lijeva na desno. I kao što nam je činiti, mi smo će pomak elemenata već smo vidjeli kako bi napravili mjesta za manjih koje je potrebno da stane negdje natrag u tom sortirani dijelu. Tako smo izgraditi sortirani niz jedan Element na vrijeme, s lijeva na desno, a mi pomak stvari kako bi napravili mjesta. Najgorem slučaju izvođenja vrijeme umetanje vrsta n na kvadrat. Najbolji slučaja pokrenuti vrijeme nje. 

Spoji sort-- ključnu riječ Ovdje je podijeljen i spajanje. Podijeliti smo cijeli niz, bilo to je šest elemenata, osam elemenata, 10.000 elements-- smo ga podijeliti dolje po pola, pola, pola, dok smo pod nizom n jedan element polja. Skup je n jedan element polja. Tako smo počeli s jednim 1000-element matrice, i mi doći do točke gdje smo ima 1.000 jedna elementa polja. Onda smo počeli spojiti one pod polja natrag zajedno u ispravnom redoslijedu. Tako smo se dva jedan-elementa polja i stvoriti dva elementa niza. Vodimo dva dva elementa polja i stvoriti četiri elementa niz i tako dalje i tako dalje dok imamo opet obnovili jednu n element matrice. 

Najgorem slučaju izvođenja vrijeme spojiti vrsta je N puta prijavite nje. Imamo n elemenata, ali ovaj proces ponovnog spajanja traje prijavite n koraka kako bi dobili natrag na punu lepezu. Najbolji slučaj pokrenuti vrijeme je n dnevnik nje, jer se taj proces ne stvarno briga je li niz je razvrstani ili ne početi s. Postupak je isti, nema ni na koji način kratkog spoja stvari. Tako je n log n u najgorem slučaju, n log n u najboljem slučaju. 

Razgovarali smo o dvije traži algoritama. Dakle, linearno pretraživanje je oko Ponavljanje. Nastavljamo preko polja jednom, s lijeva na desno, pokušava pronaći broj da tražimo. Najgorem slučaju pokrenuti vrijeme je veliki O n. To bi moglo potrajati iterating nas preko svakog pojedinog elementa pronaći element tražimo za, bilo u zadnjem položaju, ili uopće ne. No, ne možemo potvrditi da je do smo pogledali sve. m najbolje slučaj, odmah smo pronašli. Najbolji slučaja pokrenuti vrijeme linearno pretraživanje je omega 1. 

Na kraju, tu je binarno pretraživanje, što zahtijeva ponekog niz. Sjetite se da je vrlo važno razmatranje kada se radi s binarnim pretraživanja. To je preduvjet korištenja it-- Niz koji ste u potrazi kroz moraju biti razvrstani. Inače, ključna riječ je podijeli pa vladaj. Split niz u pola i eliminirati polovice elemenata svaki put kao što nastavite putem. Zbog tog Podijeli pa vladaj i cijepanje stvari u pola pristupu, najgorem slučaju izvođenja vrijeme od binarno pretraživanje je Prijava N, koji je uglavnom bolji od linearnog Traži u n. Najbolji slučaja pokrenuti vrijeme je još uvijek jedan. 

Možemo ga pronaći odmah Prvi put smo napraviti podjelu, ali, opet, ne zaboravite da Iako je binarno pretraživanje je znatno bolje nego linearna pretraživanje samim time što su log n odnosu n, možda ćete morati proći kroz rad sortiranje svoj niz prvi, koji Možda bi ga manje učinkovit, ovisno o veličini Ponavljanje sortirati. 

Ja sam Doug Lloyd, ovo je CS50.