1
00:00:00,000 --> 00:00:04,419
>> [音樂播放]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD：OK，這樣的合併
排序是另一種算法

4
00:00:08,460 --> 00:00:11,200
我們可以用它來梳理
數組的元素。

5
00:00:11,200 --> 00:00:14,480
但是，正如我們看到的，它有一個
很根本的區別

6
00:00:14,480 --> 00:00:17,850
從選擇排序，冒泡
排序和插入排序

7
00:00:17,850 --> 00:00:20,280
這使得它真的很聰明。

8
00:00:20,280 --> 00:00:24,290
>> 合併背後的基本理念
排序是更小的數組排序

9
00:00:24,290 --> 00:00:27,430
然後再結合這些陣列
在一起，或合併them--

10
00:00:27,430 --> 00:00:31,440
因此，在有序的name--。

11
00:00:31,440 --> 00:00:34,230
該歸併排序的方式做
這是通過利用一個工具

12
00:00:34,230 --> 00:00:37,290
被稱為遞歸，這是什麼
我們要談論不久，

13
00:00:37,290 --> 00:00:39,720
但我們還沒有真正談過呢。

14
00:00:39,720 --> 00:00:43,010
>> 這裡的背後歸併排序的基本思想。

15
00:00:43,010 --> 00:00:46,320
對數組進行排序的左半部分，
假設n大於1。

16
00:00:46,320 --> 00:00:49,980
而我的意思是，當我說
假設n大於1是

17
00:00:49,980 --> 00:00:53,970
我想我們可以同意，如果一個數組
僅由一個單一的元件的，

18
00:00:53,970 --> 00:00:54,680
它的排序。

19
00:00:54,680 --> 00:00:56,560
我們實際上並不需要
做任何事情來了。

20
00:00:56,560 --> 00:00:58,059
我們只需將其聲明進行排序。

21
00:00:58,059 --> 00:01:00,110
這只是一個單一的元件。

22
00:01:00,110 --> 00:01:03,610
>> 這樣的偽碼，同樣，是
對數組進行排序的左一半，

23
00:01:03,610 --> 00:01:08,590
然後排序右半陣列，
然後合併兩半。

24
00:01:08,590 --> 00:01:11,040
現在，已經你可能會
思考，它只是一種

25
00:01:11,040 --> 00:01:14,080
聽起來你推遲喜歡the--
你實際上沒有做任何事情。

26
00:01:14,080 --> 00:01:16,330
你是說左邊的排序
上半年，排序的右半​​部分，

27
00:01:16,330 --> 00:01:19,335
但你不能告訴
我怎麼你這樣做。

28
00:01:19,335 --> 00:01:22,220
>> 但要記住，只要
陣列是一個單一元件，

29
00:01:22,220 --> 00:01:23,705
我們可以宣布它排序。

30
00:01:23,705 --> 00:01:25,330
然後，我們就可以將它們組合在一起。

31
00:01:25,330 --> 00:01:27,788
而這實際上是
背後歸併排序基本思想，

32
00:01:27,788 --> 00:01:31,150
是要打破它，這樣
你的數組的大小之一。

33
00:01:31,150 --> 00:01:33,430
然後你從那裡重建家園。

34
00:01:33,430 --> 00:01:35,910
>> 合併排序是肯定
一個複雜的算法。

35
00:01:35,910 --> 00:01:38,210
而且它也是一個小
複雜的可視化。

36
00:01:38,210 --> 00:01:41,870
所以希望，可視化，我
這裡將幫助你跟著。

37
00:01:41,870 --> 00:01:45,640
我會盡我所能敘述的事情
並繼續通過這個多一點

38
00:01:45,640 --> 00:01:49,180
慢慢比其他的
只是希望得到你的頭

39
00:01:49,180 --> 00:01:51,800
各地背後歸併排序的思想。

40
00:01:51,800 --> 00:01:54,680
>> 因此，我們有相同的陣列作為
其他排序算法視頻

41
00:01:54,680 --> 00:01:57,120
如果你看過them--
六元素的數組。

42
00:01:57,120 --> 00:02:02,110
在這裡，我們的偽代碼排序
左半，排序右半

43
00:02:02,110 --> 00:02:03,890
合併的兩半一起。

44
00:02:03,890 --> 00:02:09,770
因此，讓我們利用這個非常暗磚紅色
數組和排序它的左半邊。

45
00:02:09,770 --> 00:02:13,380
>> 所以暫且，我們將
忽略右邊的東西。

46
00:02:13,380 --> 00:02:15,740
它的存在，但我們
不是在這一步呢。

47
00:02:15,740 --> 00:02:18,220
我們不是在排序
陣列的右半。

48
00:02:18,220 --> 00:02:21,037
我們在左邊的排序
一半的陣列。

49
00:02:21,037 --> 00:02:22,870
而貪圖
被多一點

50
00:02:22,870 --> 00:02:26,480
清晰的，這樣我就可以參考
到了哪一步，我們是上，

51
00:02:26,480 --> 00:02:29,800
我要去切換
顏色這套橙色的。

52
00:02:29,800 --> 00:02:33,190
現在，我們還在談論
原來陣列相同的左一半。

53
00:02:33,190 --> 00:02:38,520
但我希望，通過能夠
指各種物品的顏色，

54
00:02:38,520 --> 00:02:40,900
它會讓它多了幾分
不清楚什麼是怎麼回事。

55
00:02:40,900 --> 00:02:43,270
>> 好了，現在我們有一個
三元數組。

56
00:02:43,270 --> 00:02:46,420
我們怎麼樣的這個左半
陣列，這仍然是這個步驟？

57
00:02:46,420 --> 00:02:49,400
我們試圖向左排序
一半的磚紅色array--的

58
00:02:49,400 --> 00:02:52,410
其中左一半
我現在已經橙色。

59
00:02:52,410 --> 00:02:54,840
>> 好了，我們可以嘗試
再次重複這個過程。

60
00:02:54,840 --> 00:02:56,756
因此，我們仍然在
試圖梳理中間

61
00:02:56,756 --> 00:02:58,700
完整陣列的左半部。

62
00:02:58,700 --> 00:03:00,450
的左半
陣列，我只是去

63
00:03:00,450 --> 00:03:03,910
任意決定的左半
將比右半較小，

64
00:03:03,910 --> 00:03:06,550
因為這恰巧
包括三個部分。

65
00:03:06,550 --> 00:03:11,260
>> 所以我會說，
左半陣列的左半

66
00:03:11,260 --> 00:03:14,050
只是五行說。

67
00:03:14,050 --> 00:03:18,360
五，作為一個單一的元素
陣列，我們知道如何排序。

68
00:03:18,360 --> 00:03:21,615
所以五是排序。

69
00:03:21,615 --> 00:03:22,990
我們只是要聲明。

70
00:03:22,990 --> 00:03:24,890
這是一個單元素數組。

71
00:03:24,890 --> 00:03:29,015
>> 所以，我們現在已經排序
左half--的左半

72
00:03:29,015 --> 00:03:33,190
或者更確切地說，我們已經排序
橙色的左半部。

73
00:03:33,190 --> 00:03:37,970
所以，現在，為了仍然完整
整個陣列的左半邊，

74
00:03:37,970 --> 00:03:43,481
我們需要的右半排序
的橙色或這個東西。

75
00:03:43,481 --> 00:03:44,230
我們該怎麼做呢？

76
00:03:44,230 --> 00:03:45,930
好了，我們有兩個元素的數組。

77
00:03:45,930 --> 00:03:50,470
因此，我們可以排序的左半
陣列，這是兩個。

78
00:03:50,470 --> 00:03:52,090
兩個是單一元件。

79
00:03:52,090 --> 00:03:55,890
因此，它的排序默認情況下。
然後，我們可以排序的右半

80
00:03:55,890 --> 00:03:58,530
該部分陣列，所述一個的。

81
00:03:58,530 --> 00:04:00,210
這類型的默認。

82
00:04:00,210 --> 00:04:03,610
>> 現在這是第一次
我們已經達成了合併的步驟。

83
00:04:03,610 --> 00:04:06,135
我們已經完成了，雖然
那種我們現在嵌套down--

84
00:04:06,135 --> 00:04:08,420
這就是那種棘手的
遞歸的是，

85
00:04:08,420 --> 00:04:10,930
你需要保持你的
腦袋一下我們在哪裡。

86
00:04:10,930 --> 00:04:15,560
因此，我們在左邊的已排序
一半的橙色部分。

87
00:04:15,560 --> 00:04:21,280
>> 而現在，我們在整理的中間
橙色部的右半部分。

88
00:04:21,280 --> 00:04:25,320
而在這過程中，我們
現在即將要上台階，

89
00:04:25,320 --> 00:04:27,850
合併的兩半一起。

90
00:04:27,850 --> 00:04:31,700
當我們在看的兩半
陣列的，我們看到兩個和一個。

91
00:04:31,700 --> 00:04:33,880
該元件是小？

92
00:04:33,880 --> 00:04:35,160
一。

93
00:04:35,160 --> 00:04:36,760
>> 那麼哪一個元素是小？

94
00:04:36,760 --> 00:04:38,300
嗯，這是兩個或沒有。

95
00:04:38,300 --> 00:04:39,910
因此，這兩種。

96
00:04:39,910 --> 00:04:43,690
所以，現在，想再次回到框架
我們所處的背景下，

97
00:04:43,690 --> 00:04:48,230
我們已經整理了
橙色的左半

98
00:04:48,230 --> 00:04:49,886
和原點的右半部。

99
00:04:49,886 --> 00:04:52,510
我知道我已經改變了顏色
再次，但是這就是我們。

100
00:04:52,510 --> 00:04:54,676
而我之所以這樣做
是因為這個過程是

101
00:04:54,676 --> 00:04:57,870
要繼續下去，迭代下降。

102
00:04:57,870 --> 00:05:00,500
我們已經排序的左
半前橙色

103
00:05:00,500 --> 00:05:02,590
和前橙色的右半部分。

104
00:05:02,590 --> 00:05:05,620
>> 現在，我們需要合併這些
兩半了。

105
00:05:05,620 --> 00:05:07,730
這是我們的第一步。

106
00:05:07,730 --> 00:05:11,440
所以我們考慮所有的
元素是現在綠，

107
00:05:11,440 --> 00:05:12,972
原數組的左半部。

108
00:05:12,972 --> 00:05:14,680
我們合併這些
使用相同的過程

109
00:05:14,680 --> 00:05:18,660
我們為合併兩個
和一個剛才。

110
00:05:18,660 --> 00:05:23,080
>> 左半，最小
左邊一半元件是五。

111
00:05:23,080 --> 00:05:25,620
上的最小元素
右半邊是其中之一。

112
00:05:25,620 --> 00:05:27,370
其中哪些是小？

113
00:05:27,370 --> 00:05:29,260
一。

114
00:05:29,260 --> 00:05:32,250
>> 上的最小元素
左半邊是五。

115
00:05:32,250 --> 00:05:35,540
上的最小元素
右半邊為兩個。

116
00:05:35,540 --> 00:05:36,970
什麼是最小的？

117
00:05:36,970 --> 00:05:38,160
二。

118
00:05:38,160 --> 00:05:41,540
然後最後五
什麼都沒有，可以說五位。

119
00:05:41,540 --> 00:05:43,935
>> 好了，這麼大的畫面，讓我們
休息一秒鐘

120
00:05:43,935 --> 00:05:46,080
並找出我們在哪裡。

121
00:05:46,080 --> 00:05:48,580
如果我們從開始
一開始，我們

122
00:05:48,580 --> 00:05:51,640
現在已經完成了
整體陣列只

123
00:05:51,640 --> 00:05:53,810
的偽代碼一步在這裡。

124
00:05:53,810 --> 00:05:56,645
我們已經整理了
陣列的左半部。

125
00:05:56,645 --> 00:05:59,490
>> 回想一下，原
為了五歲，二，一。

126
00:05:59,490 --> 00:06:02,570
通過經歷這個過程
和築巢下來，重複，

127
00:06:02,570 --> 00:06:05,990
繼續打破問題
分解成更小和更小的部分，

128
00:06:05,990 --> 00:06:09,670
現在我們已經完成
步驟的偽代碼之一

129
00:06:09,670 --> 00:06:13,940
對於整個起動陣列。

130
00:06:13,940 --> 00:06:16,670
我們已經整理了左前衛。

131
00:06:16,670 --> 00:06:18,670
>> 所以，現在，讓我們定格在那裡。

132
00:06:18,670 --> 00:06:23,087
現在，讓我們來排序的權利
原來的一半數組。

133
00:06:23,087 --> 00:06:25,670
而我們要做到這一點
經歷同樣的迭代

134
00:06:25,670 --> 00:06:30,630
打破下來的過程
然後將它們合併在一起。

135
00:06:30,630 --> 00:06:34,290
>> 這樣的左半
紅色，或左半

136
00:06:34,290 --> 00:06:38,830
原稿的右半部
陣，我會說是三。

137
00:06:38,830 --> 00:06:40,312
再次，我是一致的在這裡。

138
00:06:40,312 --> 00:06:42,020
如果你有一個奇怪的
元件的數目，它

139
00:06:42,020 --> 00:06:44,478
並沒有真正也罷
你讓左邊的一個小

140
00:06:44,478 --> 00:06:45,620
或者是正確的要小。

141
00:06:45,620 --> 00:06:49,230
>> 重要的是，只要你
遇到在進行這個問題

142
00:06:49,230 --> 00:06:51,422
合併，就需要保持一致。

143
00:06:51,422 --> 00:06:53,505
要么你總是需要
使一個左側小

144
00:06:53,505 --> 00:06:55,421
或總是需要使
右側小。

145
00:06:55,421 --> 00:06:57,720
在這裡，我選擇永遠
使左側小

146
00:06:57,720 --> 00:07:04,380
當我的數組，還是我的
子陣列，是一個奇怪的大小。

147
00:07:04,380 --> 00:07:07,420
>> 三是單一元件，
所以它的排序。

148
00:07:07,420 --> 00:07:10,860
我們充分利用這一假設
我們整個過程為止。

149
00:07:10,860 --> 00:07:15,020
所以，現在讓我們來排序的權利
一半的右邊一半的，

150
00:07:15,020 --> 00:07:18,210
或紅色的右半邊。

151
00:07:18,210 --> 00:07:20,390
>> 同樣，我們需要拆分下來。

152
00:07:20,390 --> 00:07:21,910
這不是一個單一的元件陣列。

153
00:07:21,910 --> 00:07:23,970
我們不能宣布它排序。

154
00:07:23,970 --> 00:07:27,060
所以首先，我們要
在左半排序。

155
00:07:27,060 --> 00:07:31,620
>> 左半是單一元件，
所以它的排序默認情況下。

156
00:07:31,620 --> 00:07:34,840
然後，我們要排序的權利
一半，這是單一元件。

157
00:07:34,840 --> 00:07:41,250
它的排序默認情況下。而現在，
我們可以合併這兩個在一起。

158
00:07:41,250 --> 00:07:45,820
四個較小，並
然後6越小。

159
00:07:45,820 --> 00:07:48,870
>> 此外，我們還有什麼在這一點上做了什麼？

160
00:07:48,870 --> 00:07:52,512
我們已經排序的左
一半的右邊一半。

161
00:07:52,512 --> 00:07:54,720
或回到原來的
這是有顏色的，

162
00:07:54,720 --> 00:07:57,875
我們已經排序的左
一半的較軟的紅色。

163
00:07:57,875 --> 00:08:00,416
它最初是一個黑磚
紅現在是一個更柔和的紅色，

164
00:08:00,416 --> 00:08:02,350
或者，這是一個較軟的紅色。

165
00:08:02,350 --> 00:08:05,145
>> 然後我們排序
的較軟紅右半邊。

166
00:08:05,145 --> 00:08:08,270
現在的，很好，他們是綠色還是一樣，只
因為我們正在經歷一個過程。

167
00:08:08,270 --> 00:08:10,720
我們要重複
這一遍又一遍。

168
00:08:10,720 --> 00:08:14,695
>> 所以，現在，我們可以合併這些
兩半。

169
00:08:14,695 --> 00:08:15,820
這就是我們在這裡做。

170
00:08:15,820 --> 00:08:17,653
所以黑線剛
劃分左半

171
00:08:17,653 --> 00:08:19,690
與這種部分的右半部分。

172
00:08:19,690 --> 00:08:24,310
>> 我們比較的最小值
在array--左側

173
00:08:24,310 --> 00:08:26,710
還是原諒了我，最小
左半的值

174
00:08:26,710 --> 00:08:30,790
到的右側的值最小
一半，並找到三個較小。

175
00:08:30,790 --> 00:08:32,530
而現在有點優化的，對不對？

176
00:08:32,530 --> 00:08:35,175
有其實也沒什麼
留在左側。

177
00:08:35,175 --> 00:08:37,440
>> 沒有什麼剩餘
在左側，

178
00:08:37,440 --> 00:08:40,877
所以我們可以有效地
只是move--我們可以聲明

179
00:08:40,877 --> 00:08:42,960
它的其餘部分實際上是
排序，只是它釘住

180
00:08:42,960 --> 00:08:45,126
對，因為沒有什麼
別人進行比較的。

181
00:08:45,126 --> 00:08:49,140
我們知道，右側
右側是排序。

182
00:08:49,140 --> 00:08:52,770
>> 好了，現在讓我們再次凍結和
找出我們所處的故事。

183
00:08:52,770 --> 00:08:56,120
在整個陣列，
我們有什麼成就？

184
00:08:56,120 --> 00:08:58,790
我們實際上已經完成
現在步驟一和步驟二。

185
00:08:58,790 --> 00:09:03,300
我們的排序左半，和
我們整理了右半邊。

186
00:09:03,300 --> 00:09:08,210
>> 所以，現在，這一切仍然是我們
這些兩半合併在一起。

187
00:09:08,210 --> 00:09:11,670
所以我們比較具有最低值
陣列的每個一半的元件

188
00:09:11,670 --> 00:09:13,510
反過來，然後繼續。

189
00:09:13,510 --> 00:09:16,535
一個是小於3，所以一去。

190
00:09:16,535 --> 00:09:19,770
>> 二是不到三年，所以二除。

191
00:09:19,770 --> 00:09:22,740
三是小於5，所以三去。

192
00:09:22,740 --> 00:09:25,820
四是小於5，因此四去。

193
00:09:25,820 --> 00:09:30,210
然後，五是不到六個月，
六是所有仍然存在。

194
00:09:30,210 --> 00:09:31,820
>> 現在，我知道，這是一個很大的步驟。

195
00:09:31,820 --> 00:09:33,636
而且我們留下了很多
記憶在我們喚醒。

196
00:09:33,636 --> 00:09:35,260
而這正是那些灰色方格。

197
00:09:35,260 --> 00:09:40,540
它可能感覺就像是拿了
很多的時間比插入排序，氣泡

198
00:09:40,540 --> 00:09:42,660
排序或選擇排序。

199
00:09:42,660 --> 00:09:45,330
>> 但實際上，由於
很多這些過程

200
00:09:45,330 --> 00:09:48,260
都發生在同一時間 - 
這是一件好事，我們將再次

201
00:09:48,260 --> 00:09:51,100
談論當我們談論
遞歸在未來video--

202
00:09:51,100 --> 00:09:53,799
這種算法實際上
顯然是根本

203
00:09:53,799 --> 00:09:55,590
比什麼不同
我們已經看到前

204
00:09:55,590 --> 00:09:58,820
但是也顯著
更有效。

205
00:09:58,820 --> 00:09:59,532
>> 這是為什麼呢？

206
00:09:59,532 --> 00:10:01,240
那麼，在最壞的
的情況下，我們有

207
00:10:01,240 --> 00:10:04,830
分裂n個元素了
然後重新組合它們。

208
00:10:04,830 --> 00:10:06,680
但是，當我們重新組合
他們，我們在做什麼

209
00:10:06,680 --> 00:10:11,110
基本上是翻倍
較小的數組的大小。

210
00:10:11,110 --> 00:10:14,260
我們有一大堆的一個元素
陣列我們有效

211
00:10:14,260 --> 00:10:16,290
合併成2個元素的數組。

212
00:10:16,290 --> 00:10:18,590
然後我們把這些
二元陣列

213
00:10:18,590 --> 00:10:21,890
並結合在一起成
4元件陣列，等等，

214
00:10:21,890 --> 00:10:26,130
等等，依此類推，直到我們
有一個單個n元件陣列。

215
00:10:26,130 --> 00:10:29,910
>> 但究竟有多少倍增
它才能讓到n？

216
00:10:29,910 --> 00:10:31,460
回想一下電話簿的例子。

217
00:10:31,460 --> 00:10:34,490
多少次，我們要撕
電話薄了一半，要多

218
00:10:34,490 --> 00:10:38,370
次我們是否撕電話簿
在一半中，如果電話簿的大小

219
00:10:38,370 --> 00:10:39,680
翻倍？

220
00:10:39,680 --> 00:10:41,960
這裡只有一個，對不對？

221
00:10:41,960 --> 00:10:45,360
>> 因此，有某種
這裡對數的元素。

222
00:10:45,360 --> 00:10:48,590
但是，我們也還是要至少
看看所有的n個元素。

223
00:10:48,590 --> 00:10:53,860
因此，在最壞的情況下，
合併排序運行時間為n日誌ñ。

224
00:10:53,860 --> 00:10:56,160
我們來看看
所有的n個元素，

225
00:10:56,160 --> 00:11:02,915
我們必須把它們混合起來
一起在記錄n個步驟。

226
00:11:02,915 --> 00:11:05,290
在最好的情況下，
該陣列是完全排序。

227
00:11:05,290 --> 00:11:06,300
這是偉大的。

228
00:11:06,300 --> 00:11:09,980
但基於算法，我們這裡有，
我們還是要分裂和重組。

229
00:11:09,980 --> 00:11:13,290
雖然在這種情況下，
再結合是一種無效的。

230
00:11:13,290 --> 00:11:14,720
它是不需要的。

231
00:11:14,720 --> 00:11:17,580
但是，我們仍然要經過
整個過程呢。

232
00:11:17,580 --> 00:11:21,290
>> 因此，在最好的情況下
而在最壞的情況下，

233
00:11:21,290 --> 00:11:24,970
該算法運行在的n log n次。

234
00:11:24,970 --> 00:11:29,130
合併排序肯定是有點棘手
比其他主排序算法

235
00:11:29,130 --> 00:11:33,470
我們談到CS50但
實質上更加強大。

236
00:11:33,470 --> 00:11:35,400
>> 所以，如果你發現
有時需要它

237
00:11:35,400 --> 00:11:38,480
或用它來排序
大型數據集，得到

238
00:11:38,480 --> 00:11:41,940
你的頭左右遞歸的想法
將是真正強大。

239
00:11:41,940 --> 00:11:45,270
而這將讓你的
節目真的更有效

240
00:11:45,270 --> 00:11:48,700
使用分類合併與其他任何東西。

241
00:11:48,700 --> 00:11:49,640
我是道格·勞埃德。

242
00:11:49,640 --> 00:11:51,970
這是CS50。

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