DOUG LLOYD: Så i CS50 vi lært om en rekke sorterings- og søke algoritmer. Og noen ganger kan det være litt vanskelig å holde rede på hva algoritme gjør hva. Vi har egentlig bare skummet overflaten også, det er mange andre søking og sortering algoritmer. Så i denne videoen la oss bare ta noen få minutter å prøve og destillere hver algoritme ned til sine kjerneelementer slik at du kan huske mest viktig informasjon om dem og være i stand til å artikulere forskjeller, om nødvendig. 

Den første er utvalget slag. Den grunnleggende ideen bak utvalget sort er å finne den minste usortert element i en matrise og bytte det med første usortert element av denne matrisen. Vi sa at det verste-fall kjøretid fra som ble n squared. Og hvis du ønsker å huske hvorfor, ta en titt på utvalget slags video. Den best-case kjøretid er også n squared. 

Boble sortere, ideen bak det en er å bytte tilstøtende par. Så det er nøkkelen som hjelper deg Husk forskjellen her. Utvalg liksom er, så langt, finne smallest-- boble sort er bytte tilstøtende par. Vi bytte tilstøtende par elementer hvis de er ute av drift, noe som effektivt bobler større elementer til høyre, og samtidig som den også begynner å flytte mindre elementer til venstre. Den verst tenkelige tilfelle kjøretid boble slag er n squared. Den best-case kjøretid boble typen er n. Fordi i den situasjonen vi ikke actually-- vi kanskje ikke trenger å gjøre noen bytteavtaler i det hele tatt. Vi trenger bare å lage én passere tvers av alle n elementer. 

I innsetting sortere, den Grunntanken her er skiftende. Det er nøkkelordet for innsetting slag. Vi kommer til å gå en gang gjennom matrisen fra venstre til høyre. Og som vi gjør, er vi kommer til å skifte elementer har vi allerede sett å gi plass til små som trenger å passe et sted tilbake i det sortert delen. Så vi bygge den sorterte rekke én element om gangen, fra venstre mot høyre, og vi skifte ting å gjøre plass. Worst-case kjøretid fra innsetting slag er n squared. Den best-case kjøretid er n. 

Flett sort-- nøkkelordet her er splitte og slå. Vi delt hel rekke, enten det er seks elementer, åtte elementer, 10000 elements-- vi dele den ned til det halve, det halve, det halve, før vi har under matrise n ett element arrays. Et sett av n én elementrekker. Så vi startet med en 1000-element array, og vi kommer til et punkt der vi har 1000 ett element arrays. Da begynner vi å fusjonere de under arrays sammen igjen i riktig rekkefølge. Så vi tar to one-element arrays og lage en to-element array. Vi tar to to-element arrays og skape en fire-elementsatsen og så videre og så videre inntil vi har igjen ombygd én n element array. 

Worst-case kjøretid fra fusjonere slags er N ganger log n. Vi har n elementer, men dette rekombinerende prosessen tar log n skritt for å få tilbake til en hel rekke. Beste fall kjøretid er også n log n fordi denne prosessen gjør egentlig ikke bryr seg om tabellen var sortert eller ikke til å begynne med. Prosessen er den samme, er det ingen måte å kortslutnings ting. Så n log n i verste fall n log n i beste fall. 

Vi snakket om to- søke algoritmer. Så lineær søk er om itera. Vi fortsetter gjennom hele arrayet en gang, fra venstre til høyre, prøver å finne nummeret at vi leter etter. Worst-case kjøretid er stor O av n. Det kan ta oss itera over hver enkelt element å finne elementet vi leter for, enten i den siste plassen, eller ikke i det hele tatt. Men vi kan ikke bekrefte at inntil vi har sett på alt. m best-case, finner vi umiddelbart. Den best case driftstiden lineær søk er omega for en. 

Endelig var det binære søk, som krever assortert utvalg. Husk at det er en veldig viktig faktor når du arbeider med binære søk. Det er en forutsetning for å hjelp it-- matrisen at du leter gjennom skal sorteres. Ellers nøkkelordet er splitt og hersk. Splitte rekken i halv og eliminere halvparten av elementene hver gang du går gjennom. På grunn av dette Splitt og hersk og dele ting i halvparten tilnærming, worst-case kjøretid av binære søk er log n, som er i det vesentlige bedre enn lineær søk er n. Den best-case kjøre tiden er fortsatt en. 

Vi kan finne det umiddelbart første gang vi gjør en divisjon, men, igjen, husk at selv om binære søk er vesentlig bedre enn lineær søk kraft av å være log n versus n, du kan ha til å gå gjennom arbeidet sorterings array først, noe som kan gjøre det mindre effektivt avhengig på størrelsen av den itera sortert. 

Jeg er Doug Lloyd, dette er CS50.