Даг Lloyd: Так у CS50 мы даведаліся пра разнастайнасць сартавання і пошуку алгарытмы. І часам гэта можа быць крыху больш складана трымаць трэк, які алгарытм робіць. Мы сапраўды толькі абястлушчанае паверхню таксама Ёсць шмат іншых пошук і алгарытмы сартавання. Такім чынам, у гэтым відэа давайце проста ўзяць некалькі хвілін каб паспрабаваць адагнаць кожны алгарытм да яго асноўных элементаў так што вы можаце памятаць, найбольш важная інфармацыя пра іх і быць у стане сфармуляваць адрозненні, калі гэта неабходна. 

Першы выбар роду. Асноўная ідэя выбару роду гэта знайсці найменшы элемент малокомплектных ў масіве і памяняць яго з у першую чаргу малокомплектных элемент гэтага масіва. Мы сказалі, што ў горшым выпадку запусціць час, што быў н квадраце. І калі вы хочаце, каб успомніць, чаму, узяць Паглядзіце на выбар роду відэа. Час працы лепшым выпадку таксама п квадраце. 

Бурбалка роду, ідэя, што адзін, каб памяняць суседнія пары. Так што гэта ключ, які дапамагае вам запомніць розніцу тут. Выбар роду ёсць, да гэтага часу, знайсці smallest-- бурбалка Сартаваць па-за памяняць суседнія пары. Мы памяняць суседнія пары элементаў, калі яны выйшлі з ладу, які эфектыўна бурбалкі буйныя элементы правы, і ў той жа час яна таксама пачынае для перамяшчэння дробных элементаў налева. Час выканання выпадак найгоршага выпадку бурбалкі сартавання п квадраце. Час працы лепшым выпадку бурбалкі сартавання п. Таму што ў гэтай сітуацыі мы не actually-- мы, магчыма, не трэба рабіць якія-небудзь свопы на ўсіх. У нас ёсць толькі зрабіць адзін прайсці праз усе п элементаў. 

У ўстаўкі роду, то Асноўная ідэя тут мяняецца. Гэта ключавое слова для ўстаўкі роду. Мы збіраемся выйсці адзін раз праз масіў злева направа. І, як мы робім, мы збіраецца перанесці элементы мы ўжо бачылі, каб вызваліць месца для дробныя, што трэба, каб адпавядаць дзесьці таму ў гэтай Сартаваць часткі. Так мы будуем адсартаваны масіў адным элемент, у той час, злева направа, і мы пераходзім рэчы, каб зрабіць пакой. Найгоршы час прабег устаўка сартавання п квадраце. Час лепшы варыянт запуску з'яўляецца н. 

Зліццё sort-- ключавога слова тут падзел і зліццё. Мы падзялілі поўны спектр Ці гэта шэсць элементаў, васьмі элементаў, 10000 elements-- мы падзялілі яго скарацілася ўдвая, удвая, удвая, пакуль у нас пад масіў н адной масіваў элементаў. Набор N Адзін масіваў элементаў. Такім чынам, мы пачалі з аднаго Масіў 1000 элемент, і мы дабрацца да кропкі, дзе мы ёсць 1000 масіваў одноэлементные. Тады мы пачынаем аб'яднаць гэтыя суб масівы разам у правільным парадку. Такім чынам, мы прыняць два масіва одноэлементные і стварыць масіў з двух элементаў. Возьмем два масівы двух элементаў і стварыць масіў з чатырох элементаў і гэтак далей, і гэтак далей, пакуль мы не зноў адноўлены адзін масіў п элементаў. 

Найгоршы час прабег сартаванне зліццём п раз увайсці н. У нас ёсць п элементаў, але гэты працэс рекомбинирующий прымае ўвайсці п крокаў, каб атрымаць вярнуцца да поўнай масіва. У лепшым выпадку час выканання таксама п часопіса п таму што гэты працэс не мае вялікага клапаціцца, ці быў масіў сартавання ці не пачынаць. Працэс той жа, ёсць няма спосаб кароткіх рэчаў выключальнікаў. Так п п увайсці ў горшым выпадку, п п увайсці ў лепшым выпадку. 

Мы гаварылі пра двух алгарытмы пошуку. Так лінейны пошук аб ітэрацыі. Пяройдзем праз масіў адзін раз, злева направа, спрабуючы знайсці нумар што мы шукаем. Час горшы запусціць вялікі вываду п. Гэта можа заняць нам ітэрацыі па кожнай элемента каб знайсці элемент мы шукаем для, альбо ў апошняй пазіцыі, ці не на ўсіх. Але мы не можам пацвердзіць, што да таго часу, мы глядзелі на ўсё. м лепшым выпадку, мы адразу знайсці. Лепшы выпадку час прабег лінейны пошук амега 1. 

Нарэшце, было бінарны пошук, які патрабуе асарці масіў. Памятаеце, што гэта вельмі важным фактарам пры працы з бінарнага пошуку. Гэта з'яўляецца неабходным умовай для дапамогі it-- масіў, што вы шукаеце праз павінны быць адсартаваныя. У адваротным выпадку, ключавое слова гэта падзяляй і ўладар. Спліт масіў напалову і ліквідацыі палова элементаў кожны раз, як вы прайсці праз. З-за гэтага падзяляй і ўладар і падзел рэчаў у палове падыходу, у горшым выпадку час выканання бінарных пошук увайсці н, які, па сутнасці лепш, чым лінейны пошук у п. Час лепшым выпадку працаваць па-ранейшаму адзін. 

Мы маглі б адразу ж знайсці Першы раз мы робім падзел, але, зноў, памятаеце, што хоць двайковы пошук значна лепш, чым лінейны пошук у сілу таго, часопіс N у параўнанні з п, Вы, магчыма, прыйдзецца прайсці праз працу сартавання свой масіў першай, можа зрабіць яго менш эфектыўным у залежнасці на памер ітэрацыі адсартаваныя. 

Я Дуг Лойд, гэта CS50.