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