>> МАРК GROZEN-Смит: Здраво, јас сум Марк Grozen-Смит, и ова е Quicksort.
Исто како и вметнување вид и меур вид, Quicksort е алгоритам за
сортирање листа или низа на работи.
За едноставност, да претпоставиме дека оние работи се само цели броеви, но
знаете дека Quicksort работи за повеќе од само бројки.
Quickstart е малку повеќе комплицирано од вметнување или балон, но тоа е
исто така многу поефикасно во повеќето случаи.
Чекај една секунда.
Дали тој само велат "повеќето случаи, "не" сите "?
Интересно, бр.
Не сите случаи се исти.
Не грижете се за овој детал ако не сум ја видел голема О нотација уште, но
Quicksort е О (n квадрат) алгоритам во најлош случај, исто како и
вметнување или балон вид.
Сепак, тоа обично делува многу повеќе како старите аналогни метри алгоритам.
Зошто?
Ние ќе се вратам на тоа подоцна.
Но, за сега, ајде да дознаете како Quicksort работи.
>> Па ајде да одиме преку Quicksorting овој низа од цели броеви од најмалите
на најголемата.
Тука имаме цели броеви 6, 5, 1, 3, 8, 4, 7, 9, и 2.
Прво, ние го избере конечниот елемент на оваа низа - во овој случај, две -
и повик дека "стожерот". Следниот, ние почнете да се погледне две работи -
еден, што е најниско индекс, кој ќе се однесува како престојуваат на правото на
ѕидот, и две, најлева елемент, кој ќе викнам "тековната
елемент. "Она што се случува да направите е изгледа сите други елементи, други
од стожерот, и го стави сите елементи помал од стожерот на
лево од ѕидот и сите оние поголема од стожерот на
правото на ѕидот.
Потоа, конечно, ќе се намали на стожерот право на тој ѕид да го стави меѓу
сите броеви помали од тоа и сите броеви поголеми.
>> Па ајде направите тоа.
Ги собереш на 2, се стави на ѕидот на на почетокот, и повик на 6 "тековната
елемент. "Значи, ние сакаме да се погледне нашите сегашни елемент, 6.
И бидејќи е поголем од 2, ние да го оставиме таму на
правото на ѕидот.
Тогаш, ние се движат да се погледне на 5 како наш тековниот елемент и да види дека оваа
е, пак, поголеми од стожерот, па ние оставете го таму каде што е на десната
страна на ѕидот.
Ние се движат натаму.
Нашата актуелна елемент е сега 1, и - ох.
Ова е различно сега.
Тековниот елемент е сега помал од стожерот, затоа сакаме да го стави
од лево на ѕидот.
Да го направите ова, ајде да се префрлат на тековниот елемент со најниска индекс
седи само на правото на ѕидот.
Сега, ние се движат на ѕидот до еден индекс па 1 се наоѓа на левата
страна на ѕидот сега.
>> Чекаат.
Јас само измешани елементи на десната страна на ѕидот, не јас?
Не грижете се.
Тоа е во ред.
Единственото нешто што се грижат за сега за сега е дека сите овие елементи на
правото на ѕидот се поголеми од стожерот.
Не постојат вистински цел уште се претпоставува.
>> Сега, назад на сортирање.
Па ние продолжи да гледа во остатокот од елементи.
И во овој случај, можеме да видиме дека постојат нема други елементи помалку од
стожерот, па сите ние ги остават на на десната страна на ѕидот.
Конечно, ние се дојде до тековниот елемент и види дека тоа е стожерот.
Сега, тоа значи дека имаме две делови од низа, првиот суштество
мали на стожерот и на левата страна на ѕидот, а втората е
поголема од стожерот на десно на ѕидот.
Ние сакаме да се стави на стожерот елемент помеѓу две, а потоа ќе знаеме
дека стожерот е во право конечна сортирани место.
Па ние се префрлат на првиот елемент на десно на ѕидот со стожерот,
и знаеме стожерот на во својата право позиција.
>> Тогаш ние го повторите овој процес за subarrays лево и десно на стожерот.
Од последните subarray е само еден елемент долго, ние знаеме дека е веќе
сортирани бидејќи како може да биде надвор од нарачате ако сте само еден елемент?
За десната страна на subarray, ние види дека стожерот е 5, и ѕидот
е само лево од 6.
И тековниот елемент, исто така, започнува како 6.
Така 6 е поголема од 5.
Ние го оставиме тоа каде што е на десно на ѕидот.
Сега, да се пресели на, 3 е помал од 5.
Па ние го префрлат со првиот елемент само правото на ѕидот.
Сега, јас се пресели на ѕидот до една.
Сега, да се пресели на 8.
8 е поголема од 5, и така ние го оставиме тоа.
4 е помал од 5, па ние го вклучите.
И натаму.
>> Секој пат кога ние го повторуваме процесот на левата и десната страна на низата. ние
изберете стожерот и прават споредби и да се создаде едно друго ниво на лево и
право subarrays.
Овој рекурзивен повик ќе продолжи се додека стигнавме до крајот кога ние сме
поделена на целокупниот спектар на само subarrays должина 1.
Од таму, ние знаеме низата е сортирана затоа што секој елемент има,
одреден момент, е стожерот.
Со други зборови, за секој елемент, сите на бројки на лево се помалку
вредности и сите броеви на право да имаат поголема вредност.
>> Овој метод работи многу добро ако вредноста на стожерот избран е
приближно во средината опсег на листата вредности.
Ова би значело дека, откако ќе се движат елементи наоколу, има за онолку
елементи од лево на стожерот како што постојат кон десно.
И поделбата-и-ја освои природата на Quicksort алгоритам потоа се земени
целосно искористување на.
Ова создава траење на О (n најавите n,) на n, бидејќи ние треба да се направи N минус 1
споредби на секоја генерација и да се најавите n бидејќи ние треба да се подели на листата
логирате n пати.
Меѓутоа, во најлош случај, овој алгоритам всушност може да биде О (n
квадрат.) Да претпоставиме дека на секоја генерација, стожерот само така се случува да биде
Најмалата или најголемиот од броеви ние сме сортирање.
Ова би значело рушење на листа n пати и одлуки n минус 1
споредби секој време.
Така, о н квадрат.
>> Како можеме да се подобри начинот?
Еден добар начин да се подобри начинот е да се намали веројатноста дека
траење некогаш всушност o од n квадрат.
Се сеќавам ова најлош случај, најлошото сценарио само може да се случи кога
стожерот избрана е секогаш на највисоко или најниската вредност во низа.
Да се ​​обезбеди тоа е помалку веројатно да се случи, можеме да најдеме стожерот од
изборот на повеќе елементи и земајќи средна вредност.
>> Моето име е Марк Grozen-Смит, и ова е CS50.
>> За едноставност, да претпоставиме дека оние работи се само цели броеви, но
знаете дека Quicksert -
Quicksert?
Жал.
>> Тука имаме цели броеви 6, 5, 1, 3, 8, 4, 9.
>> ЗВУЧНИК 1: Навистина?
>> ЗВУЧНИК 2: Не завршуваат тука.
>> ЗВУЧНИК 1: Навистина?