DOUG LLOYD: Belə ki, CS50 biz haqqında öyrəndim çeşidlənməsi və axtarış bir sıra alqoritmləri. Və bəzən ola bilər saxlamaq üçün bir az çətin nə alqoritm track nə yoxdur. Biz, həqiqətən, yalnız var çox səthi məsulları bir çox digər axtarış var və alqoritmləri çeşidlənməsi. Belə ki, bu video edək yalnız bir neçə dəqiqə cəhd və hər alqoritm çəkmək əsas elementləri aşağı belə ki, ən yadda bilər onlar haqqında əhəmiyyətli məlumatlar və ifadə etmək mümkün fərqlər, zəruri hallarda. 

ilk seçim sortudur. seçim sort əsas ideyası kiçik çeşidlənməmiş element tapmaq olunur və bir sıra ilə dəyişdirmək ki, serialın ilk çeşidlənməmiş element. Ən pis halda olduğunu bildirib ki, run dəfə kvadrat n oldu. Və niyə geri istəyirsinizsə, almaq bir seçim sort video baxmaq. Ən yaxşı halda run vaxt də n kvadrat edir. 

Bubble sort ki, arxasında ideyası bir bitişik cüt dəyişdirmək üçün. Belə ki, sizə kömək edir əsas var Burada fərq xatırlayıram. Seçki sort, bu günə qədər, smallest-- bubble tapmaq sort bitişik cüt dəyişdirmək. Biz qonşu cüt dəyişdirmək elementləri onlar əgər olan səmərəli qaydada həyata , sağ böyük elementləri Bubbles və eyni zamanda bu da başlayır sol kiçik elementləri hərəkət etmək. ən pis halda hal run vaxt bubble növ n kvadrat edir. Ən yaxşı halda run vaxt bubble sort n edir. Çünki ki, vəziyyət biz həqiqətən deyil biz lazımdır bilər hər hansı svopları edir. Biz yalnız bir etmək lazımdır bütün n elementləri arasında keçir. 

Durub sort, Burada əsas fikir dəyişir. Bu durub sırala üçün söz var. Biz vasitəsilə bir dəfə addım olacaq olan array soldan sağa. Biz kimi, biz istəyirik elementləri keçmək gedir Biz artıq üçün otaq etmək gördüm haradasa uyğun lazımdır kiçik olanları geri sıralanır hissəsi. Beləliklə, biz sıralanır array qurmaq bir soldan sağa bir zamanda element, və biz otaq etmək şeyi keçmək. ən pis halda run vaxt durub sort n kvadrat edir. Ən yaxşı halda run zaman n edir. 

Söz sort Birleştirme burada split və daxil edilir. Biz olsun, tam array split bu altı elementləri, səkkiz elementləri var, 10.000 elementləri biz split aşağı yarısında, yarım, yarım, biz array altında qədər n bir element seriallarda. N bir element seriallarda toplusu. Beləliklə, biz bir ilə başladı 1000-element array, və biz nöqtəsinə almaq biz 1000-element Diziler var. Sonra biz həmin sub serialların daxil başlayır geri birlikdə düzgün qaydada. Beləliklə, biz iki bir-element serialların almaq və iki element sıra yaratmaq. Biz iki-element Diziler almaq və dörd element sıra yaratmaq və s və s biz sizin qədər daha bir n element array yenidən. 

ən pis halda run vaxt sort daxil n dəfə n daxil olun. Biz n elementləri var, amma bu recombining proses daxil edir n addımlar almaq üçün tam array geri. vaxt run ən yaxşı halda da n log edir n bu proses həqiqətən deyil, çünki array olub qayğı sıralanır və ya ilə başlamaq. proses var, eyni qısa qapanma şeylər üçün heç bir yol. Belə ki, n ən pis halda n log, n ən yaxşı halda n daxil olun. 

Biz iki haqqında danışdı alqoritmlər axtarış. Belə ki, xətti axtarış iterating edir. Biz array arasında davam bir dəfə, soldan sağa, sayı tapmaq üçün çalışırıq ki, biz aradığınız. ən pis halda run zaman n böyük O edir. Bu iterating bizi bilər hər bir element üzrə biz aradığınız element tapmaq üçün, ya son mövqe, və ya bütün. Amma biz qədər təsdiq edə biz hər şeyi baxdı etdik. ən yaxşı halda deyiləm, biz dərhal tapa bilərsiniz. ən yaxşı halda run vaxt xətti axtarış 1 omega edir. 

Nəhayət, ikili axtarış var idi olan müxtəlif array tələb edir. Ki, bir çox var saxla mühüm baxılması Binar axtarış ilə iş zamanı. Bu pseudocode istifadə bir ön şərt var Siz vasitəsilə aradığınız array sıralanır olmalıdır. Əks halda, söz parçala və fəth edir. Yarısı daxil array Split və elementlərin yarım aradan qaldırılması hər dəfə vasitəsilə davam kimi. Çünki bu uçurum və fəth və yarım yanaşma parçalanması şeyi, ən pis halda run vaxt ikili axtarış əhəmiyyətli dərəcədə olan, n log xətti axtarış nin n daha yaxşı. Ən yaxşı halda run zaman hələ biridir. 

Biz dərhal tapa bilərsiniz İlk dəfə biz bir bölmə, lakin yenə unutmayın ki ikili axtarış, baxmayaraq ki, xətti axtarış nisbətən əhəmiyyətli dərəcədə daha yaxşı log olmanın gərəyi n n qarşı, iş vasitəsilə getmək üçün ola bilər , ilk array çeşidlənməsi hansı asılı olaraq az effektiv edə bilər sıralaması iterating ölçüsü. 

Mən Doug Lloyd deyiləm, bu CS50 edir.