Doug LLOYD: Tātad CS50 mēs uzzinājām dažādas šķirošanas un meklēšanas algoritmi. Un dažreiz tas var būt nedaudz grūts, lai saglabātu līdzi tam, ko algoritms ko dara. Mēs esam tiešām tikai vājpiena virsmu pārāk, ir daudzi citi meklēšana un šķirošanas algoritmu. Tātad šajā video pieņemsim lietojiet tikai dažas minūtes mēģināt destilēt katru algoritmu leju, lai tās galvenajiem elementiem lai jūs varētu atcerēties visvairāk Svarīga informācija par tām un jāspēj formulēt atšķirības, ja nepieciešams. 

Pirmais ir izvēle kārtošanas. Pamatideja atlases veida ir atrast mazāko nešķirotas elements masīva un mijmaiņas to ar Pirmais nešķiroti elements šī masīva. Mēs teicām, ka sliktākajā gadījumā palaist laiks, kas bija n brusas. Un, ja jūs vēlaties, lai atcerēties, kāpēc ņemt apskatīt atlase kārtošanas video. Labākā gadījuma darbības laiks ir arī n brusas. 

Bubble kārtot, ideja, ka viens ir mijmaiņas blakus pāriem. Tātad tas ir galvenais, kas palīdz jums atcerēties atšķirību šeit. Atlases kārtošanas ir, līdz šim, atrast smallest-- burbuli kārtošanas ir mijmaiņas blakus pāriem. Mēs mijmaiņas blakus pāriem elementu, ja tie ir iziet no ierindas, kas efektīvi burbuļi lielākus elementus tiesībām, un tajā pašā laikā, tā arī sākas virzīties uz mazākiem elementiem kreisi. Sliktākajā-Case darbības laiks burbuļiem veida ir n brusas. Labākā gadījuma darbības laiks burbuļiem kārtošanas ir n. Jo šajā situācijā mums nav actually-- mēs, iespējams, nav nepieciešams nekādas mijmaiņas darījumus vispār. Mums ir tikai veikt vienu iet pāri visām n elementiem. 

In ievietošanas veida, tad Pamatideja šeit mainās. Tas ir atslēgvārds ievietošanas veida. Mēs ejam soli vienreiz cauri masīvs no kreisās puses uz labo. Un, kā mēs to darām, mēs esam gatavojas novirzīt elementus mēs jau esam redzējuši, lai padarītu telpu mazākie, kas nepieciešams, lai ietilptu kaut kur atpakaļ šajā sakārtoti porciju. Tātad mēs veidojam sakārtoti masīvs viens elements laikā, no kreisās uz labo, un mēs novirzīt lietas, lai padarītu telpu. Sliktāko palaist laiks ievietošanas kārtošanas ir n brusas. Vislabāk lieta palaist laiks n. 

Apvienot sort-- atslēgvārda šeit ir sadalīt un apvienot. Mēs sadalīt pilnu klāstu, vai tas ir seši elementi, astoņas elementus, 10,000 elements-- mēs sadalīt to leju uz pusi, uz pusi, uz pusi, kamēr mums ir zem masīva no n viens elements masīvi. Kopums n viena elementa masīvi. Tā mēs sākām ar vienu 1000-elementu masīvs, un mēs nokļūt līdz vietai, kur mēs ir 1000 viena elementu masīvu. Tad mēs sākam apvienot šos sub bloki atpakaļ kopā pareizā secībā. Tātad mēs divas viena elementu masīvu un radīt divu elementu masīvu. Ņemam divus divu elementu masīvu un izveidot četru elementu masīvs un tā tālāk, un tā tālāk, kamēr mēs esam vēlreiz pārbūvēta viena n elementu klāstu. 

Sliktāko palaist laiks apvienot kārtošanas ir n reizes log n. Mums ir n elementi, bet šis krustmijas process ņem log n soļi, lai saņemtu atpakaļ uz pilnu masīvs. Labākā lieta palaist laiks ir arī n log n jo šis process nav īsti vienalga, vai masīvs bija sakārtoti vai ne, lai sāktu ar. Process ir tāds pats, tur ir Nav veids, kā īsslēguma lietām. Tātad n log n sliktākajā gadījumā, n log n labākajā gadījumā. 

Mēs runājām par divām meklējot algoritmus. Tātad lineārā meklēšana ir par atkārtojot. Mēs turpināt visā masīvs vienreiz, no kreisās uz labo pusi, mēģinot atrast numuru ka mēs meklējam. Sliktāko palaist laiks ir liels O n. Tas var aizņemt mūs atkārtojot pāri katru elementu lai atrastu elementu mēs meklējam par, vai nu pēdējā pozīcijā, vai nav vispār. Bet mēs nevaram apstiprināt, ka līdz mēs esam paskatījās viss. m vislabāk lietu, mēs atrast uzreiz. Vislabāk gadījums palaist laiks lineārā meklēšana ir omega no 1. 

Visbeidzot, tur bija bināro meklēšanu, kas prasa asorti masīvs. Atcerieties, ka ir ļoti Svarīgs apsvērums strādājot ar bināro meklēšanu. Tas ir priekšnoteikums, lai, izmantojot it-- masīvs, ka jūs meklējat, izmantojot ir sakārtoti. Pretējā gadījumā atslēgvārds ir skaldi un valdi. Sadalīt masīvs uz pusi un likvidēt puse no elementiem Katru reizi, kā jūs turpināt cauri. Sakarā ar šo skaldi un valdi un sadalīšanas lietas pusi pieeju, sliktākajā gadījuma darbības laiks no binārā meklēšana ir log n, kas ir būtiski labāk nekā lineārās meklēšana s n. Vislabāk lieta palaist laiks ir vēl viens. 

Mēs varētu atrast to nekavējoties Pirmo reizi mēs sadalījumu, bet, atkal, atcerieties, ka kaut arī binārā meklēšana ir ievērojami labāk nekā lineāri meklēšanu pamatojoties uz to log n pret n, jums varētu būt, lai iet caur darbu šķirošanas savu masīvs pirmais, kas varētu padarīt to mazāk efektīvu atkarībā par lielumu atkārtojot sakārtoti. 

Es esmu Doug Lloyd, tas ir CS50.