1
00:00:00,000 --> 00:00:07,270

2
00:00:07,270 --> 00:00:10,390
>> ŽENKLAS GROZEN-Smith: Sveiki, aš esu Pažymėti
Grozen-Smith, ir tai yra QuickSort.

3
00:00:10,390 --> 00:00:13,520
Tiesiog kaip ir įterpimo rūšiuoti ir burbulas
rūšiuoti QuickSort yra už algoritmas

4
00:00:13,520 --> 00:00:15,720
rūšiavimas sąrašą arba dalykų masyvo.

5
00:00:15,720 --> 00:00:19,080
Kad būtų paprasčiau, tarkime, kad tie
viskas yra tik sveikieji skaičiai, tačiau

6
00:00:19,080 --> 00:00:22,060
žinau, kad QuickSort veikia
daugiau nei tik numeriais.

7
00:00:22,060 --> 00:00:24,720
Quickstart yra šiek tiek sudėtingesnis
kaip įterpimas ar burbulas, bet tai

8
00:00:24,720 --> 00:00:27,560
Taip pat yra daug veiksmingiau
daugeliu atvejų.

9
00:00:27,560 --> 00:00:28,150
Palauk sekundę.

10
00:00:28,150 --> 00:00:30,760
Ar jis tiesiog pasakyti "labiausiai
atvejai ", o ne" visi "?

11
00:00:30,760 --> 00:00:31,710
Įdomu tai, kad ne.

12
00:00:31,710 --> 00:00:33,560
Ne visi atvejai yra vienodi.

13
00:00:33,560 --> 00:00:36,650
Nesijaudinkite apie šį išsamiai, jei jums
nemačiau didelis O notacijos nėra, tačiau

14
00:00:36,650 --> 00:00:39,730
QuickSort yra O (n kvadratu) algoritmas
blogiausiu atveju, kaip

15
00:00:39,730 --> 00:00:41,430
įterpimo arba burbulas rūšiuoti.

16
00:00:41,430 --> 00:00:44,950
Tačiau ji paprastai veikia daug
kaip senas analoginis m algoritmas.

17
00:00:44,950 --> 00:00:45,750
Kodėl?

18
00:00:45,750 --> 00:00:46,810
Mes grįžti į vėliau.

19
00:00:46,810 --> 00:00:49,610
Bet dabar, tegul tiesiog išmokti
kaip QuickSort veikia.

20
00:00:49,610 --> 00:00:53,080
>> Taigi, galime eiti per Quicksorting tai
sveikųjų skaičių masyvas iš mažiausių

21
00:00:53,080 --> 00:00:54,260
iki didžiausio.

22
00:00:54,260 --> 00:01:00,110
Čia mes turime skaičiais 6,
5, 1, 3, 8, 4, 7, 9, ir 2.

23
00:01:00,110 --> 00:01:03,480
Pirma, mes pasirinkti galutinį elementas
tai masyvas - šiuo atveju, du -

24
00:01:03,480 --> 00:01:06,870
ir skambinti, kad "suktis". Be to, mes
pradėti ieškoti dviejų dalykų -

25
00:01:06,870 --> 00:01:10,220
vienas, žemiausia indekso, kurį aš skaitykite
kaip būna su teise

26
00:01:10,220 --> 00:01:13,970
siena, ir du, kairiausias
elementas, kurį aš vadinu "dabartinis

27
00:01:13,970 --> 00:01:17,260
elementas. "Ką mes ketiname daryti yra
žiūrėti visus kitus elementus, kitus

28
00:01:17,260 --> 00:01:20,930
nei ašies, ir įdėti visus elementus
mažesnės nei iki ašies

29
00:01:20,930 --> 00:01:24,140
liko sienos ir visi tie,
didesnis nei iki ašies

30
00:01:24,140 --> 00:01:25,570
teisė sienos.

31
00:01:25,570 --> 00:01:29,560
Tada, pagaliau, mes lašas suktis
tiesiai ant tos sienos įdėti jį tarp

32
00:01:29,560 --> 00:01:32,970
visi skaičiai mažesni už jį
ir visi numeriai didesni.

33
00:01:32,970 --> 00:01:34,460
>> Taigi galime daryti.

34
00:01:34,460 --> 00:01:38,540
Paimkite 2, įdėti siena
pradžioje, ir paskambinti į 6 "dabartinė

35
00:01:38,540 --> 00:01:41,590
elementas. "Taigi, mes norime pažvelgti į
mūsų dabartinis elementas, 6.

36
00:01:41,590 --> 00:01:44,200
Ir kadangi jis didesnis nei
2, mes palikti jį ten

37
00:01:44,200 --> 00:01:45,610
teisė sienos.

38
00:01:45,610 --> 00:01:48,980
Tada mes pereiti į pažvelgti į 5, nes mūsų
dabartinis elementas ir pamatyti, kad tai

39
00:01:48,980 --> 00:01:51,840
, vėlgi, didesnis nei ašies, todėl mes
palikti jį ten, kur jis yra dešinėje

40
00:01:51,840 --> 00:01:53,190
pusė sienos.

41
00:01:53,190 --> 00:01:53,880
Mes judėti pirmyn.

42
00:01:53,880 --> 00:01:56,750
Mūsų dabartinis elementas yra
dabar 1, ir - oi.

43
00:01:56,750 --> 00:01:58,030
Tai kitokia.

44
00:01:58,030 --> 00:02:00,890
Dabartinis elementas yra dabar mažesnis nei
ašis, todėl norime jį

45
00:02:00,890 --> 00:02:02,570
prie sienos kairėje.

46
00:02:02,570 --> 00:02:06,555
Norėdami tai padaryti, tegul tiesiog pereiti
dabartinis elementas su mažiausiu indeksas

47
00:02:06,555 --> 00:02:07,970
sėdi tik prie sienos dešinėje.

48
00:02:07,970 --> 00:02:14,050

49
00:02:14,050 --> 00:02:17,570
Dabar mes pereiti sieną iki vieno indeksas
taip 1 yra kairėje

50
00:02:17,570 --> 00:02:19,750
pusė sienos dabar.

51
00:02:19,750 --> 00:02:20,310
>> Palaukti.

52
00:02:20,310 --> 00:02:23,450
Aš tiesiog sumaišyti ant elementų
Dešinėje pusėje prie sienos, ar ne aš?

53
00:02:23,450 --> 00:02:23,890
Nesijaudinkite.

54
00:02:23,890 --> 00:02:24,930
Tai gerai.

55
00:02:24,930 --> 00:02:27,570
Vienintelis dalykas, mums rūpi dabar
yra tai, kad visi šie elementai

56
00:02:27,570 --> 00:02:29,570
teisė sienos yra didesni
nei ašies.

57
00:02:29,570 --> 00:02:31,760
Ne faktinis kad prielaida dar.

58
00:02:31,760 --> 00:02:33,200
>> Dabar atgal prie rūšiavimo.

59
00:02:33,200 --> 00:02:35,840
Taigi mes ir toliau ant žiūri
elementų poilsio.

60
00:02:35,840 --> 00:02:39,075
Ir šiuo atveju, mes matome, kad yra
nėra kitų elementų, mažiau nei

61
00:02:39,075 --> 00:02:42,100
ašis, todėl mes palikti juos visus
Dešinėje pusėje sienos.

62
00:02:42,100 --> 00:02:45,980
Galiausiai, mes turime einamųjų elemento
ir pamatysite, kad tai yra ašis.

63
00:02:45,980 --> 00:02:48,830
Dabar, tai reiškia, kad mes turime du
skyriai masyvo, pirmasis būties

64
00:02:48,830 --> 00:02:51,820
mažas ant ašies ir kairėje pusėje
sienos, o antrasis

65
00:02:51,820 --> 00:02:54,500
didesnis nei iki ašies
Dešinėje pusėje sienos.

66
00:02:54,500 --> 00:02:57,040
Mes norime įdėti sukimosi elementas tarp
du, ir tada mes žinome,

67
00:02:57,040 --> 00:03:01,000
kad ašis yra jo dešinėje
galutinis surūšiuoti vieta.

68
00:03:01,000 --> 00:03:04,980
Taigi, mes pereiti pirmąjį elementą
Dešinėje pusėje prie sienos su ašies,

69
00:03:04,980 --> 00:03:06,410
ir mes žinome, ašis s
savo teisingoje padėtyje.

70
00:03:06,410 --> 00:03:11,130

71
00:03:11,130 --> 00:03:15,650
>> Mes tada pakartokite šį procesą
subarrays į kairę ir į dešinę nuo ašies.

72
00:03:15,650 --> 00:03:18,700
Kadangi paskutinis subarray yra tik vienas
elementas ilgai, mes žinome, kad tai jau

73
00:03:18,700 --> 00:03:22,480
surikiuota, nes, kaip jūs galite būti iš
užsisakyti, jei esate tik vienas elementas?

74
00:03:22,480 --> 00:03:28,860
Dėl dešinėje subarray, mes
matyti, kad ašis yra 5, ir sienos

75
00:03:28,860 --> 00:03:32,250
tiesiog liko iš 6.

76
00:03:32,250 --> 00:03:34,970
Ir dabartinis elementas taip pat
prasideda kaip 6.

77
00:03:34,970 --> 00:03:36,200
Taigi 6 yra didesnis nei 5.

78
00:03:36,200 --> 00:03:38,590
Mes palikti jį ten, kur jis yra
Dešinėje pusėje sienos.

79
00:03:38,590 --> 00:03:41,060
Dabar pereikime prie 3 yra mažesnis nei 5.

80
00:03:41,060 --> 00:03:44,160
Taigi mes vėl jį su pirmojo elemento
teisingai sienos.

81
00:03:44,160 --> 00:03:47,944

82
00:03:47,944 --> 00:03:50,750
Dabar, aš persikėlė į sieną dar vieną.

83
00:03:50,750 --> 00:03:53,010
Dabar pereikime prie 8.

84
00:03:53,010 --> 00:03:56,480
8 yra didesnis nei 5,
ir todėl palikti jį.

85
00:03:56,480 --> 00:03:58,720
4 yra mažesnis nei 5, tad jį įjungti.

86
00:03:58,720 --> 00:04:02,950

87
00:04:02,950 --> 00:04:03,570
Ir.

88
00:04:03,570 --> 00:04:04,820
Ir.

89
00:04:04,820 --> 00:04:10,190

90
00:04:10,190 --> 00:04:13,670
>> Kiekvieną kartą, kai mes pakartokite procesą
kairysis ir dešinysis kraštai masyvo. mes

91
00:04:13,670 --> 00:04:17,010
pasirinkti suktis ir daryti palyginimus
ir sukurti kitą lygį kairėje ir

92
00:04:17,010 --> 00:04:18,240
teisė subarrays.

93
00:04:18,240 --> 00:04:21,500
Tai grįžtamojo skambutis bus tęsiamas tol, kol
mes pasiekti pabaigos, kai mes

94
00:04:21,500 --> 00:04:25,290
padalintas į bendrą masyvą į
tik subarrays ilgio 1.

95
00:04:25,290 --> 00:04:28,060
Iš ten, mes žinome, masyvas surūšiuotas
nes kiekvienas elementas turi ne

96
00:04:28,060 --> 00:04:29,330
Tam tikru momentu, buvo ašis.

97
00:04:29,330 --> 00:04:32,720
Kitaip tariant, kiekvieno elemento, visi
į kairę skaičiai yra mažiau

98
00:04:32,720 --> 00:04:36,420
vertybės ir visi iki numeriai
teisė turėti didesnes vertes.

99
00:04:36,420 --> 00:04:38,980
>> Šis metodas veikia labai gerai, jei
vertė šerdeso pasirinkta

100
00:04:38,980 --> 00:04:41,930
maždaug per vidurį
diapazonas sąrašą vertybes.

101
00:04:41,930 --> 00:04:45,630
Tai reikštų, kad, kai mes einame
elementai aplink, yra maždaug kaip daug

102
00:04:45,630 --> 00:04:48,390
elementai iš ašies kairėje
nes yra į dešinę.

103
00:04:48,390 --> 00:04:52,380
Ir skaldyk ir valdyk pobūdis
QuickSort algoritmas tada imtis

104
00:04:52,380 --> 00:04:53,850
visiškai išnaudoti.

105
00:04:53,850 --> 00:04:57,500
Tai sukuria O runtime (n log n)
n, nes mes turime daryti n atėmus 1

106
00:04:57,500 --> 00:05:01,640
palyginimams kiekviena karta ir log
n, nes mes turime padalinti sąrašą

107
00:05:01,640 --> 00:05:03,210
prisijunkite n kartų.

108
00:05:03,210 --> 00:05:06,160
Tačiau blogiausiu atveju, tai
algoritmas iš tikrųjų gali būti O (n

109
00:05:06,160 --> 00:05:09,850
kvadratu.) Tarkime, kiekvieną kartą,
suktis tiesiog taip atsitinka, kad

110
00:05:09,850 --> 00:05:12,520
mažiausia arba didžiausia
numeriai mes rūšiavimo.

111
00:05:12,520 --> 00:05:15,870
Tai reikštų, skaidyti sąrašą
n kartų ir padaryti n atėmus 1

112
00:05:15,870 --> 00:05:17,690
lyginti kiekvieną kartą.

113
00:05:17,690 --> 00:05:20,490
Taigi, o n kvadratu.

114
00:05:20,490 --> 00:05:22,000
>> Kaip mes galime pagerinti metodas?

115
00:05:22,000 --> 00:05:25,100
Vienas geras būdas pagerinti metodas yra
siekiama sumažinti tikimybę, kad

116
00:05:25,100 --> 00:05:28,150
Runtime kada nors iš tikrųjų
O n kvadratu.

117
00:05:28,150 --> 00:05:31,860
Prisiminti šią blogiausias blogiausiu atveju
gali įvykti tik tada, kai

118
00:05:31,860 --> 00:05:35,320
pasirinktas ašis visada yra aukščiausia
arba mažiausia reikšmė masyvo.

119
00:05:35,320 --> 00:05:38,630
Siekiant tai užtikrinti yra mažiau tikėtina, kad taip atsitiktų,
mes galime rasti suktis pagal

120
00:05:38,630 --> 00:05:42,610
pasirinkti kelis elementus ir
atsižvelgiant medianą.

121
00:05:42,610 --> 00:05:44,650
>> Mano vardas yra Markas Grozen-Smith
ir tai yra CS50.

122
00:05:44,650 --> 00:05:47,790

123
00:05:47,790 --> 00:05:50,930
>> Kad būtų paprasčiau, tarkime, kad tie
viskas yra tik sveikieji skaičiai, tačiau

124
00:05:50,930 --> 00:05:51,970
žinoti, kad Quicksert -

125
00:05:51,970 --> 00:05:53,160
Quicksert?

126
00:05:53,160 --> 00:05:55,200
Atsiprašau.

127
00:05:55,200 --> 00:06:02,000
>> Čia mes turime skaičiais
6, 5, 1, 3, 8, 4, 9.

128
00:06:02,000 --> 00:06:03,200
>> GARSIAKALBIS 1: Tikrai?

129
00:06:03,200 --> 00:06:04,850
>> SPEAKER 2: Negalima sustoti.

130
00:06:04,850 --> 00:06:06,100
>> GARSIAKALBIS 1: Tikrai?

131
00:06:06,100 --> 00:06:08,491