>> 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.