DOUG Lloyd: Niin CS50 me opimme erilaisia ​​lajittelu ja etsiminen algoritmeja. Ja joskus se voi olla hieman hankala pitää kirjaa mitä algoritmin tekee mitä. Olemme oikeastaan ​​vain rasvaton pinta liian, on olemassa monia muita etsimistä ja lajittelualgoritmeja. Joten tässä video nyt vain kestää muutaman minuutin yrittää polttaa kukin algoritmi alas sen keskeiset osatekijät joten voit muistaa eniten tärkeää tietoa niistä ja pystyä ilmaisemaan erot, jos on tarpeen. 

Ensimmäinen on valinta lajitella. Perusajatuksena valinta lajitella on löytää pienin lajittelemattomat elementti array ja vaihtaa sen kanssa ensimmäinen lajittelematon osa tätä array. Sanoimme, että pahin ajoaika, joka oli n potenssiin. Ja jos haluat muistaa miksi, ota katso valinta lajitella video. Parhaassa tapauksessa ajoaika on myös n potenssiin. 

Kuplalajittelu, ajatuksena että yksi on vaihtaa vieressä paria. Niin se on avain, jonka avulla voit muistaa ero täällä. Valinta lajitella on, toistaiseksi, löytää smallest-- kupla SORT vaihtaa vieressä paria. Me vaihtaa vieressä paria elementtien jos he ovat epäkunnossa, joka tehokkaasti kuplia suurempi elementit oikealle, ja samalla se myös alkaa siirtyä pienempiä osia vasemmalle. Pahin tapaus ajoaika kupla lajitella on n potenssiin. Parhaassa tapauksessa ajoaika kupla lajitella on n. Koska tässä tilanteessa emme actually-- emme ehkä tarvitse tehdä swap ollenkaan. Meillä on vain tehdä yhden siirtää kaikilla n elementtiä. 

Vuonna lisäyslajittelun, Perusajatuksena tässä on siirtymässä. Se avainsanan lisäyslajittelun. Aiomme vaiheeseen kerran kautta array vasemmalta oikealle. Ja kuten teemme, olemme menossa siirtää elementtejä olemme jo nähneet tehdä tilaa pienempiä, jotka täytyy sovittaa jonnekin takaisin että lajiteltu osaan. Joten me rakennamme lajitellut array yksi elementti kerrallaan, vasemmalta oikealle, ja siirrämme asioita tehdä tilaa. Pahimman tapauksen ajoaika lisäyslajittelun on n potenssiin. Paras-tapaus ajoaika on n. 

Yhdistä sort-- avainsanan täällä on jakaa ja yhdistää. Jaamme täyden valikoiman, onko se on kuusi elementtejä, kahdeksan elementtejä, 10000 elements-- me jakaa sen laskenut puoleen, puoleen, puoleen, kunnes meillä on alle array n yksi elementti taulukot. Joukko n yksi elementti taulukot. Joten aloitimme yksi 1000-elementti array, ja saamme siihen pisteeseen, jossa meillä on 1000 yksi-elementti paneelit. Sitten alamme yhdistää niillä osa paneelit takaisin yhteen oikeassa järjestyksessä. Joten otamme kaksi yhden elementin paneelit ja luoda kaksi-elementti array. Otamme kaksi kahden alkion taulukot ja luoda neljän alkiotaulukon ja niin edelleen ja niin edelleen, kunnes olemme taas uudelleen yksi n alkiotaulukko. 

Pahimman tapauksen ajoaika yhdistää lajitella on n kertaa log n. Meillä on n alkiota, mutta tämä rekombinaatiovälineen prosessi panee log n askelta päästä Takaisin täyden valikoiman. Parhaassa tapauksessa ajoaika on myös n loki n koska tämä prosessi ei oikeastaan piittaa siitä array oli lajiteltu tai ei aloittaa. Prosessi on sama, on olemassa mitenkään oikosulku asioita. Joten n log n pahimmassa tapauksessa, n log n parhaassa tapauksessa. 

Puhuimme kaksi hakuja algoritmeja. Joten lineaarinen haku on noin iteroimalla. Etenemme koko joukko kerran, vasemmalta oikealle, yrittää löytää numero että etsimme. Pahimman tapauksen ajoaika on iso O n. Se voi viedä meidät iteroimalla poikki jokainen elementti löytää elementti etsimme varten, joko viimeisessä asennossa, tai ei lainkaan. Mutta emme voi vahvistaa, että ennen teimme kaiken. m parhaassa tapauksessa, löydämme heti. Paras-tapaus ajoaika lineaarinen haku on omega 1. 

Lopuksi nousi binäärihaku, joka vaatii valikoituja array. Muista, että on hyvin tärkeä näkökohta kun työskentelet binäärihakupuu. Se on edellytys käyttäen it-- array että etsit kautta pitää lajitella. Muuten avainsana on hajota ja hallitse. Jakaa array osaksi puoli ja poistaa puolet elementit joka kerta kun jatkat kautta. Tämän vuoksi hajoita ja hallitse ja halkaisu asioita puoli lähestymistapa, pahimman tapauksen ajoaika binary haku on log n, joka on olennaisesti parempi kuin lineaarinen haku n n. Paras-tapaus ajoaika on edelleen yksi. 

Voisimme löytää sen heti Ensimmäistä kertaa teemme jako, mutta, jälleen, muista, että vaikka binary haku on huomattavasti parempi kuin lineaarinen haku sen perusteella, että log n vs. n, saatat joutua käydä läpi työn lajittelu matriisisi ensimmäinen, joka voisi tehdä sen vähemmän tehokas riippuen koosta iteroimalla lajiteltu. 

Olen Doug Lloyd, tämä on CS50.