>> ŽENKLAS GROZEN-Smith: Sveiki, aš esu Pažymėti Grozen-Smith, ir tai yra QuickSort.
Tiesiog kaip ir įterpimo rūšiuoti ir burbulas rūšiuoti QuickSort yra už algoritmas
rūšiavimas sąrašą arba dalykų masyvo.
Kad būtų paprasčiau, tarkime, kad tie viskas yra tik sveikieji skaičiai, tačiau
žinau, kad QuickSort veikia daugiau nei tik numeriais.
Quickstart yra šiek tiek sudėtingesnis kaip įterpimas ar burbulas, bet tai
Taip pat yra daug veiksmingiau daugeliu atvejų.
Palauk sekundę.
Ar jis tiesiog pasakyti "labiausiai atvejai ", o ne" visi "?
Įdomu tai, kad ne.
Ne visi atvejai yra vienodi.
Nesijaudinkite apie šį išsamiai, jei jums nemačiau didelis O notacijos nėra, tačiau
QuickSort yra O (n kvadratu) algoritmas blogiausiu atveju, kaip
įterpimo arba burbulas rūšiuoti.
Tačiau ji paprastai veikia daug kaip senas analoginis m algoritmas.
Kodėl?
Mes grįžti į vėliau.
Bet dabar, tegul tiesiog išmokti kaip QuickSort veikia.
>> Taigi, galime eiti per Quicksorting tai sveikųjų skaičių masyvas iš mažiausių
iki didžiausio.
Čia mes turime skaičiais 6, 5, 1, 3, 8, 4, 7, 9, ir 2.
Pirma, mes pasirinkti galutinį elementas tai masyvas - šiuo atveju, du -
ir skambinti, kad "suktis". Be to, mes pradėti ieškoti dviejų dalykų -
vienas, žemiausia indekso, kurį aš skaitykite kaip būna su teise
siena, ir du, kairiausias elementas, kurį aš vadinu "dabartinis
elementas. "Ką mes ketiname daryti yra žiūrėti visus kitus elementus, kitus
nei ašies, ir įdėti visus elementus mažesnės nei iki ašies
liko sienos ir visi tie, didesnis nei iki ašies
teisė sienos.
Tada, pagaliau, mes lašas suktis tiesiai ant tos sienos įdėti jį tarp
visi skaičiai mažesni už jį ir visi numeriai didesni.
>> Taigi galime daryti.
Paimkite 2, įdėti siena pradžioje, ir paskambinti į 6 "dabartinė
elementas. "Taigi, mes norime pažvelgti į mūsų dabartinis elementas, 6.
Ir kadangi jis didesnis nei 2, mes palikti jį ten
teisė sienos.
Tada mes pereiti į pažvelgti į 5, nes mūsų dabartinis elementas ir pamatyti, kad tai
, vėlgi, didesnis nei ašies, todėl mes palikti jį ten, kur jis yra dešinėje
pusė sienos.
Mes judėti pirmyn.
Mūsų dabartinis elementas yra dabar 1, ir - oi.
Tai kitokia.
Dabartinis elementas yra dabar mažesnis nei ašis, todėl norime jį
prie sienos kairėje.
Norėdami tai padaryti, tegul tiesiog pereiti dabartinis elementas su mažiausiu indeksas
sėdi tik prie sienos dešinėje.
Dabar mes pereiti sieną iki vieno indeksas taip 1 yra kairėje
pusė sienos dabar.
>> Palaukti.
Aš tiesiog sumaišyti ant elementų Dešinėje pusėje prie sienos, ar ne aš?
Nesijaudinkite.
Tai gerai.
Vienintelis dalykas, mums rūpi dabar yra tai, kad visi šie elementai
teisė sienos yra didesni nei ašies.
Ne faktinis kad prielaida dar.
>> Dabar atgal prie rūšiavimo.
Taigi mes ir toliau ant žiūri elementų poilsio.
Ir šiuo atveju, mes matome, kad yra nėra kitų elementų, mažiau nei
ašis, todėl mes palikti juos visus Dešinėje pusėje sienos.
Galiausiai, mes turime einamųjų elemento ir pamatysite, kad tai yra ašis.
Dabar, tai reiškia, kad mes turime du skyriai masyvo, pirmasis būties
mažas ant ašies ir kairėje pusėje sienos, o antrasis
didesnis nei iki ašies Dešinėje pusėje sienos.
Mes norime įdėti sukimosi elementas tarp du, ir tada mes žinome,
kad ašis yra jo dešinėje galutinis surūšiuoti vieta.
Taigi, mes pereiti pirmąjį elementą Dešinėje pusėje prie sienos su ašies,
ir mes žinome, ašis s savo teisingoje padėtyje.
>> Mes tada pakartokite šį procesą subarrays į kairę ir į dešinę nuo ašies.
Kadangi paskutinis subarray yra tik vienas elementas ilgai, mes žinome, kad tai jau
surikiuota, nes, kaip jūs galite būti iš užsisakyti, jei esate tik vienas elementas?
Dėl dešinėje subarray, mes matyti, kad ašis yra 5, ir sienos
tiesiog liko iš 6.
Ir dabartinis elementas taip pat prasideda kaip 6.
Taigi 6 yra didesnis nei 5.
Mes palikti jį ten, kur jis yra Dešinėje pusėje sienos.
Dabar pereikime prie 3 yra mažesnis nei 5.
Taigi mes vėl jį su pirmojo elemento teisingai sienos.
Dabar, aš persikėlė į sieną dar vieną.
Dabar pereikime prie 8.
8 yra didesnis nei 5, ir todėl palikti jį.
4 yra mažesnis nei 5, tad jį įjungti.
Ir.
>> Kiekvieną kartą, kai mes pakartokite procesą kairysis ir dešinysis kraštai masyvo. mes
pasirinkti suktis ir daryti palyginimus ir sukurti kitą lygį kairėje ir
teisė subarrays.
Tai grįžtamojo skambutis bus tęsiamas tol, kol mes pasiekti pabaigos, kai mes
padalintas į bendrą masyvą į tik subarrays ilgio 1.
Iš ten, mes žinome, masyvas surūšiuotas nes kiekvienas elementas turi ne
Tam tikru momentu, buvo ašis.
Kitaip tariant, kiekvieno elemento, visi į kairę skaičiai yra mažiau
vertybės ir visi iki numeriai teisė turėti didesnes vertes.
>> Šis metodas veikia labai gerai, jei vertė šerdeso pasirinkta
maždaug per vidurį diapazonas sąrašą vertybes.
Tai reikštų, kad, kai mes einame elementai aplink, yra maždaug kaip daug
elementai iš ašies kairėje nes yra į dešinę.
Ir skaldyk ir valdyk pobūdis QuickSort algoritmas tada imtis
visiškai išnaudoti.
Tai sukuria O runtime (n log n) n, nes mes turime daryti n atėmus 1
palyginimams kiekviena karta ir log n, nes mes turime padalinti sąrašą
prisijunkite n kartų.
Tačiau blogiausiu atveju, tai algoritmas iš tikrųjų gali būti O (n
kvadratu.) Tarkime, kiekvieną kartą, suktis tiesiog taip atsitinka, kad
mažiausia arba didžiausia numeriai mes rūšiavimo.
Tai reikštų, skaidyti sąrašą n kartų ir padaryti n atėmus 1
lyginti kiekvieną kartą.
Taigi, o n kvadratu.
>> Kaip mes galime pagerinti metodas?
Vienas geras būdas pagerinti metodas yra siekiama sumažinti tikimybę, kad
Runtime kada nors iš tikrųjų O n kvadratu.
Prisiminti šią blogiausias blogiausiu atveju gali įvykti tik tada, kai
pasirinktas ašis visada yra aukščiausia arba mažiausia reikšmė masyvo.
Siekiant tai užtikrinti yra mažiau tikėtina, kad taip atsitiktų, mes galime rasti suktis pagal
pasirinkti kelis elementus ir atsižvelgiant medianą.
>> Mano vardas yra Markas Grozen-Smith ir tai yra CS50.
>> Kad būtų paprasčiau, tarkime, kad tie viskas yra tik sveikieji skaičiai, tačiau
žinoti, kad Quicksert -
Quicksert?
Atsiprašau.
>> Čia mes turime skaičiais 6, 5, 1, 3, 8, 4, 9.
>> GARSIAKALBIS 1: Tikrai?
>> SPEAKER 2: Negalima sustoti.
>> GARSIAKALBIS 1: Tikrai?