1
00:00:00,000 --> 00:00:04,419
>> [Muzikos grojimo]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> Doug LLOYD: Gerai, todėl sujungti
Rūšiuoti dar vienas algoritmas

4
00:00:08,460 --> 00:00:11,200
, kad mes galime naudoti norėdami išsiaiškinti
Iš masyvo elementai.

5
00:00:11,200 --> 00:00:14,480
Bet, kaip matysime, ji atšoko
labai esminis skirtumas

6
00:00:14,480 --> 00:00:17,850
nuo atrankos rūšiuoti, burbulas
Rūšiuoti ir įterpimo Rūšiuoti

7
00:00:17,850 --> 00:00:20,280
kad padaryti tai tikrai gana protingas.

8
00:00:20,280 --> 00:00:24,290
>> Pagrindinė idėja suliejimo
Rūšiuoti yra rūšiuoti mažesnių masyvai

9
00:00:24,290 --> 00:00:27,430
ir tada sujungti tuos masyvus
kartu, arba sujungti them--

10
00:00:27,430 --> 00:00:31,440
taigi ir rūšiuotų kad name--.

11
00:00:31,440 --> 00:00:34,230
Taip, kad sujungti rūšiuoti daro
tai nukreipdama įrankį

12
00:00:34,230 --> 00:00:37,290
vadinamas rekursija, o tai, ką
mes ketiname kalbėti apie netrukus,

13
00:00:37,290 --> 00:00:39,720
bet mes ne tikrai kalbėjo apie dar.

14
00:00:39,720 --> 00:00:43,010
>> Štai pagrindinė idėja merge rūšiuoti.

15
00:00:43,010 --> 00:00:46,320
Rūšiuoti kairįjį pusę masyvo,
darant prielaidą, kad n yra didesnis už 1.

16
00:00:46,320 --> 00:00:49,980
Ir ką aš turiu galvoje, kai aš sakau
darant prielaidą, kad n yra didesnis už 1, yra,

17
00:00:49,980 --> 00:00:53,970
Manau, mes galime susitarti, kad jei masyvo
sudaro tik vienas elementas,

18
00:00:53,970 --> 00:00:54,680
tai rūšiuojamos.

19
00:00:54,680 --> 00:00:56,560
Mes ne iš tikrųjų reikia
nieko daryti su juo.

20
00:00:56,560 --> 00:00:58,059
Mes galime tik pripažinti ją turi būti išspręstos.

21
00:00:58,059 --> 00:01:00,110
Tai tik vienas elementas.

22
00:01:00,110 --> 00:01:03,610
>> Taigi Pseudocode, vėl, yra
rūšiuoti kairįjį pusę masyvo,

23
00:01:03,610 --> 00:01:08,590
tada rūšiuoti teisė pusė masyvas,
tada sujungti dvi puses kartu.

24
00:01:08,590 --> 00:01:11,040
Dabar jau galite būti
galvoju, kad tipo tik

25
00:01:11,040 --> 00:01:14,080
skamba kaip jūs atkalba the--
jūs ne iš tikrųjų ką nors.

26
00:01:14,080 --> 00:01:16,330
Jūs sakote rūšiuoti į kairę
pusę, rūšiuoti tinkamą pusę,

27
00:01:16,330 --> 00:01:19,335
bet esate ne pasakoti
man, kaip jūs darote.

28
00:01:19,335 --> 00:01:22,220
>> Bet nepamiršti, kad taip ilgai, kaip
masyvo yra vienas elementas,

29
00:01:22,220 --> 00:01:23,705
mes galime pripažinti ją rūšiuojami.

30
00:01:23,705 --> 00:01:25,330
Tada mes galime tiesiog sujungti juos kartu.

31
00:01:25,330 --> 00:01:27,788
Ir tai iš tikrųjų
pagrindinė idėja merge rūšiuoti,

32
00:01:27,788 --> 00:01:31,150
yra ją padalyti taip, kad
Jūsų matricos dydžio vieno.

33
00:01:31,150 --> 00:01:33,430
Ir tada jūs atkurti iš ten.

34
00:01:33,430 --> 00:01:35,910
>> Sujungti Rūšiuoti tikrai
sudėtingas algoritmas.

35
00:01:35,910 --> 00:01:38,210
Ir tai taip pat šiek tiek
sudėtinga įsivaizduoti.

36
00:01:38,210 --> 00:01:41,870
Taigi tikiuosi, vizualizacija, kad aš
turime čia padės jums sekti kartu.

37
00:01:41,870 --> 00:01:45,640
Ir aš pabandyti mano geriausia pasakoti dalykus
ir pereikite per tai šiek tiek daugiau

38
00:01:45,640 --> 00:01:49,180
lėtai, nei kitų tie
tik tikiuosi gauti savo galvą

39
00:01:49,180 --> 00:01:51,800
aplink atsilieka merge rūšiuoti idėjas.

40
00:01:51,800 --> 00:01:54,680
>> Taigi, mes turi tą patį kaip ir į nustatomas masyvo
kiti rūšiavimo algoritmas video

41
00:01:54,680 --> 00:01:57,120
Jei mačiau them--
šešių elementų masyvas.

42
00:01:57,120 --> 00:02:02,110
Ir mūsų Pseudocode kodas čia yra tarsi
kairė pusė, rūšiuoti tinkamą pusę,

43
00:02:02,110 --> 00:02:03,890
sujungti dvi puses kartu.

44
00:02:03,890 --> 00:02:09,770
Taigi leiskite pasinaudoti šia labai tamsiai raudonų plytų
masyvas ir rūšiuoti kairįjį pusę jo.

45
00:02:09,770 --> 00:02:13,380
>> Taigi šiuo metu, mes ketiname
ignoruoti dešinėje stuff.

46
00:02:13,380 --> 00:02:15,740
Tai ten, bet mes
ne tame etape dar.

47
00:02:15,740 --> 00:02:18,220
Mes ne rūšiuos
teisė pusė masyvo.

48
00:02:18,220 --> 00:02:21,037
Mes ne Rūšiuoti kairėje
pusė masyvo.

49
00:02:21,037 --> 00:02:22,870
Ir tik vardan
, kad jis turi šiek tiek daugiau

50
00:02:22,870 --> 00:02:26,480
aišku, kad aš galiu kreiptis
kas žingsnis mes apie,

51
00:02:26,480 --> 00:02:29,800
Aš ruošiuosi perjungti
spalva šio rinkinio į oranžinę.

52
00:02:29,800 --> 00:02:33,190
Dabar, mes vis dar kalbame apie
pati kairėje pusėje, pirminio masyvo.

53
00:02:33,190 --> 00:02:38,520
Bet aš tikiuosi, kad galėtų
kreiptis į įvairių daiktų spalvas,

54
00:02:38,520 --> 00:02:40,900
jis bus padaryti jį šiek tiek daugiau
išvalyti tai, kas vyksta čia.

55
00:02:40,900 --> 00:02:43,270
>> Gerai, kad dabar mes turime
trijų elementų masyvas.

56
00:02:43,270 --> 00:02:46,420
Kaip mes rūšiuoti kairėje pusėje, tai
masyvo, kuris yra dar šis žingsnis?

57
00:02:46,420 --> 00:02:49,400
Mes stengiamės rūšiuoti į kairę
pusė plytinio raudonumo array--

58
00:02:49,400 --> 00:02:52,410
kairė pusė, kuri
Aš dabar spalvos oranžinė.

59
00:02:52,410 --> 00:02:54,840
>> Na, mes galime išbandyti ir
vėl pakartokite šį procesą.

60
00:02:54,840 --> 00:02:56,756
Taigi mes vis dar
viduryje bando rūšiuoti

61
00:02:56,756 --> 00:02:58,700
kairėje pusėje, visiškai masyvo.

62
00:02:58,700 --> 00:03:00,450
Kairėje pusė
masyvas, aš tik ketina

63
00:03:00,450 --> 00:03:03,910
savavališkai nuspręsti, kad kairė pusė
bus mažesnis nei dešinės pusę,

64
00:03:03,910 --> 00:03:06,550
nes tai atsitinka
sudarytas iš trijų dalių.

65
00:03:06,550 --> 00:03:11,260
>> Ir todėl aš ruošiuosi pasakyti, kad
kairė pusė kairėje pusėje masyvo

66
00:03:11,260 --> 00:03:14,050
yra tik elementas penki.

67
00:03:14,050 --> 00:03:18,360
Penki, būdamas vienas elementas
masyvas, mes žinome, kaip rūšiuoti.

68
00:03:18,360 --> 00:03:21,615
Ir taip penkis rūšiuojamos.

69
00:03:21,615 --> 00:03:22,990
Mes tik ketina paskelbti, kad.

70
00:03:22,990 --> 00:03:24,890
Tai vienas elementas masyve.

71
00:03:24,890 --> 00:03:29,015
>> Taigi dabar mes surūšiuoti
kairė pusė kairėje half--

72
00:03:29,015 --> 00:03:33,190
arba, tiksliau, mes surūšiuoti
kairėje pusėje, oranžinės spalvos.

73
00:03:33,190 --> 00:03:37,970
Taigi, dabar, siekiant dar baigtas
į bendrą masyvo kairės pusės pusę,

74
00:03:37,970 --> 00:03:43,481
turime rūšiuoti tinkamą pusę
iš apelsinų, ar šios medžiagos.

75
00:03:43,481 --> 00:03:44,230
Kaip mes tai padaryti?

76
00:03:44,230 --> 00:03:45,930
Na, mes turime dvi elementų masyvas.

77
00:03:45,930 --> 00:03:50,470
Taigi, mes galime rūšiuoti kairįjį pusę
masyvo, kuris yra du.

78
00:03:50,470 --> 00:03:52,090
Du yra vienas elementas.

79
00:03:52,090 --> 00:03:55,890
Taigi jis rūšiuojami pagal nutylėjimą.
Tada mes galime rūšiuoti tinkamą pusę

80
00:03:55,890 --> 00:03:58,530
tos masyvo, pavaizduoto porcijoje.

81
00:03:58,530 --> 00:04:00,210
Tai tarsi pagal nutylėjimą.

82
00:04:00,210 --> 00:04:03,610
>> Šiuo metu tai yra pirmą kartą
mes pasiekėme suliejimo žingsnį.

83
00:04:03,610 --> 00:04:06,135
Baigėme, nors
mes dabar rūšies įdėtos down--

84
00:04:06,135 --> 00:04:08,420
ir tai tarsi keblus
dalykas su Rekursija yra

85
00:04:08,420 --> 00:04:10,930
Jums reikės išlaikyti savo
galvą apie tai, kur mes esame.

86
00:04:10,930 --> 00:04:15,560
Taigi mes tarsi kairėje
pusė apelsinų porcijoje.

87
00:04:15,560 --> 00:04:21,280
>> Ir dabar, mes vidury rūšiavimas
teisę pusė apelsinų porcijoje.

88
00:04:21,280 --> 00:04:25,320
Ir tame procese, mes esame
dabar ketinate būti žingsnis,

89
00:04:25,320 --> 00:04:27,850
sujungti dvi puses kartu.

90
00:04:27,850 --> 00:04:31,700
Kai pažvelgiame į dvi dalis
masyvo, matome du ir vienas.

91
00:04:31,700 --> 00:04:33,880
Kuris elementas yra mažesnis?

92
00:04:33,880 --> 00:04:35,160
Vienas.

93
00:04:35,160 --> 00:04:36,760
>> Tada kuris elementas yra mažesnis?

94
00:04:36,760 --> 00:04:38,300
Na, tai dviejų ar nieko.

95
00:04:38,300 --> 00:04:39,910
Taigi, tai du.

96
00:04:39,910 --> 00:04:43,690
Taigi, dabar, tik dar kartą rėmo
kur mes esame kontekste,

97
00:04:43,690 --> 00:04:48,230
mes surūšiuoti
kairė pusė apelsino

98
00:04:48,230 --> 00:04:49,886
ir teisę pusė kilmės.

99
00:04:49,886 --> 00:04:52,510
Aš žinau, aš pasikeitė spalvas
vėl, bet tai kur mes buvome.

100
00:04:52,510 --> 00:04:54,676
Ir aš priežastis tai padarė
yra todėl, kad šis procesas yra

101
00:04:54,676 --> 00:04:57,870
ketina nesustoti, Iteracja žemyn.

102
00:04:57,870 --> 00:05:00,500
Mes rūšiuojami į kairę
pusė buvusios oranžinė

103
00:05:00,500 --> 00:05:02,590
ir teisę pusė buvusios oranžinės spalvos.

104
00:05:02,590 --> 00:05:05,620
>> Dabar, mes turime sujungti tuos
dvi dalis kartu per daug.

105
00:05:05,620 --> 00:05:07,730
Štai žingsnis mes apie.

106
00:05:07,730 --> 00:05:11,440
Taigi, mes apsvarstyti visus
elementai, kurie dabar žalia,

107
00:05:11,440 --> 00:05:12,972
kairėje pusėje, pirminio masyvo.

108
00:05:12,972 --> 00:05:14,680
Ir mes sulieti tuos
naudojant tą patį procesą

109
00:05:14,680 --> 00:05:18,660
mes padarėme sujungimo du
ir prieš tik vienas momentas.

110
00:05:18,660 --> 00:05:23,080
>> Kairėje pusę, mažiausias
elementas kairėje pusėje yra penki.

111
00:05:23,080 --> 00:05:25,620
Mažiausias elementas
teisė pusė yra vienas.

112
00:05:25,620 --> 00:05:27,370
Kuris iš jų yra mažesnė?

113
00:05:27,370 --> 00:05:29,260
Vienas.

114
00:05:29,260 --> 00:05:32,250
>> Mažiausias elementas
kairė pusė yra penki.

115
00:05:32,250 --> 00:05:35,540
Mažiausias elementas
teisė pusė yra du.

116
00:05:35,540 --> 00:05:36,970
Kas yra mažiausia?

117
00:05:36,970 --> 00:05:38,160
Du.

118
00:05:38,160 --> 00:05:41,540
Ir tada galiausiai penkių
nieko, mes galime pasakyti, penki.

119
00:05:41,540 --> 00:05:43,935
>> Gerai, kad Big Picture, tegul
atsipūsti sekundę

120
00:05:43,935 --> 00:05:46,080
ir išsiaiškinti, kur mes esame.

121
00:05:46,080 --> 00:05:48,580
Jei mes pradėjome nuo
Pačioje pradžioje mes

122
00:05:48,580 --> 00:05:51,640
jau baigtas
bendras masyvas tik

123
00:05:51,640 --> 00:05:53,810
vienas žingsnis Pseudocode kodas čia.

124
00:05:53,810 --> 00:05:56,645
Mes surūšiuoti
kairė pusė masyvo.

125
00:05:56,645 --> 00:05:59,490
>> Prisiminkite, kad originalus
Kad buvo penki, du, vienas.

126
00:05:59,490 --> 00:06:02,570
Išgyvena šį procesą
ir lizdus žemyn ir kartoti,

127
00:06:02,570 --> 00:06:05,990
toliau pertrauka problemą
žemyn į mažesnes dalis,

128
00:06:05,990 --> 00:06:09,670
mes jau baigė
vieną iš Pseudocode žingsnis

129
00:06:09,670 --> 00:06:13,940
už visą atskaitos masyvo.

130
00:06:13,940 --> 00:06:16,670
Mes rūšiuojami savo kaire puse.

131
00:06:16,670 --> 00:06:18,670
>> Taigi dabar galime užšaldyti ten.

132
00:06:18,670 --> 00:06:23,087
O dabar tegul rūšiuoti teisę
pusė pradinio masyvo.

133
00:06:23,087 --> 00:06:25,670
Ir mes ketiname daryti, kad
išgyvena tą patį kartotinis

134
00:06:25,670 --> 00:06:30,630
procesas kad dalykų žemyn
ir tada sujungti juos kartu.

135
00:06:30,630 --> 00:06:34,290
>> Taigi kairė pusė
raudona, arba yra kairėje pusėje

136
00:06:34,290 --> 00:06:38,830
iš dešinės pusės originalo
masyvas, aš ruošiuosi pasakyti trys.

137
00:06:38,830 --> 00:06:40,312
Vėlgi, aš vis nuoseklūs čia.

138
00:06:40,312 --> 00:06:42,020
Jei turite nelyginis
skaičius elementų, ją

139
00:06:42,020 --> 00:06:44,478
tikrai ne klausimas, ar
jums padaryti liko vienas mažesnis

140
00:06:44,478 --> 00:06:45,620
arba vienas teisingas mažesnis.

141
00:06:45,620 --> 00:06:49,230
>> Svarbu tai, kad, kai jūs
susiduriate su šia problema vykdant

142
00:06:49,230 --> 00:06:51,422
Sujungimas, jūs turite būti nuoseklūs.

143
00:06:51,422 --> 00:06:53,505
Jūs arba visada reikia
padaryti kairėje pusėje mažesnis

144
00:06:53,505 --> 00:06:55,421
ar visada reikia padaryti
dešinėje pusėje mažesnis.

145
00:06:55,421 --> 00:06:57,720
Čia, aš pasirinko, kad visada
padaryti kairėje pusėje mažesnis

146
00:06:57,720 --> 00:07:04,380
kai mano masyvas, ar mano
Sub-masyvas, yra nelyginis dydžio.

147
00:07:04,380 --> 00:07:07,420
>> Trys yra vienas elementas,
ir todėl ji yra rūšiuojami.

148
00:07:07,420 --> 00:07:10,860
Mes skolintomis šią prielaidą
per visą mūsų procese iki šiol.

149
00:07:10,860 --> 00:07:15,020
Taigi dabar galime rūšiuoti teisę
pusė dešinės pusę,

150
00:07:15,020 --> 00:07:18,210
arba į dešinę pusę raudonos.

151
00:07:18,210 --> 00:07:20,390
>> Vėlgi, mes turime išskaidyti tai žemyn.

152
00:07:20,390 --> 00:07:21,910
Tai ne vienas elementas masyve.

153
00:07:21,910 --> 00:07:23,970
Mes negalime pripažinti ją rūšiuojami.

154
00:07:23,970 --> 00:07:27,060
Ir todėl pirmiausia, mes ketiname
rūšiuoti yra kairėje pusėje.

155
00:07:27,060 --> 00:07:31,620
>> Kairysis pusė yra vienas elementas,
todėl rūšiuoti pagal nutylėjimą.

156
00:07:31,620 --> 00:07:34,840
Tada mes ketiname rūšiuoti teisę
pusė, kuri yra vienas elementas.

157
00:07:34,840 --> 00:07:41,250
Tai rūšiuojami pagal nutylėjimą. Ir dabar,
mes galime sujungti šių dviejų kartu.

158
00:07:41,250 --> 00:07:45,820
Keturių yra mažesnis, ir
Tada šeši yra mažesnis.

159
00:07:45,820 --> 00:07:48,870
>> Vėlgi, ką mes padarėme šiuo metu?

160
00:07:48,870 --> 00:07:52,512
Mes rūšiuojami į kairę
pusė dešinės pusę.

161
00:07:52,512 --> 00:07:54,720
Arba grįžta į originalą
spalvos, kad ten buvo,

162
00:07:54,720 --> 00:07:57,875
mes rūšiuojami į kairę
pusė minkštesnė raudonai.

163
00:07:57,875 --> 00:08:00,416
Iš pradžių buvo tamsiai plytų
raudona ir dabar tai minkštesnė raudona,

164
00:08:00,416 --> 00:08:02,350
ar tai buvo minkštesnė raudona.

165
00:08:02,350 --> 00:08:05,145
>> Ir tada mes surūšiuoti
teisė pusė minkštesnė raudona.

166
00:08:05,145 --> 00:08:08,270
Dabar gerai, jie žali dar kartą, tik
nes mes ketiname per procesą.

167
00:08:08,270 --> 00:08:10,720
Ir mes turime kartoti
ir per šį daugiau.

168
00:08:10,720 --> 00:08:14,695
>> Taigi, dabar mes galime sujungti tuos
dvi dalis kartu.

169
00:08:14,695 --> 00:08:15,820
Ir tai, ką mes darome čia.

170
00:08:15,820 --> 00:08:17,653
Taigi juoda linija tiesiog
suskirstyti kairįjį pusę

171
00:08:17,653 --> 00:08:19,690
ir teisė pusė šios rūšies dalis.

172
00:08:19,690 --> 00:08:24,310
>> Mes lyginame mažiausią vertę
kairėje pusėje array--

173
00:08:24,310 --> 00:08:26,710
arba atsiprašau, mažiausias
vertė kairės pusę

174
00:08:26,710 --> 00:08:30,790
mažiausiam vertės dešinę
pusę ir rasti, kad trys yra mažesnis.

175
00:08:30,790 --> 00:08:32,530
Ir dabar, kai jos buvo optimizuoti tiek, tiesa?

176
00:08:32,530 --> 00:08:35,175
Yra tikrai nieko
paliktas kairėje pusėje.

177
00:08:35,175 --> 00:08:37,440
>> Nėra nieko likę
kairėje pusėje,

178
00:08:37,440 --> 00:08:40,877
todėl mes galime efektyviai
tik move-- mes galime paskelbti

179
00:08:40,877 --> 00:08:42,960
likusios yra iš tikrųjų
rūšiuojamos ir tik smeigtuko ją

180
00:08:42,960 --> 00:08:45,126
apie, nes nėra nieko
dar palyginti prieš.

181
00:08:45,126 --> 00:08:49,140
Ir mes žinome, kad dešinė pusė
iš dešinės pusės yra rūšiuojami.

182
00:08:49,140 --> 00:08:52,770
>> Gerai, kad dabar galime užšaldyti ir vėl
išsiaiškinti, kur mes esame į istoriją.

183
00:08:52,770 --> 00:08:56,120
Bendroje masyvas,
Ką mes pasiekiama?

184
00:08:56,120 --> 00:08:58,790
Mes iš tikrųjų pasiekti
dabar vienas ir žingsnis dviem etapais.

185
00:08:58,790 --> 00:09:03,300
Mes rūšiuojami yra kairėje pusėje, o
surūšiuota tinkamą pusę.

186
00:09:03,300 --> 00:09:08,210
>> Taigi dabar belieka mums
sujungti šias dvi puses kartu.

187
00:09:08,210 --> 00:09:11,670
Taigi mes palyginti žemiausias vertinami
elementas kiekvieno masyvo pusėje

188
00:09:11,670 --> 00:09:13,510
savo ruožtu ir toliau.

189
00:09:13,510 --> 00:09:16,535
Vienas iš jų yra mažesnis kaip trys, taip, vienas eina.

190
00:09:16,535 --> 00:09:19,770
>> Du yra mažesnis kaip trys, taip, du eina.

191
00:09:19,770 --> 00:09:22,740
Trys yra mažesnis nei 5, todėl trijų eina.

192
00:09:22,740 --> 00:09:25,820
Keturi yra mažesnis nei 5, todėl keturių eina.

193
00:09:25,820 --> 00:09:30,210
Tada penki yra mažesnis nei šešių,
šeši yra viskas, išlieka.

194
00:09:30,210 --> 00:09:31,820
>> Dabar, aš žinau, kad buvo daug žingsnių.

195
00:09:31,820 --> 00:09:33,636
Ir mes palikome daug
atminties mūsų tinklą.

196
00:09:33,636 --> 00:09:35,260
Ir tai, ką tie pilki kvadratėliai.

197
00:09:35,260 --> 00:09:40,540
Ir tai tikriausiai jaučiau, kad paėmė
daug ilgiau nei įterpimo rūšiuoti, burbulas

198
00:09:40,540 --> 00:09:42,660
Rūšiuoti arba atranka rūšiuoti.

199
00:09:42,660 --> 00:09:45,330
>> Bet iš tikrųjų, nes
daug iš šių procesų

200
00:09:45,330 --> 00:09:48,260
vyksta tuo pačiu LAIKĄ_
kuri yra kažkas, mes vėl

201
00:09:48,260 --> 00:09:51,100
kalbėti apie kai kalbame apie
rekursija į ateitį video--

202
00:09:51,100 --> 00:09:53,799
Šis algoritmas iš tikrųjų
aiškiai yra iš esmės

203
00:09:53,799 --> 00:09:55,590
kitoks, nei nieko
mes matėme prieš

204
00:09:55,590 --> 00:09:58,820
bet taip pat yra žymiai
efektyviau.

205
00:09:58,820 --> 00:09:59,532
>> Kodėl taip yra?

206
00:09:59,532 --> 00:10:01,240
Na, blogiausiu
scenarijaus atveju, mes turime

207
00:10:01,240 --> 00:10:04,830
padalinti n elementų iki
ir tada rekombinuoja juos.

208
00:10:04,830 --> 00:10:06,680
Bet kai mes rekombinuoja
jiems, ką mes darome

209
00:10:06,680 --> 00:10:11,110
iš esmės dubliuoti
dydis iš mažesnių matricos.

210
00:10:11,110 --> 00:10:14,260
Mes turime vieno elemento krūva
masyvai, kad mes iš tikrųjų

211
00:10:14,260 --> 00:10:16,290
sujungti į dvi elementų matricos.

212
00:10:16,290 --> 00:10:18,590
Ir tada mes tie
du elementas masyvai

213
00:10:18,590 --> 00:10:21,890
ir sujungti juos kartu į
keturi element matricas ir tt,

214
00:10:21,890 --> 00:10:26,130
ir taip toliau, ir taip toliau, kol mes
turėti vieną n elementų masyvas.

215
00:10:26,130 --> 00:10:29,910
>> Bet kiek dubliavimǐ
užtrunka gauti n?

216
00:10:29,910 --> 00:10:31,460
Pagalvokite atgal į telefonų knygos pavyzdyje.

217
00:10:31,460 --> 00:10:34,490
Kiek kartų mes turime ašara
telefonų knyga per pusę, kiek daugiau

218
00:10:34,490 --> 00:10:38,370
kartų mes turime ašara telefono knyga
per pusę, jei telefono knygos dydis

219
00:10:38,370 --> 00:10:39,680
dvigubai?

220
00:10:39,680 --> 00:10:41,960
Yra tik vienas, tiesa?

221
00:10:41,960 --> 00:10:45,360
>> Taigi ten kažkokia
logaritminė elementas čia.

222
00:10:45,360 --> 00:10:48,590
Tačiau mes taip pat dar turi bent
ieškoti visi n elementų.

223
00:10:48,590 --> 00:10:53,860
Taigi, blogiausiu atveju,
sujungti rūšiuoti veikia n log n.

224
00:10:53,860 --> 00:10:56,160
Mes turime pažvelgti į
visi n elementų,

225
00:10:56,160 --> 00:11:02,915
ir mes turime juos sujungti
kartu log n rinkinių žingsnius.

226
00:11:02,915 --> 00:11:05,290
Geriausiu atveju,
masyvas puikiai rūšiuojami.

227
00:11:05,290 --> 00:11:06,300
Tai puiku.

228
00:11:06,300 --> 00:11:09,980
Tačiau remiantis algoritmu mes čia,
mes vis dar turime išskaidyti ir rekombinuoja.

229
00:11:09,980 --> 00:11:13,290
Nors šiuo atveju,
apsauginio apvalkalo rūšies neveiksmingas.

230
00:11:13,290 --> 00:11:14,720
Tai nėra būtinas.

231
00:11:14,720 --> 00:11:17,580
Bet mes vis dar eiti per
visas procesas vistiek.

232
00:11:17,580 --> 00:11:21,290
>> Taigi geriausiu atveju
o blogiausiu atveju,

233
00:11:21,290 --> 00:11:24,970
Šis algoritmas veikia n log n metu.

234
00:11:24,970 --> 00:11:29,130
Sujungti Rūšiuoti tikrai tiek sudėtingesnis
nei kitų pagrindinių rūšiavimo algoritmų

235
00:11:29,130 --> 00:11:33,470
mes kalbėjome apie CS50 bet
gerokai galingesnis.

236
00:11:33,470 --> 00:11:35,400
>> Ir todėl, jei jūs kada nors rasti
proga reikia

237
00:11:35,400 --> 00:11:38,480
arba naudoti jį rūšiuoti
didelė duomenų rinkinys, gauti

238
00:11:38,480 --> 00:11:41,940
jūsų galva aplink rekursijos idėjos
bus tikrai galingas.

239
00:11:41,940 --> 00:11:45,270
Ir jis ketina padaryti jūsų
programos tikrai yra daug veiksmingiau

240
00:11:45,270 --> 00:11:48,700
naudojant sujungti rūšiuoti palyginti kas nors kitas.

241
00:11:48,700 --> 00:11:49,640
Aš Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Tai CS50.

243
00:11:51,970 --> 00:11:53,826