DOUG LLOYD: So in CS50 ons geleer het oor 'n verskeidenheid van sortering en soek algoritmes. En soms is dit kan wees 'n bietjie lastig te hou spoor van wat algoritme wat doen. Ons het eintlik net maer die oppervlak ook daar is baie ander soek en sortering algoritmes. So in hierdie video laat net 'n paar minute om te probeer en distilleer elke algoritme af na die kern elemente sodat jy kan die mees onthou belangrike inligting oor hulle en in staat wees om die te verwoord verskille, indien nodig. 

Die eerste is seleksie soort. Die basiese idee agter seleksie soort is te vind in die kleinste ongesorteerde element in 'n skikking en ruil dit met die eerste ongesorteerde element van daardie skikking. Ons het gesê dat die ergste geval hardloop tyd van wat n vierkant. En as jy wil om te onthou hoekom nie, neem 'n blik op die seleksie soort video. Die beste geval hardloop tyd ook N kwadraat. 

Borrel soort, die idee agter dat een is om aangrensende pare te ruil. So wat is die sleutel wat jy help Onthou hier die verskil. Seleksie soort is, so ver, vind die smallest-- borrel sorteer IS ruil aangrensende pare. Ons ruil aangrensende pare elemente as hulle is buite orde, wat effektief borrels groter elemente na regs, en op dieselfde tyd wat dit begin ook kleiner elemente aan die linkerkant beweeg. Die ergste geval geval hardloop tyd van die borrel soort is N kwadraat. Die beste geval hardloop tyd van die borrel soort is n. Want in daardie situasie ons nie actually-- ons dalk nie nodig om enige swaps at all. Ons het net om een ​​te maak slaag in al n elemente. 

In invoeging soort, die basiese idee hier is verskuiwing. Dit is die sleutelwoord vir invoeging soort. Ons gaan een keer stap vir stap deur die skikking van links na regs. En as ons dit doen, ons is gaan elemente skuif ons het reeds gesien om plek te maak vir kleiner wat nodig het om iewers te pas terug in daardie gesorteer gedeelte. So ons bou die gesorteerde skikking een element op 'n slag, van links na regs, en ons skuif dinge om plek te maak. Die ergste geval run tyd van invoeging soort is N kwadraat. Die beste geval loop die tyd is n. 

Merge sort-- die navraag hier is verdeel en saam te smelt. Ons verdeel die volle reeks, of dit is ses elemente, agt elemente, 10000 elements-- ons verdeel dit af met die helfte, met die helfte, met die helfte, totdat ons onder array van N een element skikkings. 'N stel van N een element skikkings. So het ons begin met 'n 1000-element skikking, en ons kry tot op die punt waar ons het 1000 een-element skikkings. Dan begin ons om daardie sub skikkings saamsmelt weer saam in die korrekte volgorde. So neem ons twee een-element skikkings en die skep van 'n twee-element skikking. Ons neem twee twee-element skikkings en die skep van 'n vier-element array en so aan en so aan totdat ons het weer herbou een N element skikking. 

Die ergste geval run tyd van saamsmelt soort is n keer inteken n. Ons het n elemente, maar hierdie recombining proses neem meld N stappe te kry terug na 'n volle reeks. Die beste geval loop die tyd is ook n log N omdat hierdie proses nie regtig omgee of die skikking was gesorteer of nie om te begin met. Die proses is dieselfde, daar is geen manier om 'n kortsluiting dinge. So n teken N in die ergste geval, N teken N in die beste geval. 

Ons het gepraat oor twee soek algoritmes. So lineêre soek is sowat iterating. Ons gaan oor die skikking een keer, van links na regs, probeer om die getal te vind dat ons is op soek na. Die ergste geval loop die tyd is groot O van n. Dit mag dalk vir ons neem iterating oor elke enkele element om die element wat ons soek vind vir, óf in die laaste posisie, of glad nie. Maar ons kan nie bevestig dat tot Ons het gekyk na alles. m die beste geval is, vind ons onmiddellik. Die beste geval run tyd van lineêre soek is omega van 1. 

Laastens was daar binêre soek, wat vereis verskillende skikking. Onthou dat 'n baie belangrike oorweging wanneer daar met binêre soek. Dit is 'n voorvereiste vir die gebruik van it-- die skikking wat jy soek deur middel van gesorteer moet word. Andersins, die navraag is verdeel en oorwin. Verdeel die skikking in die helfte en helfte van die elemente te skakel elke keer as jy deur. As gevolg van hierdie Verdeel en oorwin en verdeel dinge in die helfte benadering, die ergste geval hardloop tyd van binêre soek is meld N, wat aansienlik is beter as lineêre soek se n. Die beste geval loop die tyd is nog steeds een. 

Ons kan dit dadelik die vind eerste keer maak ons ​​'n afdeling, maar weer, onthou dat hoewel binêre soek is aansienlik beter as lineêre soek uit hoofde van wat log N versus n, jy mag hê om te gaan deur die werk sorteer jou array eerste, wat kan dit minder doeltreffend maak, afhangende van die grootte van die iterating gesorteer. 

Ek is Doug Lloyd, dit is CS50.