>> MARK GROZEN-Smith: Szia, én vagyok Mark Grozen-Smith, és ez gyorsrendezés.
Csakúgy, mint a beillesztés sort és a buborék sort, a gyors-egy algoritmus
rendezés a lista, vagy egy sor dolgot.
Az egyszerűség kedvéért tegyük fel, hogy ezeket a a dolgok csak egész számok, de
tudják, hogy a gyors dolgozik több, mint csak számok.
Ez a menüpont egy kicsit bonyolultabb mint a beillesztés vagy buborék, de
is sokkal hatékonyabb a legtöbb esetben.
Várj egy percet.
Csak nem azt, hogy "a legtöbb esetben, a "nem" minden "?
Érdekes módon, nem.
Nem minden esetben azonosak.
Ne aggódj ezt a részletet, ha Nem láttam a nagy O jelölés még, de
Gyors-O (n négyzetes) algoritmus a legrosszabb esetben, mint
beillesztés vagy bubble sort.
Azonban ez általában sokkal jár mint egy régi analóg m algoritmus.
Miért?
Majd menj vissza később.
De most, most csak tanulni hogyan gyorsrendezés elvét.
>> Szóval séta Quicksorting ezt tömb egész szám legkisebb
a legnagyobb.
Itt van az egész 6 5, 1, 3, 8, 4, 7, 9 és 2.
Először is, vedd az utolsó eleme ezt a tömböt - ebben az esetben a két -
és hívja, hogy a "pivot". Következő, elkezdi nézni két dolgot -
egy, a legkisebb index, amit majd hivatkozni hogy tartózkodik a jobbra
a fal, és a két, a bal szélső elem, amely hívom a "jelenlegi
elem. "mit fogunk csinálni a meg az összes többi elem, egyéb
, mint a pivot, és tegye az összes elemet kisebb, mint az, hogy az elforduló
balra a fal és minden nagyobb, mint a pivot a
jobbra a falon.
Aztán végül dobjuk a pivot közvetlenül a falra, hogy tedd között
összes szám kisebb, mint és az összes nagyobb számok.
>> Így csináljuk.
Vedd fel a 2., tedd a falra a elején, és hívja a 6. a "jelenlegi
elem. "Ezért szeretnénk nézni a jelenlegi elem, a 6..
És mivel ez nagyobb, mint a 2, hagyjuk ott a
jobbra a falon.
Aztán megyünk tovább nézni az 5, mint a mi aktuális elem, és látom, hogy ez a
van, ismét, nagyobb, mint a pivot, ezért hagyja, ahol a jobb oldalon
oldalán a fal.
Tovább kell lépnünk.
A jelenlegi elem Most 1 és - ó.
Ez most más.
Az aktuális elem már kisebb, mint a A pivot, ezért szeretnénk, hogy azt
a bal oldalon a fal.
Ehhez nézzük csak be kell kapcsolnia a aktuális elem a legalacsonyabb index
ül csak jobbra a falon.
Most megyünk a falnak fel egy index így az 1 a bal oldalon
oldalán a fal most.
>> Várjon.
Én csak összekeverte az elemeket a jobb oldalon a fal, nem igaz?
Ne aggódj.
Ez rendben van.
Az egyetlen dolog, amit érdekel most az, hogy ezeket az elemeket a
a fal jobb nagyobbak mint a pivot.
Nem aktuális rendelés feltételezzük még.
>> Most vissza a válogatás.
Tehát tovább néztem a többi elem.
És ebben az esetben, azt látjuk, hogy vannak más elemeket nem kevesebb, mint a
pivot, így hagyjuk őket a a jobb oldalán a fal.
Végül eljutunk az aktuális elem és látom, hogy ez a pivot.
Nos, ez azt jelenti, hogy a két szakaszok a tömb, az első lény
kicsi a pivot és a bal oldali a fal, és a második lény
nagyobb, mint a pivot a jobb oldalán a fal.
Azt szeretnénk, hogy a pivot elem között A két, és akkor tudjuk, hogy
hogy a pivot annak megfelelő végső rendezett helyen.
Így kapcsolja az első elem a jobb oldalán a fal a pivot,
és tudjuk, hogy a pivot a annak megfelelő pozícióba.
>> Ezután ismételje meg ezt a folyamatot a subarrays bal és jobb a pivot.
Mivel az utolsó csak egy subarray elem hosszú, tudjuk, hogy ez már
rendezett, mert hogy lehet ki rendelni, ha csak az egyik eleme?
A jobb oldalon a subarray, mi látni, hogy a pivot értéke 5, és a fal
csak maradt a 6.
És az aktuális elem is indul ki, mint a 6.
Tehát 6 nagyobb, mint 5.
Hagyjuk ott, ahol ez a jobb oldalán a fal.
Most, mozgó, 3 kisebb, mint 5.
Így kapcsolja az első elem csak jobb a fal.
Most költöztem a fal fel egy.
Most mozog a 8.
8 nagyobb, mint 5, és így hagyjuk.
A 4 kevesebb, mint 5, úgyhogy kapcsolja.
És.
>> Minden alkalommal, amikor ismételje meg a folyamatot a bal és jobb oldalán a tömb. mi
válasszon egy pivot, és nem az összehasonlítás és hozzon létre egy másik szintje a bal-és
jobb subarrays.
Ez a rekurzív hívás addig folytatódik, amíg elérjük a végét, amikor már
felosztották a teljes tömb csak subarrays hosszúságú 1.
Onnan tudjuk, hogy a tömb rendezve mert minden elem, a
Valamikor volt a pivot.
Más szóval, minden elem, minden A számok a bal oldalon kisebb
értékek és a számokat, hogy a joga van a nagyobb érték.
>> Ez a módszer nagyon jól működik, ha a értéke a pivot választott
hozzávetőleg a közepén tartománya a lista értékeket.
Ez azt jelenti, hogy, miután mozgunk elemek körül, ott körülbelül annyi
elemeket, hogy a bal oldalon a forgócsap mint ahány jobbra.
És az oszd meg és uralkodj jellege Gyors-algoritmus ezután venni
teljes mértékben kihasználják.
Ez létrehoz egy futásidejű O (n log n) n, mert meg kell tennünk n mínusz 1
összehasonlítások minden generáció és log n mert meg kell osztani a lista
log n-szer.
Azonban, a legrosszabb esetben ez algoritmus is lehet O (n
négyzeten.) Tegyük fel, minden nemzedék, A pivot csak azért történik, hogy a
a legkisebb, illetve a legnagyobb a számok vagyunk válogatás.
Ez azt jelentené, összeomlanak a listán n-szer és a döntéshozatalban n mínusz 1
összehasonlítást minden egyes alkalommal.
Így o n a négyzeten.
>> Hogyan lehet javítani a módszer?
Egy jó módja annak, hogy javítsák a módszer csökkenteni a valószínűségét, hogy
Az üzemidő valaha is o n a négyzeten.
Ne feledje, ez a legrosszabb, legrosszabb esetben csak akkor történhet meg, ha a
forgócsap választott mindig a legmagasabb vagy a legalacsonyabb érték a tömbben.
Annak érdekében, hogy ez a kevésbé valószínű, hogy megtörténjen, megtaláljuk a pivot a
kiválasztása több elemet és figyelembe véve a medián értéket.
>> A nevem Mark Grozen-Smith, és ez a CS50.
>> Az egyszerűség kedvéért tegyük fel, hogy ezeket a a dolgok csak egész számok, de
tudják, hogy Quicksert -
Quicksert?
Bocsánat.
>> Itt van az egész 6, 5, 1, 3, 8, 4, 9.
>> SPEAKER 1: Tényleg?
>> SPEAKER 2: nem állnak meg ott.
>> SPEAKER 1: Tényleg?