1
00:00:00,000 --> 00:00:04,419
>> [Mūzikas atskaņošanai]

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

3
00:00:05,401 --> 00:00:08,460
>> Doug LLOYD: Labi, tāpēc apvienot
kārtošanas ir vēl viens algoritms

4
00:00:08,460 --> 00:00:11,200
ka mēs varam izmantot, lai sakārtotu
elementi masīva.

5
00:00:11,200 --> 00:00:14,480
Bet kā mēs redzēsim, tas ir got
ļoti būtiska atšķirība

6
00:00:14,480 --> 00:00:17,850
no atlases kārtot, burbulis
kārtot, un ievietošanas šķirot

7
00:00:17,850 --> 00:00:20,280
kas padara to patiešām diezgan gudrs.

8
00:00:20,280 --> 00:00:24,290
>> Pamatideja sapludināšanas
kārtošanas ir sakārtot mazākus blokus

9
00:00:24,290 --> 00:00:27,430
un tad apvienot tos bloki
kopā, vai apvienot them--

10
00:00:27,430 --> 00:00:31,440
tāpēc name-- jo šķiroto kārtībā.

11
00:00:31,440 --> 00:00:34,230
Veidā, ka apvienot veida dara
tas ir, piesaistot rīks

12
00:00:34,230 --> 00:00:37,290
sauc rekursijas, kas ir tas, ko
mēs spēsim runāt par drīz,

13
00:00:37,290 --> 00:00:39,720
bet mēs neesam īsti runājuši par vēl.

14
00:00:39,720 --> 00:00:43,010
>> Lūk Pamatideja sapludināšanas kārtošanas.

15
00:00:43,010 --> 00:00:46,320
Kārtot kreiso pusi no masīva,
pieņemot, ka n ir lielāks par 1.

16
00:00:46,320 --> 00:00:49,980
Un ko es domāju, kad es saku
pieņemot, ka n ir lielāks par 1, ir,

17
00:00:49,980 --> 00:00:53,970
Es domāju, ka mēs varam vienoties, ka, ja masīva
tikai sastāv no viena elementa,

18
00:00:53,970 --> 00:00:54,680
tas ir sakārtoti.

19
00:00:54,680 --> 00:00:56,560
Mums nav tiešām nepieciešams
kaut ko darīt, lai to.

20
00:00:56,560 --> 00:00:58,059
Mēs varam tikai atzīt to, lai tiktu sakārtoti.

21
00:00:58,059 --> 00:01:00,110
Tas ir tikai viens elements.

22
00:01:00,110 --> 00:01:03,610
>> Tātad pseudocode, atkal, ir
kārtot kreiso pusi no masīva,

23
00:01:03,610 --> 00:01:08,590
tad šķirot labajā pusē masīvs,
tad apvienot abas pusītes kopā.

24
00:01:08,590 --> 00:01:11,040
Tagad, jau jūs varētu būt
domāšana, tas veida tikai

25
00:01:11,040 --> 00:01:14,080
izklausās kā jūs esat novilcināšanas the--
Jūs neesat faktiski darīt kaut ko.

26
00:01:14,080 --> 00:01:16,330
Jūs sakāt, šķirot kreiso
puse, kārtot pareizo pusi,

27
00:01:16,330 --> 00:01:19,335
bet jūs neesat stāsta
man, kā jūs darāt to.

28
00:01:19,335 --> 00:01:22,220
>> Bet atcerieties, ka tik ilgi, kamēr
masīvs ir viens elements,

29
00:01:22,220 --> 00:01:23,705
mēs varam atzīt to sakārtoti.

30
00:01:23,705 --> 00:01:25,330
Tad mēs varam vienkārši apvienot tos kopā.

31
00:01:25,330 --> 00:01:27,788
Un tas ir faktiski
fundamentāla ideja sapludināšanas veida,

32
00:01:27,788 --> 00:01:31,150
ir lauzt to uz leju, lai
Jūsu masīvi ir lielums vienam.

33
00:01:31,150 --> 00:01:33,430
Un tad jūs atjaunot no turienes.

34
00:01:33,430 --> 00:01:35,910
>> Apvienot kārtošanas ir noteikti
sarežģīts algoritms.

35
00:01:35,910 --> 00:01:38,210
Un tas ir arī nedaudz
sarežģīti iztēloties.

36
00:01:38,210 --> 00:01:41,870
Tik cerams, vizualizācijas, ka es
ir šeit palīdzēs jums sekot līdzi.

37
00:01:41,870 --> 00:01:45,640
Un es mēģināšu manos spēkos, lai stāstīt lietas
un rīkojas ar šo nedaudz vairāk

38
00:01:45,640 --> 00:01:49,180
lēnāk nekā citiem uzņēmumiem
tikai, lai, cerams, saņemt savu galvu

39
00:01:49,180 --> 00:01:51,800
ap aiz sapludināšanas veida idejas.

40
00:01:51,800 --> 00:01:54,680
>> Tāpēc mums ir tāda pati masīvs kā
citas šķirošanas algoritmu video

41
00:01:54,680 --> 00:01:57,120
ja esat redzējuši them--
sešu elementu masīvs.

42
00:01:57,120 --> 00:02:02,110
Un mūsu pseudocode kods šeit ir sava
kreiso pusi, kārtot pareizo pusi,

43
00:02:02,110 --> 00:02:03,890
apvienot abas pusītes kopā.

44
00:02:03,890 --> 00:02:09,770
Tātad pieņemsim šo ļoti tumši ķieģeļu sarkans
masīvs un kārtot kreiso pusi no tā.

45
00:02:09,770 --> 00:02:13,380
>> Tāpēc pagaidām, mēs ejam
ignorēt sīkumi labajā pusē.

46
00:02:13,380 --> 00:02:15,740
Tas ir tur, bet mēs esam
ne šajā posmā vēl.

47
00:02:15,740 --> 00:02:18,220
Mēs esam ne kārtot
tiesības puse no masīva.

48
00:02:18,220 --> 00:02:21,037
Mēs esam pie sava no kreisā
puse no masīva.

49
00:02:21,037 --> 00:02:22,870
Un tikai dēļ
būt mazliet vairāk

50
00:02:22,870 --> 00:02:26,480
skaidrs, lai es varētu atsaukties
uz ko soli mēs esam par,

51
00:02:26,480 --> 00:02:29,800
Es esmu gatavojas, lai pārslēgtos
krāsu šo komplektu uz oranžu.

52
00:02:29,800 --> 00:02:33,190
Tagad mēs joprojām runājam par
pats kreisā puse no sākotnējā masīva.

53
00:02:33,190 --> 00:02:38,520
Bet es esmu cerot, ka ar to var
atsaukties uz krāsas dažādiem priekšmetiem,

54
00:02:38,520 --> 00:02:40,900
tas būs padarīt to mazliet vairāk
skaidrs, kas notiek šeit.

55
00:02:40,900 --> 00:02:43,270
>> Labi, tāpēc tagad mums ir
trīs elementu masīvs.

56
00:02:43,270 --> 00:02:46,420
Kā mēs kārtotu kreiso pusi no šī
masīvs, kas ir vēl šis solis?

57
00:02:46,420 --> 00:02:49,400
Mēs cenšamies, lai sakārtotu kreiso
puse no ķieģeļu sarkanā array--

58
00:02:49,400 --> 00:02:52,410
kreiso pusi no kuriem
Esmu tagad oranžā.

59
00:02:52,410 --> 00:02:54,840
>> Nu, mēs varētu mēģināt
vēlreiz atkārtot šo procesu.

60
00:02:54,840 --> 00:02:56,756
Tātad mēs joprojām esi
vidū mēģina kārtot

61
00:02:56,756 --> 00:02:58,700
kreiso pusi no pilnas masīva.

62
00:02:58,700 --> 00:03:00,450
Kreisajā pusē no
masīvs, es esmu tikai gatavojas

63
00:03:00,450 --> 00:03:03,910
patvaļīgi izlemt, ka kreisā puse
būs mazāks nekā labajā pusē,

64
00:03:03,910 --> 00:03:06,550
jo tas notiek ar
sastāv no trim elementiem.

65
00:03:06,550 --> 00:03:11,260
>> Un tāpēc es esmu gatavojas teikt, ka
kreisā puse no kreisā pusē masīva

66
00:03:11,260 --> 00:03:14,050
ir tikai elements pieci.

67
00:03:14,050 --> 00:03:18,360
Pieci, būdams viens elements
masīvs, mēs zinām, kā šķirot to.

68
00:03:18,360 --> 00:03:21,615
Un tā piecas ir sakārtots.

69
00:03:21,615 --> 00:03:22,990
Mēs esam tikai gatavojas paziņot, ka.

70
00:03:22,990 --> 00:03:24,890
Tas ir viens elements masīvs.

71
00:03:24,890 --> 00:03:29,015
>> Tāpēc mēs esam tagad sakārtoti
kreisā puse no kreisās half--

72
00:03:29,015 --> 00:03:33,190
vai drīzāk, mēs esam sakārtoti
kreisā puse no oranža.

73
00:03:33,190 --> 00:03:37,970
Tāpēc tagad, lai vēl pilns
Vispārējais Array kreisā puse,

74
00:03:37,970 --> 00:03:43,481
mums ir nepieciešams, lai sakārtotu pareizo pusi
no apelsīnu, vai šīs lietas.

75
00:03:43,481 --> 00:03:44,230
Kā mēs to darām?

76
00:03:44,230 --> 00:03:45,930
Nu, mums ir divas elementu masīvu.

77
00:03:45,930 --> 00:03:50,470
Tātad, mēs varam sakārtot kreisi pusi
no masīva, kas ir divi.

78
00:03:50,470 --> 00:03:52,090
Divi ir viens elements.

79
00:03:52,090 --> 00:03:55,890
Tātad, tas ir sakārtoti pēc noklusējuma.
Tad mēs varam sakārtot pareizo pusi

80
00:03:55,890 --> 00:03:58,530
Minētās daļas masīva, viens.

81
00:03:58,530 --> 00:04:00,210
Tas ir sava veida pēc noklusējuma.

82
00:04:00,210 --> 00:04:03,610
>> Tas ir tagad pirmo reizi
mēs esam sasnieguši sapludināšanas soli.

83
00:04:03,610 --> 00:04:06,135
Mums ir pabeigta, lai gan
mēs tagad esam veida ligzdotu down--

84
00:04:06,135 --> 00:04:08,420
un tas ir sava veida kutelīgs
lieta ar recursion ir,

85
00:04:08,420 --> 00:04:10,930
Jums ir nepieciešams, lai saglabātu savu
galvu par to, kur mēs esam.

86
00:04:10,930 --> 00:04:15,560
Tātad, mēs esam sava veida kreisi
puse no apelsīnu porciju.

87
00:04:15,560 --> 00:04:21,280
>> Un tagad mēs esam vidū šķirošanas
labajā pusē apelsīnu porciju.

88
00:04:21,280 --> 00:04:25,320
Un šajā procesā, mēs esam
Tagad par to ir par soli,

89
00:04:25,320 --> 00:04:27,850
apvienot abas pusītes kopā.

90
00:04:27,850 --> 00:04:31,700
Kad mēs skatāmies uz divām pusēm
masīva, mēs redzam divas un vienu.

91
00:04:31,700 --> 00:04:33,880
Kurš elements ir mazāks?

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

93
00:04:35,160 --> 00:04:36,760
>> Tad kurš no šiem elementiem ir mazāks?

94
00:04:36,760 --> 00:04:38,300
Nu, tas ir divi vai neko.

95
00:04:38,300 --> 00:04:39,910
Tātad, tas ir divi.

96
00:04:39,910 --> 00:04:43,690
Tāpēc tagad, tikai, lai atkal rāmi
kur mēs esam kontekstā,

97
00:04:43,690 --> 00:04:48,230
mums ir sakārtoti
kreisā puse no oranža

98
00:04:48,230 --> 00:04:49,886
un labajā pusē izcelsmi.

99
00:04:49,886 --> 00:04:52,510
Es zinu, es esmu mainījies krāsas
atkal, bet tas, kur mēs bijām.

100
00:04:52,510 --> 00:04:54,676
Un iemesls, kāpēc es did this
ir tāpēc, ka šis process ir

101
00:04:54,676 --> 00:04:57,870
gatavojas, lai saglabātu turpinās, atkārtojot leju.

102
00:04:57,870 --> 00:05:00,500
Mēs esam sakārtoti kreiso
puse no iepriekšējā apelsīnu

103
00:05:00,500 --> 00:05:02,590
un labajā pusē bijušās oranža.

104
00:05:02,590 --> 00:05:05,620
>> Tagad mums ir nepieciešams apvienot tos,
divas pusītes kopā too.

105
00:05:05,620 --> 00:05:07,730
Tas ir solis, mēs esam par.

106
00:05:07,730 --> 00:05:11,440
Tāpēc mēs uzskatām, visi
elementus, kas tagad zaļā,

107
00:05:11,440 --> 00:05:12,972
kreiso pusi no sākotnējā masīva.

108
00:05:12,972 --> 00:05:14,680
Un mēs apvienot tos,
izmantojot to pašu procesu

109
00:05:14,680 --> 00:05:18,660
mēs darījām, kas apvienojas divas
un viens tikai pirms brīža.

110
00:05:18,660 --> 00:05:23,080
>> Kreisajā pusē, mazākais
elements kreisajā pusē ir pieci.

111
00:05:23,080 --> 00:05:25,620
Mazākais elements
labajā pusē ir viens.

112
00:05:25,620 --> 00:05:27,370
Kurš no tiem ir mazāks?

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

114
00:05:29,260 --> 00:05:32,250
>> Mazākais elements
kreisā puse ir pieci.

115
00:05:32,250 --> 00:05:35,540
Mazākais elements
labajā pusē ir divi.

116
00:05:35,540 --> 00:05:36,970
Kāds ir mazākais?

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

118
00:05:38,160 --> 00:05:41,540
Un tad visbeidzot pieciem
nekas, mēs varam teikt, pieci.

119
00:05:41,540 --> 00:05:43,935
>> Labi, tik liels attēlu, pieņemsim
ņemt pārtraukumu par sekundi

120
00:05:43,935 --> 00:05:46,080
un izdomāt, kur mēs esam.

121
00:05:46,080 --> 00:05:48,580
Ja mēs sākām no
pašā sākumā, mēs

122
00:05:48,580 --> 00:05:51,640
tagad pabeigta
kopējais masīvs tikko

123
00:05:51,640 --> 00:05:53,810
viens solis pseudocode kodu šeit.

124
00:05:53,810 --> 00:05:56,645
Mums ir sakārtoti
kreisā puse no masīva.

125
00:05:56,645 --> 00:05:59,490
>> Atgādināt, ka sākotnējā
rīkojums bija pieci, divi, viens.

126
00:05:59,490 --> 00:06:02,570
, Ejot cauri šim procesam
un ligzdošanas leju un atkārtojot,

127
00:06:02,570 --> 00:06:05,990
turpinot lauzt problēmu
lejup mazākās un mazākās daļās,

128
00:06:05,990 --> 00:06:09,670
tagad mēs esam pabeiguši
Step viens no pseudocode

129
00:06:09,670 --> 00:06:13,940
visai starta masīvs.

130
00:06:13,940 --> 00:06:16,670
Mums ir sakārtoti tā kreiso pusi.

131
00:06:16,670 --> 00:06:18,670
>> Tāpēc tagad pieņemsim iesaldēt tur.

132
00:06:18,670 --> 00:06:23,087
Un tagad pieņemsim kārtot tiesības
puse no sākotnējā masīva.

133
00:06:23,087 --> 00:06:25,670
Un mēs gatavojamies darīt,
iet caur to pašu iteratīvs

134
00:06:25,670 --> 00:06:30,630
process sadalīšana lietas leju
un pēc tam apvienojot tos kopā.

135
00:06:30,630 --> 00:06:34,290
>> Tātad kreiso pusi no
sarkans, vai kreiso pusi

136
00:06:34,290 --> 00:06:38,830
no labajā pusē oriģināla
masīvs, es esmu gatavojas teikt, ir trīs.

137
00:06:38,830 --> 00:06:40,312
Atkal, es esmu to konsekventi šeit.

138
00:06:40,312 --> 00:06:42,020
Ja jums ir nepāra
elementu skaits, to

139
00:06:42,020 --> 00:06:44,478
nav īsti svarīgi, vai
veicat kreisi viens mazāks

140
00:06:44,478 --> 00:06:45,620
vai pareizais mazāks.

141
00:06:45,620 --> 00:06:49,230
>> Svarīgi ir tas, ka ikreiz, kad jums
saskaras ar šo problēmu veikšanu

142
00:06:49,230 --> 00:06:51,422
apvienošana, jums ir nepieciešams, lai būtu konsekventa.

143
00:06:51,422 --> 00:06:53,505
Jums vai nu vienmēr vajag
veikt kreisā puse mazāka

144
00:06:53,505 --> 00:06:55,421
vai vienmēr ir nepieciešams, lai
labā puse mazākas.

145
00:06:55,421 --> 00:06:57,720
Lūk, es esmu izvēlējusies vienmēr
padarīt kreisajā pusē mazāku

146
00:06:57,720 --> 00:07:04,380
kad mans masīvs, vai mans
sub-masīvs, ir nepāra izmēra.

147
00:07:04,380 --> 00:07:07,420
>> Trīs ir viens elements,
un tāpēc tas ir sakārtots.

148
00:07:07,420 --> 00:07:10,860
Mēs esam parādi šo pieņēmumu
visā mūsu visu procesu līdz šim.

149
00:07:10,860 --> 00:07:15,020
Tāpēc tagad pieņemsim kārtot tiesības
puse no labajā pusē,

150
00:07:15,020 --> 00:07:18,210
vai labajā pusē sarkanā krāsā.

151
00:07:18,210 --> 00:07:20,390
>> Atkal, mums ir nepieciešams sadalīt šo leju.

152
00:07:20,390 --> 00:07:21,910
Tas nav viens elements masīvs.

153
00:07:21,910 --> 00:07:23,970
Mēs nevaram atzīt to sakārtoti.

154
00:07:23,970 --> 00:07:27,060
Un tā, pirmkārt, mēs ejam
kārtot kreiso pusi.

155
00:07:27,060 --> 00:07:31,620
>> Kreisajā pusē ir viens elements,
tāpēc tas ir sava veida pēc noklusējuma.

156
00:07:31,620 --> 00:07:34,840
Tad mēs ejam, lai sakārtotu tiesības
puse, kas ir viens elements.

157
00:07:34,840 --> 00:07:41,250
Tas ir sakārtoti pēc noklusējuma. Un tagad,
mēs varam apvienot šos abus kopā.

158
00:07:41,250 --> 00:07:45,820
Four ir mazāks, un
tad seši ir mazāks.

159
00:07:45,820 --> 00:07:48,870
>> Atkal, ko mēs esam darījuši šajā brīdī?

160
00:07:48,870 --> 00:07:52,512
Mēs esam sakārtoti kreiso
puse no labajā pusē.

161
00:07:52,512 --> 00:07:54,720
Vai dodas atpakaļ uz sākotnējo
krāsas, kas bija tur,

162
00:07:54,720 --> 00:07:57,875
mēs esam sakārtoti kreiso
puse no mīkstāka sarkanā krāsā.

163
00:07:57,875 --> 00:08:00,416
Tā sākotnēji bija tumšs ķieģeļu
sarkans un tagad tas ir mīkstāks sarkans,

164
00:08:00,416 --> 00:08:02,350
vai tas bija mīkstāks sarkana.

165
00:08:02,350 --> 00:08:05,145
>> Un tad mēs esam sakārtoti
labajā pusē mīkstāka sarkanā krāsā.

166
00:08:05,145 --> 00:08:08,270
Tagad, labi, viņi zaļš atkal, tikai
tāpēc, ka mēs ejam cauri procesam.

167
00:08:08,270 --> 00:08:10,720
Un mums ir jāatkārto
Tas vairāk un vairāk.

168
00:08:10,720 --> 00:08:14,695
>> Tāpēc tagad mēs varam apvienot tos,
divas pusītes kopā.

169
00:08:14,695 --> 00:08:15,820
Un tas, ko mēs darām šeit.

170
00:08:15,820 --> 00:08:17,653
Tātad melnā līnija tikko
sadalīts kreiso pusi

171
00:08:17,653 --> 00:08:19,690
un labajā pusē šāda veida daļas.

172
00:08:19,690 --> 00:08:24,310
>> Mēs salīdzinām mazāko vērtību
kreisajā pusē array--

173
00:08:24,310 --> 00:08:26,710
vai atvainojiet, mazākais
vērtība no kreisā pusē

174
00:08:26,710 --> 00:08:30,790
uz vismazāko vērtību, tiesību
pusi un konstatēt, ka trīs ir mazāks.

175
00:08:30,790 --> 00:08:32,530
Un tagad mazliet optimizāciju, vai ne?

176
00:08:32,530 --> 00:08:35,175
Tur tiešām nekas
kreisi kreisajā pusē.

177
00:08:35,175 --> 00:08:37,440
>> Nav nekas atlikušais
kreisajā pusē,

178
00:08:37,440 --> 00:08:40,877
lai mēs varētu efektīvi
tikai move-- mēs varam paziņot,

179
00:08:40,877 --> 00:08:42,960
pārējais tas faktiski
sakārtots un vienkārši sadiegšana to

180
00:08:42,960 --> 00:08:45,126
tālāk, jo tur nekas
cits salīdzināt pret.

181
00:08:45,126 --> 00:08:49,140
Un mēs zinām, ka labajā pusē
no labās puses ir sakārtots.

182
00:08:49,140 --> 00:08:52,770
>> Labi, tāpēc tagad pieņemsim iesaldēt atkal un
izdomāt, kur mēs esam stāsts.

183
00:08:52,770 --> 00:08:56,120
Kopējā masīva,
Kas mums paveikt?

184
00:08:56,120 --> 00:08:58,790
Mēs esam tiešām paveikt
Tagad soli viens un divi soli.

185
00:08:58,790 --> 00:09:03,300
Mēs sakārtoti kreiso pusi, un
mēs sakārtoti pareizo pusi.

186
00:09:03,300 --> 00:09:08,210
>> Tāpēc tagad, viss, kas paliek, ir mums
apvienot šīs divas pusītes kopā.

187
00:09:08,210 --> 00:09:11,670
Tātad mēs salīdzinām zemākais vērtē
katra puse no masīva elements

188
00:09:11,670 --> 00:09:13,510
savukārt un turpināt.

189
00:09:13,510 --> 00:09:16,535
Viens no tiem ir mazāks par trim, tāpēc viens iet.

190
00:09:16,535 --> 00:09:19,770
>> Divi ir mazāks par trim, tā divi iet.

191
00:09:19,770 --> 00:09:22,740
Trīs ir mazāks nekā 5, tāpēc trīs iet.

192
00:09:22,740 --> 00:09:25,820
Četri ir mazāks nekā 5, tāpēc četri iet.

193
00:09:25,820 --> 00:09:30,210
Tad pieci ir mazāks par sešiem,
un seši ir viss, kas paliek.

194
00:09:30,210 --> 00:09:31,820
>> Tagad es zinu, ka bija daudz soļiem.

195
00:09:31,820 --> 00:09:33,636
Un mēs esam atstājuši daudz
Atmiņas mūsu vārtsargam.

196
00:09:33,636 --> 00:09:35,260
Un tas, ko šie pelēkie laukumi ir.

197
00:09:35,260 --> 00:09:40,540
Un tas, iespējams, jutos kā ka paņēma
ilgāk nekā ievietošanas veida daudz, burbulis

198
00:09:40,540 --> 00:09:42,660
kārtot, vai izvēle kārtot.

199
00:09:42,660 --> 00:09:45,330
>> Bet patiesībā, jo
Šo procesu daudz

200
00:09:45,330 --> 00:09:48,260
kas notiek tajā pašā LAIKU_
kas ir kaut mēs, atkal,

201
00:09:48,260 --> 00:09:51,100
runāt par to, kad mēs runājam par
rekursijas kādā nākotnē video--

202
00:09:51,100 --> 00:09:53,799
Šis algoritms faktiski
nepārprotami ir fundamentāli

203
00:09:53,799 --> 00:09:55,590
savādāka nekā jebkas
mēs esam redzējuši iepriekš

204
00:09:55,590 --> 00:09:58,820
bet ir arī ievērojami
efektīvāku.

205
00:09:58,820 --> 00:09:59,532
>> Kāpēc ir tā, ka?

206
00:09:59,532 --> 00:10:01,240
Nu, sliktākajā
scenārijs, mums ir

207
00:10:01,240 --> 00:10:04,830
sadalīt n elementus up
un tad rekombinēties tos.

208
00:10:04,830 --> 00:10:06,680
Bet, kad mēs rekombinēties
tos, ko mēs darām

209
00:10:06,680 --> 00:10:11,110
būtībā dubultojot
izmērs mazākiem masīvi.

210
00:10:11,110 --> 00:10:14,260
Mums ir ķekars viena elementa
masīvi, ka mēs efektīvi

211
00:10:14,260 --> 00:10:16,290
apvienot divās elementu blokiem.

212
00:10:16,290 --> 00:10:18,590
Un tad mēs tos
divi elementu bloki

213
00:10:18,590 --> 00:10:21,890
un tos apvienot
četriem elementiem, bloki, un tā tālāk,

214
00:10:21,890 --> 00:10:26,130
un tā tālāk, un tā tālāk, kamēr mēs
ir viens n elementu klāstu.

215
00:10:26,130 --> 00:10:29,910
>> Bet cik daudz doublings
tas nepieciešams, lai saņemtu uz n?

216
00:10:29,910 --> 00:10:31,460
Think atpakaļ uz tālruņu grāmatu piemērs.

217
00:10:31,460 --> 00:10:34,490
Cik reizes mums ir asaru
tālrunis grāmatu pusi, cik daudz vairāk

218
00:10:34,490 --> 00:10:38,370
reizes mums ir saplēst telefona grāmatu
uz pusi, ja lielums telefona grāmatu

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

220
00:10:39,680 --> 00:10:41,960
Tur ir tikai viens, vai ne?

221
00:10:41,960 --> 00:10:45,360
>> Tātad tur ir daži veida
logaritmiska elements šeit.

222
00:10:45,360 --> 00:10:48,590
Bet mēs arī vēl vismaz
apskatīt visu no n elementiem.

223
00:10:48,590 --> 00:10:53,860
Tātad sliktākajā gadījumā,
apvienot kārtot trašu n log n.

224
00:10:53,860 --> 00:10:56,160
Mums ir jāskatās uz
visi no n elementiem,

225
00:10:56,160 --> 00:11:02,915
un mums ir apvienot tos
kopā log n kopas soļiem.

226
00:11:02,915 --> 00:11:05,290
Labākajā gadījumā,
masīvs ir perfekti sakārtots.

227
00:11:05,290 --> 00:11:06,300
Tas ir lieliski.

228
00:11:06,300 --> 00:11:09,980
Bet, pamatojoties uz algoritmu mums ir šeit,
mums vēl ir sadalīt un rekombinēties.

229
00:11:09,980 --> 00:11:13,290
Lai gan šajā gadījumā
krustmijas ir veida neefektīvs.

230
00:11:13,290 --> 00:11:14,720
Tas nav vajadzīgs.

231
00:11:14,720 --> 00:11:17,580
Bet mēs joprojām iet cauri
viss process anyway.

232
00:11:17,580 --> 00:11:21,290
>> Tātad labākajā gadījumā
un sliktākajā gadījumā,

233
00:11:21,290 --> 00:11:24,970
Šis algoritms darbojas n žurnālā n laikā.

234
00:11:24,970 --> 00:11:29,130
Apvienot kārtošanas noteikti ir mazliet sarežģītāk
nekā citiem galvenajiem šķirošanas algoritmu

235
00:11:29,130 --> 00:11:33,470
mēs esam runājuši par CS50 bet ir
ievērojami jaudīgāku.

236
00:11:33,470 --> 00:11:35,400
>> Un tāpēc, ja jūs kādreiz atrast
izdevība uz to vajag

237
00:11:35,400 --> 00:11:38,480
vai izmantot to kārtot
liels datu kopumu, kļūst

238
00:11:38,480 --> 00:11:41,940
galvu ap ideju recursion
būs ļoti spēcīgs.

239
00:11:41,940 --> 00:11:45,270
Un tas notiek, lai jūsu
programmas tiešām daudz efektīvāka

240
00:11:45,270 --> 00:11:48,700
izmantojot apvienot kārtot pret kaut ko citu.

241
00:11:48,700 --> 00:11:49,640
Es esmu Doug Lloyd.

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

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