[Музички] 

Даг LLOYD: Добро, па спој вид е уште еден алгоритам кои може да се користат да се најде решение елементите на низата. Но, како што ќе видиме, тоа е се здобија со многу фундаментална разлика од селекцијата вид, меур вид, и вметнување вид кои го прават тоа навистина прилично паметни. 

Основната идеја зад спојување вид е да се најде решение за помали низи а потоа се комбинираат тие низи заедно, или се спојуваат them-- оттука name-- во по некаков ред. Начинот на кој се спојуваат вид не ова е од проширува алатка наречена рекурзија, што е она што ние ќе треба да се зборува за наскоро, но ние не сме навистина разговаравме за уште. 

Тука е основната идеја зад спојат вид. Сортирање на левата половина од низа, под претпоставка дека n е поголемо од 1. И на што мислам кога велам под претпоставка дека n е поголемо од 1 е, Мислам дека можеме да се согласуваат дека ако низа само се состои од еден елемент, тоа се подредени. Ние всушност не се потребни да се направи нешто со неа. Ние само може да ја прогласи за да се решат. Тоа е само еден елемент. 

Па pseudocode, повторно, е сортирање на левата половина од низа, потоа се најде решение за десната половина на низата, тогаш се спојат двете половини заедно. Сега, веќе може да биде размислување, тој вид на само звучи како да сте ставање надвор the-- вие не сте, всушност, не прават ништо. Ти си велејќи средиме лево половина, сортирање на десната половина, но ти не си кажува ми како сте го прави тоа. 

Но, се сеќавам дека се додека низа е еден елемент, можеме да ја прогласи за подредени. Тогаш ние само може да ги комбинираат заедно. А тоа е, всушност, Основната идеја зад спојат вид, е да го срушат, така што Вашиот низи се на големината на еден. А потоа ќе се обнови од таму. 

Спојат вид е дефинитивно комплициран алгоритам. И тоа е исто така малку комплицирано да се претстави. Па се надевам, визуелизација дека јас го имаме тука ќе ви помогне да го следат заедно. А јас ќе се обидам моето најдобро да се раскажуваат работи и да продолжи во текот на оваа малку повеќе побавно од останатите само да се надевам дека ја добиете вашата глава околу идеите зад спојат вид. 

Па ние имаме иста како низа други сортирање алгоритам видеа ако сте виделе them-- шест елемент низа. И нашите pseudocode код овде е вид левата половина, сортирање на десната половина, се спојат двете половини заедно. Значи, да се земе овој многу темно црвена цигла низа и да најде решение на левата половина од тоа. 

Па сега за сега, ние ќе да се игнорира работи на десната страна. Тоа е таму, но ние сме Сепак, тоа не по чекор. Ние не сме во вид на Десната половина на низата. Ние сме во вид на левата половина на низата. И само за доброто да се биде малку повеќе јасни, па затоа може да се однесува на она што ние сме на чекор, Одам да го вклучите боја на овој сет на портокал. Сега, ние сме сè уште зборува за исто левата половина од оригиналната низа. Но, се надевам дека со тоа што се во можност да се однесуваат на боите на разни предмети, тоа ќе се направи тоа малку повеќе јасно што се случува овде. 

Добро, па сега имаме три елемент низа. Како ние да се најде решение на левата половина од оваа низа, која се уште е овој чекор? Ние се обидуваме да се најде решение за левата половина од црвена цигла array-- на левата половина од кои Јас сум сега обоени портокалово. 

Па, ние би можеле да се обидат и да повтори овој процес одново. Значи ние сме се уште во средината на обидува да најде решение левата половина од полното низа. На левата половина од низа, јас сум само ќе да се произволно да одлучи дека левата половина ќе бидат помали од десната половина, затоа што тоа се случи со се состои од три елементи. 

И така јас ќе одам да се каже дека левата половина на левата половина на низата е само елемент пет. Пет, што е еден елемент низа, ние знаеме како да го средиме. И така пет се подредени. Ние сме само ќе да се изјасни дека. Тоа е еден елемент низа. 

Па ние сега сме подредени левата половина од левата half-- или подобро кажано, ние сме подредени левата половина од портокал. Па сега, со цел да се заврши уште левата половина од вкупната низа е, ние треба да се најде решение за десната половина од портокал, или овие работи. Како го правиме тоа? Па, ние имаме две елемент низа. За да можеме да се најде решение за левата половина на низата, што е за два. Две е еден елемент. Така, тоа е сортирана по дифолт. Тогаш можеме да се најде решение за десната половина на тој дел од низата, еден. Тоа е вид на стандардно. 

Ова сега е прв пат ние сме достигна чекор на спојување. Ние имаат завршено, иако ние сме сега вид на вгнездени down-- и тоа е вид на слабо работа со рекурзија е, што треба да ги задржи вашите главата за тоа каде сме. Значи ние сме вид на лево половина од портокал дел. 

И сега, ние сме во средината на сортирање на десната половина од портокал дел. И во тој процес, ние сме сега за да биде на чекор, се спојат двете половини заедно. Кога ќе ги погледнеме двете половини на низата, гледаме две и еден. Кој елемент е помал? Еден. 

Тогаш кој елемент е помал? Па, тоа е два или ништо. Така, тоа е два. Па сега, само за да повторно ги обликувате каде се наоѓаме во контекст, ние сме подредени левата половина од портокал и десната половина на потекло. Знам дека сум смени боите повторно, но тоа е каде што бевме. А причината Го направив ова е затоа што овој процес е ќе се насочи, процесирањето надолу. Ние сме подредени по левата половина од поранешниот портокал и десната половина на поранешниот портокал. 

Сега, ние треба да се спојат овие две половини заедно премногу. Тоа е чекор сме на. Значи ние ги разгледа сите на елементи кои сега се зелени, на левата половина од оригиналната низа. И ние се спојат тие користење на истиот процес ние го сторивме за спојување на две и пред една само еден миг. 

Левата половина, најмалиот елемент на левата половина е пет. Најмалиот елемент на десната половина е еден. Која од овие е помал? Еден. 

Најмалиот елемент на левата половина е пет. Најмалиот елемент на десната половина е два. Што е најмалата? Две. А потоа и на крај и пет ништо, можеме да кажеме пет. 

Добро, така што големата слика, ајде земе пауза за една секунда и да дознаам каде што сме. Ако почнавме од На самиот почеток, ние сега имаат завршено за целокупниот спектар само еден чекор од кодот pseudocode тука. Ние сме подредени левата половина од низа. 

Потсетиме дека оригиналот цел имала пет години, два, еден. Со одење преку овој процес и гнездење надолу и повторување, продолжува да се пробие на проблемот долу во помали и помали делови, ние сме сега заврши чекор еден од pseudocode за целата почетна низа. Ние сме подредени левата половина. 

Па сега ајде да се замрзне таму. И сега ајде да се најде решение за правото половина од оригиналната низа. И ние ќе треба да го направите тоа со минуваат низ истите итеративен Процесот на распарчување работите надолу и потоа да ги спојуваат заедно. 

Па на левата половина од црвена, или на левата половина на десната половина од оригиналната низа, јас ќе одам да се каже е три. Повторно, јас сум тука за да се биде доследен. Доколку имате некоја чудна број на елементи што, навистина не е важно дали ќе се направи остави еден помал или правото една помала. 

Она што е важно е дека секогаш кога ќе судрите со овој проблем во спроведување на спојување, што треба да биде конзистентна. Можете или секогаш треба да направи од левата страна се помали или секогаш треба да се направи На десната страна помала. Еве, јас сум избран да секогаш направи на левата страна помали кога мојот низа, или мојот под-низа, е непарен големина. 

Три е еден елемент, и така се подредени. Ние сме балон таа претпоставка во текот на целата наша процесот досега. Па сега ајде да се најде решение за правото половина на десната половина, или на десната половина на црвено. 

Повторно, ние треба да се подели ова долу. Ова не е еден елемент низа. Ние не можеме да ја прогласи за подредени. И така, прво, ние си оди за сортирање на левата половина. 

Левата половина е еден елемент, па тоа е вид на стандардно. Тогаш ние ќе треба да се најде решение за правото половина, што е еден елемент. Тоа е сортирана по дифолт. А сега, можеме да се спојат овие две заедно. Четири е помала, и потоа шест е помала. 

Повторно, што сме направиле во овој момент? Ние сме подредени по левата половина на десната половина. Или да се вратам на оригиналот бои, кои беа таму, ние сме подредени по левата половина од помек црвено. Тоа беше првично темна тула црвени и сега е помек црвена, или тоа беше помек црвено. 

А потоа ние сме подредени десната половина на помек црвено. Сега, добро, тие се зелени, повторно, токму затоа што ние сме минува низ процесот. И ние треба да се повторува оваа одново и одново. 

Па сега ние може да се спојат овие две половини заедно. И тоа е она што го правиме тука. Па на црна линија само поделен на левата половина и десната половина од овој вид дел. 

Ние се споредат најмалата вредност на левата страна од array-- или, извинете, најмалите вредноста на левата половина до најмалите вредноста на правото пол и да се најде дека три е помала. И сега малку на оптимизација, нели? Има всушност ништо оставени на левата страна. 

Нема ништо останатите на левата страна, за да можеме да ефикасно само move-- ние да се прогласиме остатокот од тоа е, всушност, сортирани и само да го тактика натаму, бидејќи нема ништо на друго место да се споредат против. И знаеме дека на десната страна на десната страна е сортирана. 

Добро, па сега ајде да замрзне повторно и дознаам каде сме ние во приказната. Во целокупниот спектар, Што постигнавме? Ние сме всушност се постигне сега ги чекорите од еден и два чекор. Ние подредени левата половина, и ние подредени десната половина. 

Па сега, она што останува е за нас да се спојат овие две половини заедно. Значи ние се споредат најниска вредност елемент на секоја половина на низата од своја страна и да се продолжи. Една од нив е помалку од три, па оди. 

Две е помалку од три, па два оди. Три е помал од 5, па три оди. Четири е помал од 5, па четири оди. Потоа пет помалку од шест, и шест е се што остана. 

Сега, знам, тоа беше многу чекори. И ние сме остави многу меморија во нашата ситуација. И тоа е она што тие се во сивата плоштади. И тоа веројатно се чувствува како што требаше многу подолго од вметнување вид, меур вид, или селекција вид. 

Но, всушност, затоа што Многу од овие процеси се случуваат во исто time-- што е нешто што нема, повторно, зборуваме кога зборуваме за рекурзија во иднина video-- овој алгоритам, всушност, јасно е фундаментално различен од сè ние сме виделе досега но исто така е значително поефикасно. 

Зошто е тоа? Па, во најлош сценарио, имаме да се подели n елементи нагоре и потоа да ги здружат. Но, кога ќе се здружат нив, она што го правиме во основа е удвојување на големина на помал низи. Имаме еден куп на еден елемент низи што можеме ефикасно комбинираат во две елемент низи. А потоа ние ги преземат тие две елемент низи и ги комбинираат заедно во четири елемент низи, и така натаму, и така натаму, и така натаму, се додека не имаат единствен n елемент низа. 

Но, колку doublings е потребно за да се дојде до n? Сетам на пример телефонот книга. Колку пати ние треба да се искине телефонот книга на половина, колку повеќе пати ние треба да се искине книгата на телефонот на половина, ако големината на телефонот книга двојно се зголеми? Има само еден, нели? 

Значи има некој вид на логаритамски елемент тука. Но, ние, исто така, се уште треба да се најмалку се погледне во сите на n елементи. Значи, во најлош случај, спојат вид работи во n log n. Ние треба да се погледне во сите од n елементи, и ние треба да ги комбинирате заедно со најавите n комплети на чекори. Во најдобар случај, низата е совршено подредени. Тоа е супер. Но врз основа на алгоритам имаме тука, ние се уште треба да се подели и да се здружат. Иако во овој случај, рекомбинирачките е вид на неефикасни. Тоа не е потребно. Но ние се уште одат преку целиот процес во секој случај. 

Значи во најдобар случај а во најлош случај, овој алгоритам работи во n log n време. Спојат вид е дефинитивно малку сложени да ја формира од другите главни алгоритми за сортирање ние разговаравме за CS50 но е значително помоќни. 

И така, ако некогаш сте се најде повод за тоа се потребни или да го користат за да се најде решение на голема група на податоци, добивање вашата глава околу идејата на рекурзија ќе биде навистина моќна. И тоа се случува да се направи вашето програми навистина многу поефикасно користење спојат вид наспроти било што друго. Јас сум Даг Лојд. Ова е CS50.