>> MARK GROZEN-SMITH: Здравейте, аз съм Марк Grozen-Смит, и това е QUICKSORT.
Точно като вмъкване на сортиране и балон сортиране, QUICKSORT е алгоритъм за
сортиране на списък или масив на нещата.
За простота, нека приемем, че тези, неща са просто числа, но
Знам, че QUICKSORT работи за повече от просто числа.
Quickstart е малко по-сложно от момента на вкарване или балон, но това е
също така много по-ефективно в повечето случаи.
Чакай малко.
Каза само да кажа "най- случаи ", а не" всички "?
Интересното е, че не.
Не всички случаи са едни и същи.
Не се притеснявайте за тази подробност, ако Не съм виждал голям O нотация все още, но
QUICKSORT е О (п квадрат) алгоритъм в най-лошия, точно като
вмъкване или балон вид.
Въпреки това, обикновено действа много повече като стара m алгоритъм аналогов.
Защо?
Ние ще се върнем към това по-късно.
Но за сега, нека просто да се научат как работи QUICKSORT.
>> Така че нека да преминете през този Quicksorting набор от числа от малката
до най-големия.
Тук имаме числата 6, 5, 1, 3, 8, 4, 7, 9, и 2.
Първо, ние вземем крайния елемент на този масив - в този случай, два -
и се обадете, че "оста." След това ние започнете да се оглеждате в две неща -
един, най-ниската индекса, които ще се отнасят като пребиваващи на правото на
стената, и две, най-лявата елемент, който ще се обадя в "ток
елемент. "Това, което ще направя, е гледам всички други елементи, други
от центъра на въртене, и постави всички елементи по-малък от въртене към
остави на стената и всички онези, по-голяма от въртене към
дясно на стената.
След това, най-накрая, ще се откажа от въртене точно на тази стена, за да го поставиш между
всички номера по-малки, отколкото и всички числа, по-големи.
>> Така че нека да направим това.
Вземете 2, сложи на стената в започваше, и се обадете на 6 "ток
елемент. "Така че ние искаме да разгледаме сегашната ни елемент, на 6.
И тъй като това е по-голям от 2, ние го остави там до
дясно на стената.
След това, да преминем към погледнем в 5 като ни текущия елемент и да видим, че това
отново е по-голям от въртене, така че го оставите, където тя е от дясната страна
страна на стената.
Продължаваме напред.
Сегашната ни елемент е сега 1, и - о.
Това е различно сега.
Настоящото елемент сега е по-малък от на въртене, така че ние искаме да го кажем
отляво на стената.
За да направите това, нека просто да превключите текущия елемент с най-нисък индекс
седнал точно отдясно на стената.
Сега, ние се движат на стената до един форум така че един е в ляво
страна на стената сега.
>> Изчакайте.
Аз просто смесва на елементи на дясната страна на стената, нали?
Не се притеснявайте.
Това е добре.
Единственото нещо, което ни интересува за сега е, че всички тези елементи към
право на стената са по-големи от оста.
Не действителната цел се приема, все още.
>> Сега, обратно към сортиране.
Така че ние продължаваме да търсим най- останалите елементи.
И в този случай, ние виждаме, че има няма други елементи, по-малко от
въртене, така че можем да ги оставим всичко на от дясната страна на стената.
Накрая стигаме до текущия елемент и да видим, че тя е на въртене.
Сега, това означава, че имаме две части от масива, първата същество
малък на въртене и на лявата страна на стената, и второ същество
по-голяма от въртене към дясната страна на стената.
Ние искаме да се сложи на въртене елемент между на две, а след това ние ще знаем
че оста е в правото си крайния сортиран място.
Така че ние превключите в първия елемент, на базата на дясната страна на стената с шарнир,
и ние знаем, шарнира е в правото си положение.
>> Ние след това повторете този процес за subarrays вляво и вдясно от центъра на въртене.
След последния subarray е само един дълго елемент, ние знаем, че това е вече
сортираните, защото как може да бъдат изложени на поръчате ако сте само един елемент?
За дясната страна на subarray, ние се види, че оста е 5, и стената
е току-що излезе на 6.
И текущия елемент също започва като 6.
Така 6 е по-голямо от 5.
Ние го оставите, където тя е на дясната страна на стената.
Сега, напред, 3 е по-малко от 5.
Така че ние го включите с първия елемент точно на стената.
Сега, аз се премества на стената до един.
Сега, да преминат към 8.
8 е по-голяма от 5, и така ние го напусне.
The 4 е по-малко от 5, така че ние го включите.
И нататък.
>> Всеки път, когато се повтаря същата процедура и Лявата и дясната част на масива. ние
изберете въртене и да направим сравненията и да се създаде ново ниво на ляво и
правилните subarrays.
Това рекурсивно повикване ще продължи до стигаме до края, когато ние имаме
разделен на общия масив в само subarrays с дължина 1.
От там, ние знаем, масивът е сортиран защото всеки елемент има, при
някакъв момент, бил ос.
С други думи, за всеки елемент, всички Числата в ляво са по-малки
ценности и всички номера към нали имат по-големи стойности.
>> Този метод работи много добре, ако стойност на избрания Оста
приблизително в средата диапазон на списък ценности.
Това би означавало, че след като ние се движат елементи около, има толкова много
елементи в ляво на въртене като има надясно.
И разделяй и владей естеството на Тогава QUICKSORT алгоритъм е взета
възползват напълно от.
Това създава по време на работа на O (п влезете п) н, защото ние трябва да направим п минус 1
сравнения на всяко поколение и дневник н, защото ние трябва да се разделят на списъка
влезете N пъти.
Въпреки това, в най-лошия случай, този алгоритъм може действително да бъде O (N
квадрат.) Да предположим, на всяко поколение, шарнира просто така се случва да бъде най-
най-малкото или най-голямото от номера сме сортиране.
Това би означавало да се счупи списъка N пъти и Правене N минус 1
сравнения всеки път.
По този начин, о п квадрат.
>> Как можем да подобрим метода?
Един добър начин за подобряване на метода е за ограничаване на вероятността, че
по време на работа е някога действително о п квадрат.
Запомнете това най-лошия, най-лошия сценарий може да се случи само когато
въртене избран е винаги най-високите или най-ниската стойност в масива.
За да се гарантира, че това е по-малко вероятно да се случи, ние можем да намерим на въртене от
избирате множество елементи и като средната стойност.
>> Моето име е Марк Grozen-Smith, и това е CS50.
>> За простота, нека приемем, че тези, неща са просто числа, но
Знам, че Quicksert -
Quicksert?
Извинете.
>> Тук имаме числа 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Наистина ли?
>> SPEAKER 2: Да не се спира дотук.
>> SPEAKER 1: Наистина ли?