Дъг LLOYD: Така че в CS50 сме научили за разнообразие от сортиране и търсене алгоритми. И понякога то може да бъде малко трудно да се запази следите какво алгоритъм какво прави. Имаме наистина само обезмаслено повърхността прекалено, има много други търсене и сортиране алгоритми. Така че в това видео нека Просто отделете няколко минути, да се опита да дестилират всеки алгоритъм надолу към нейните основни компоненти така че можете да се помни най-много важна информация за тях и да може да артикулира разлики, ако е необходимо. 

Първият е за избор на сортиране. Основната идея на подбора на сортиране се намери най-малката е сортиран елемент в масив и да го сменяте с Първият елемент от сортиран, че масив. Ние казахме, че в най-лошия случай време на протичане на това е N квадрат. А ако искате да си припомним защо, вземете Един поглед към избор на сортиране на видеото. Времето на най-добрия случай тече и п е квадрат. 

Bubble сортиране, идеята зад това едната е да суап съседни двойки. Така че това е ключът, който ви помага не забравяйте разликата тук. Избор на подреждане е, че досега намерите smallest-- балон Сортът е суап съседни двойки. Ние суап съседни двойки на елементи, ако са извън строя, което ефективно мехурчета по-големи елементи на правото, и в същото време тя започва също да се движат по-малки елементи от ляво. Времето случай продължава, Най-лошият на метод на мехурчето се п квадрат. Времето на най-добрия случай тече на метод на мехурчето е п. Защото в тази ситуация ние не actually-- ние не може да се наложи да прави никакви суапове на всички. Ние само трябва да се направи една мине през всички наш елементи. 

В сортиране чрез вмъкване, на основната идея тук се измества. Това е ключовата дума, за сортиране чрез вмъкване. Отиваме да се оттегли, след като през масива от ляво на дясно. И както го правим, ние сме ще измести елементи ние вече сме виждали да направи място за по-малки такива, които трябва да се вмести някъде обратно в които сортирани порция. Така че ние се изгради сортиран масив една елемент в даден момент, от ляво на дясно, и ние се измести неща, за да направи място. Времето най-лошия случай на изтичане на сортиране чрез вмъкване е п квадрат. Времето на най-добрия случай тече, е п. 

Обединяване sort-- ключова дума тук се разделя и се сливат. Разделяме предлага пълната гама, независимо дали това е шест елемента, осем елемента, 10000 elements-- ние ги разделим определени от половината, от половината, от половината, докато имаме под масив п един елемент масиви. Набор от п един елемент масиви. Така че ние започнахме с една 1000-масив, и стигнем до точката, където ние имаме 1000 един елемент масиви. След това ние започваме да се слеят тези под масиви отново заедно в правилния ред. Така че ние се две една-елементни масиви и създаде две масив. Ние приемаме два дву-елементни масиви и да се създаде четири елемент на масив и така нататък и така нататък, докато ние сме отново възстановен една п масив. 

Времето най-лошия случай на изтичане на сортиране чрез сливане е п пъти вляза п. Имаме наш елементи, но този процес рекомбиниране отнема влезте п стъпки, за да получите резервно до пълен спектър. В най-добрия случай тече време е и п дневник п, защото този процес не е така наистина интересува дали масива е сортирано или не да се започне с. Методът е същият, има Няма начин да кратки неща верига. Така че п п влезте в най-лошия случай, п п влезете в най-добрия случай. 

Ние говорихме за двама търсите алгоритми. Така линейно търсене е около итерации. Изхождаме от другата страна на масива веднъж, от ляво на дясно, опитвайки се да намери броя че ние не търсим. В най-лошия случай тече времето е голям O от п. Тя може да ни отнеме итерации през всеки един елемент да намерите елемент, което търсим за, или на последна позиция, или не на всички. Но ние не можем да потвърдим, че до след като видяхме всичко. съм най-добрия случай, ние веднага намери. Времето на най-добрия случай на изтичане на линейно търсене е омега на 1. 

На последно място, не е двоично търсене, която изисква разнообразни масив. Не забравяйте, че е много Важно съображение при работа с двоично търсене. Това е предпоставка за използване на it-- масива, че търсите чрез трябва да бъдат сортирани. В противен случай, ключовата дума е разделяй и владей. Разделяне на масива в половината и премахване на половината от елементите всеки път, като придвижването ви през. Поради това разделяй и владей и разделяне неща в половината подход, времето на най-лошия случай продължава на двоично търсене е влизане N, който е по същество по-добре от п линейно търсене на. Времето на най-добрия случай тече все още е един. 

Бихме могли да го намерят веднага Първият път, когато се направи разделение, но, отново, не забравяйте, че въпреки двоично търсене е значително по-добре от линеен търсене по силата на това дневник п спрямо п, може да се наложи да мине през работата на сортиране вашия масив първата, която може да го направи по-малко ефективни в зависимост от размера на итерации сортирани. 

Аз съм Дъг Лойд, това е CS50.