1
00:00:00,000 --> 00:00:11,100

2
00:00:11,100 --> 00:00:12,300
>> 扬声器1：嗨大家好！

3
00:00:12,300 --> 00:00:13,890
欢迎回到一节。

4
00:00:13,890 --> 00:00:17,480
很高兴见到你们这么多人都在这里，
大家谁的在线观看。

5
00:00:17,480 --> 00:00:18,760

6
00:00:18,760 --> 00:00:20,920
所以，像往常一样，欢迎回来。

7
00:00:20,920 --> 00:00:24,360
我希望大家都度过了一个可爱
周末，得到充分的休息，放松。

8
00:00:24,360 --> 00:00:26,026
这是美丽的昨天。

9
00:00:26,026 --> 00:00:27,525
所以，我希望你喜欢户外活动。

10
00:00:27,525 --> 00:00:28,840

11
00:00:28,840 --> 00:00:30,610
>> 因此，首先一对夫妇公告。

12
00:00:30,610 --> 00:00:31,920

13
00:00:31,920 --> 00:00:32,700
分级。

14
00:00:32,700 --> 00:00:37,350
所以，你最应该得到的
从我的电子邮件你刮的Pset，

15
00:00:37,350 --> 00:00:39,920
以及分级的Pset中1。

16
00:00:39,920 --> 00:00:41,000

17
00:00:41,000 --> 00:00:42,220
所以，只是一对夫妇的事情。

18
00:00:42,220 --> 00:00:45,150
请务必使用check50在style50。

19
00:00:45,150 --> 00:00:47,250
这些都意味着是
资源为你们，

20
00:00:47,250 --> 00:00:50,660
确保你得到
尽可能多的点，你可以

21
00:00:50,660 --> 00:00:52,390
没有不必要的失去他们。

22
00:00:52,390 --> 00:00:54,407
所以像风格
是非常重要的。

23
00:00:54,407 --> 00:00:55,740
我们要起飞了。

24
00:00:55,740 --> 00:00:58,115
你们有些人可能已经
注意到，从你的pset中。

25
00:00:58,115 --> 00:00:58,920

26
00:00:58,920 --> 00:01:01,450
和check50仅仅是一个
非常简单的方法，以确保

27
00:01:01,450 --> 00:01:05,050
那我们实际上回归了什么
需要被返回给用户，

28
00:01:05,050 --> 00:01:06,690
而这一切的正常工作。

29
00:01:06,690 --> 00:01:08,690

30
00:01:08,690 --> 00:01:12,040
>> 在第二个音符时，请确保您的
上传东西到正确的文件夹中。

31
00:01:12,040 --> 00:01:14,470
它使我的生活只是一个
更困难一点

32
00:01:14,470 --> 00:01:18,836
如果你上传的Pset 2成1的Pset
因为当我下载的东西，

33
00:01:18,836 --> 00:01:20,085
他们不能正确下载。

34
00:01:20,085 --> 00:01:21,690

35
00:01:21,690 --> 00:01:24,560
我知道这是一个有点靠不住
在一个系统中使用的获得，

36
00:01:24,560 --> 00:01:26,950
但只是超
小心，如果只是对我来说，

37
00:01:26,950 --> 00:01:30,080
所以，当你得到的邮件
在像上午02点我就是分级。

38
00:01:30,080 --> 00:01:33,710
如果没有引起我要看看
各地为您的Pset。

39
00:01:33,710 --> 00:01:34,440
凉爽。

40
00:01:34,440 --> 00:01:37,270
>> 我知道这是早期的，但我
完全得到起飞​​后卫

41
00:01:37,270 --> 00:01:40,800
通过一篇短文这是本周五到期，该
我的教授只是喜欢，哦耶。

42
00:01:40,800 --> 00:01:42,550
请记住，你有一个
文章将于周五公布。

43
00:01:42,550 --> 00:01:45,780
所以，我知道没有人喜欢
想想期中考试，

44
00:01:45,780 --> 00:01:50,620
但你的第一次测验是10月15日，
其中10月份这个星期开始。

45
00:01:50,620 --> 00:01:53,290
因此，它可能是迟早
比你预期的是一切。

46
00:01:53,290 --> 00:01:57,510
让你不扔猝不及防的时候
我提到下周一节哦，

47
00:01:57,510 --> 00:02:00,560
您的测验接下来的一周，我想
我愿意给你一点点

48
00:02:00,560 --> 00:02:01,500
的抬起头来了。

49
00:02:01,500 --> 00:02:02,970

50
00:02:02,970 --> 00:02:04,660
>> 所以，你的问题集，排名第三。

51
00:02:04,660 --> 00:02:07,070
人如何阅读
规范的好奇心了呢？

52
00:02:07,070 --> 00:02:08,560

53
00:02:08,560 --> 00:02:09,199
行。

54
00:02:09,199 --> 00:02:10,229
我们有一对夫妇。

55
00:02:10,229 --> 00:02:12,320
那种从上向下
本周不过没关系。

56
00:02:12,320 --> 00:02:13,650
我知道这是美丽的。

57
00:02:13,650 --> 00:02:15,120

58
00:02:15,120 --> 00:02:16,660
因此爆发。

59
00:02:16,660 --> 00:02:21,010
一定时间后就会完成
今天看了你的天赋，至少

60
00:02:21,010 --> 00:02:25,240
尝试像下载
发行代码并运行

61
00:02:25,240 --> 00:02:27,430
像第一初始
他们问你要的东西。

62
00:02:27,430 --> 00:02:28,681

63
00:02:28,681 --> 00:02:32,590
因为我们使用
分配代码和一个图书馆

64
00:02:32,590 --> 00:02:36,790
我们只是一直在using-- --IT只是
第二次我们已经做到了这一点的Pset，

65
00:02:36,790 --> 00:02:38,650
疯狂的事情都可能发生
与您的设备，

66
00:02:38,650 --> 00:02:41,370
你想找到
从现在与以后。

67
00:02:41,370 --> 00:02:45,570
>> 因为如果是周四晚上或它的
周三晚上，由于某种原因

68
00:02:45,570 --> 00:02:48,912
您的设备少了点
要与库运行

69
00:02:48,912 --> 00:02:50,620
或用分配
代码，这意味着

70
00:02:50,620 --> 00:02:52,309
你甚至不能开始做编码。

71
00:02:52,309 --> 00:02:54,100
因为你不能检查
来看看它的工作原理。

72
00:02:54,100 --> 00:02:55,975
你不会是能够
看它是否编译。

73
00:02:55,975 --> 00:03:00,500
你想在早期照顾那些
本周，当你仍然可以给我发电子邮件

74
00:03:00,500 --> 00:03:03,100
或其他转录因子中的一个，
我们可以得到这些固定的。

75
00:03:03,100 --> 00:03:05,410
因为这些都是问题
这会阻止你

76
00:03:05,410 --> 00:03:07,120
做任何实际进展。

77
00:03:07,120 --> 00:03:10,055
它不象1的bug，那
有种你就跳过。

78
00:03:10,055 --> 00:03:10,712

79
00:03:10,712 --> 00:03:13,420
如果您遇到问题，您
设备或分发代码，

80
00:03:13,420 --> 00:03:16,211
你真的想要得到所采取的
呵护宜早不宜迟。

81
00:03:16,211 --> 00:03:20,410
所以，即使你不会真正
开始编码，下载发行

82
00:03:20,410 --> 00:03:24,040
码，读取规格，确保
一切都在那里工作。

83
00:03:24,040 --> 00:03:25,134
行？

84
00:03:25,134 --> 00:03:27,675
如果你可以做到这一点，我
答应你的生活会更容易。

85
00:03:27,675 --> 00:03:28,800

86
00:03:28,800 --> 00:03:31,410
所以你很可能会
要做到这一点，现在好吗？

87
00:03:31,410 --> 00:03:32,100
行。

88
00:03:32,100 --> 00:03:33,950
那么，有什么问题吗？

89
00:03:33,950 --> 00:03:35,850
任何逻辑的东西呢？

90
00:03:35,850 --> 00:03:36,910
大家的好？

91
00:03:36,910 --> 00:03:38,270
行。

92
00:03:38,270 --> 00:03:41,700
>> 免责声明对于那些
你在房间里上网。

93
00:03:41,700 --> 00:03:45,437
我将要尝试切换
PowerPoint中的装置之间

94
00:03:45,437 --> 00:03:47,270
因为我们要
是做一些编码

95
00:03:47,270 --> 00:03:53,630
今天流行的匿名需求
调查建议我送出去的最后一周。

96
00:03:53,630 --> 00:03:55,480
所以，我们会做一些编码。

97
00:03:55,480 --> 00:03:57,800
所以，如果你们也想
火了你的设备，

98
00:03:57,800 --> 00:04:02,910
你应该已经得到了一封电子邮件，
从我来说，有一个示例文件。

99
00:04:02,910 --> 00:04:04,310
请随时做。

100
00:04:04,310 --> 00:04:07,340
>> 所以，我们要谈
GDB，这是一个调试程序。

101
00:04:07,340 --> 00:04:09,970
这将帮助你
种揣摩出

102
00:04:09,970 --> 00:04:11,860
事情会出错的代码。

103
00:04:11,860 --> 00:04:15,370
这真的只是一个方法可以让你一步
通过你的代码，它的发生，

104
00:04:15,370 --> 00:04:19,100
并能够打印出变量
或者看看有什么实际发生

105
00:04:19,100 --> 00:04:22,980
引擎盖下的诗句程序
刚运行时，它就像断层，

106
00:04:22,980 --> 00:04:25,030
和你一样，不知道
这里刚刚发生了什么。

107
00:04:25,030 --> 00:04:26,730
我不知道它没有在哪一行。

108
00:04:26,730 --> 00:04:29,040
我不知道哪里出了问题。

109
00:04:29,040 --> 00:04:31,280
因此，GDB会帮助你的。

110
00:04:31,280 --> 00:04:35,240
另外，如果你决定
继续没错，走61，

111
00:04:35,240 --> 00:04:38,430
它真的，真的是你
最好的朋友，因为我可以告诉你

112
00:04:38,430 --> 00:04:40,840
因为我要通过这个类。

113
00:04:40,840 --> 00:04:43,620
>> 我们要看看二进制
搜索，这如果你们还记得

114
00:04:43,620 --> 00:04:47,540
伟大的电话簿例子
眼镜从类。

115
00:04:47,540 --> 00:04:50,620
我们将实现这一点，
通过多一点点走，

116
00:04:50,620 --> 00:04:54,650
然后我们要通过四个
不同种类的，这是泡沫，

117
00:04:54,650 --> 00:04:56,285
选择，插入和合并。

118
00:04:56,285 --> 00:04:57,830

119
00:04:57,830 --> 00:04:58,330
凉爽。

120
00:04:58,330 --> 00:05:00,390
所以，GDB正如我所说，是一个调试器。

121
00:05:00,390 --> 00:05:01,400

122
00:05:01,400 --> 00:05:09,370
而这些都是一种大的
的东西，大的功能或命令

123
00:05:09,370 --> 00:05:13,240
您在使用GDB，我会走
你通过它在第二演示。

124
00:05:13,240 --> 00:05:15,360
>> 所以，这不仅是
要留抽象。

125
00:05:15,360 --> 00:05:18,000
我会试着让它混凝土
尽可能为你们。

126
00:05:18,000 --> 00:05:19,870
因此，突破。

127
00:05:19,870 --> 00:05:22,200
它会要么是突破
象，一些数量，这

128
00:05:22,200 --> 00:05:26,900
代表你的程序行，
或者，你可以命名的功能。

129
00:05:26,900 --> 00:05:30,150
所以，如果你说分手主力，
它会停在主，

130
00:05:30,150 --> 00:05:32,400
并且让你通过该功能走路。

131
00:05:32,400 --> 00:05:36,350
>> 同样，如果你有一些外部
功能类似于交换或多维数据集，

132
00:05:36,350 --> 00:05:38,450
我们看最后一周。

133
00:05:38,450 --> 00:05:41,780
如果你说破其中的一个，
只要你的程序打了，

134
00:05:41,780 --> 00:05:44,290
就等你来
告诉它要做什么。

135
00:05:44,290 --> 00:05:47,860
之前，它只会执行，所以你
可以在函数内部实际步骤

136
00:05:47,860 --> 00:05:49,020
看看是怎么回事。

137
00:05:49,020 --> 00:05:50,370

138
00:05:50,370 --> 00:05:53,515
所以，接下来，就跳过了
下一行，越过功能。

139
00:05:53,515 --> 00:05:54,730

140
00:05:54,730 --> 00:05:55,560
步骤。

141
00:05:55,560 --> 00:05:56,810
这些都是有点抽象。

142
00:05:56,810 --> 00:06:00,530
所以，我只是通过他们的运行，
但你会看到他们在第二次使用。

143
00:06:00,530 --> 00:06:01,810
>> 步入函数。

144
00:06:01,810 --> 00:06:04,170
因此，正如我所说，
像交换，它会

145
00:06:04,170 --> 00:06:07,110
让你真正的，如果你
就像身体里面的加强，

146
00:06:07,110 --> 00:06:10,990
你可以乱用这些变量，打印
它们是什么，看看发生了什么事情。

147
00:06:10,990 --> 00:06:12,140

148
00:06:12,140 --> 00:06:14,830
名单将字面上只是打印
从周围的代码。

149
00:06:14,830 --> 00:06:17,570
所以，如果你种忘了
你在哪里在你的程序中，

150
00:06:17,570 --> 00:06:19,880
或者你想知道
这是怎么回事周围，

151
00:06:19,880 --> 00:06:23,790
这将只打印出一个段
都喜欢它周围的五六行。

152
00:06:23,790 --> 00:06:26,080
所以，你可以得到导向
关于你在哪里。

153
00:06:26,080 --> 00:06:27,230

154
00:06:27,230 --> 00:06:28,650
>> 打印一些变量。

155
00:06:28,650 --> 00:06:34,590
所以，如果你有这样的关键
在恺撒，那我们来看看。

156
00:06:34,590 --> 00:06:36,220
你可以说在任何时候打印键。

157
00:06:36,220 --> 00:06:40,070
它会告诉你的价值就是如此
这，也许某个地方一路走来，

158
00:06:40,070 --> 00:06:42,070
你重写你的关键。

159
00:06:42,070 --> 00:06:45,495
实际上，你可以告诉大家，因为
你其实可以观察到的价值。

160
00:06:45,495 --> 00:06:46,500

161
00:06:46,500 --> 00:06:48,780
>> 在当地人，只是版画
你的局部变量。

162
00:06:48,780 --> 00:06:53,120
所以，任何时候，你是在一个循环中，
而你只是想看看像哦。

163
00:06:53,120 --> 00:06:54,270
什么是我的吗？

164
00:06:54,270 --> 00:06:57,020
这是什么键值
我在这里初始化？

165
00:06:57,020 --> 00:06:58,537
这是在这一点上的信息？

166
00:06:58,537 --> 00:07:00,370
它只是将打印所有
那些的，这样就

167
00:07:00,370 --> 00:07:04,330
不必单独地
说，打印一打印信息。

168
00:07:04,330 --> 00:07:04,970
打印键。

169
00:07:04,970 --> 00:07:06,190

170
00:07:06,190 --> 00:07:07,700
然后显示。

171
00:07:07,700 --> 00:07:10,370
这是什么做的是为你
单步执行程序，

172
00:07:10,370 --> 00:07:13,980
它会只是确保它的
显示一定的变数

173
00:07:13,980 --> 00:07:14,780
在每一点上。

174
00:07:14,780 --> 00:07:17,160
所以，你also-- --IT是
一种快捷方式，其中的

175
00:07:17,160 --> 00:07:19,530
你没有坚持下去似的，呵呵。

176
00:07:19,530 --> 00:07:23,150
打印键或打印一，这只是
将自动为您代劳。

177
00:07:23,150 --> 00:07:25,959
>> 因此，在这一点，我们要去
怎么看这样下去。

178
00:07:25,959 --> 00:07:28,000
我要去尝试和开关
在我的设备。

179
00:07:28,000 --> 00:07:30,200

180
00:07:30,200 --> 00:07:31,271
看看我能做到这一点。

181
00:07:31,271 --> 00:07:31,770
全部。

182
00:07:31,770 --> 00:07:40,970

183
00:07:40,970 --> 00:07:42,370
我们只是要镜像。

184
00:07:42,370 --> 00:07:44,530
没有什么疯狂
我的笔记本电脑反正。

185
00:07:44,530 --> 00:07:49,600

186
00:07:49,600 --> 00:07:50,100
行。

187
00:07:50,100 --> 00:07:57,030

188
00:07:57,030 --> 00:08:01,054
这需要这个。

189
00:08:01,054 --> 00:08:01,795
它是如此的渺小。

190
00:08:01,795 --> 00:08:03,730

191
00:08:03,730 --> 00:08:05,120
让我们来看看，如果我们能做到这一点。

192
00:08:05,120 --> 00:08:09,970

193
00:08:09,970 --> 00:08:10,940
>> 行。

194
00:08:10,940 --> 00:08:15,305
爱丽丝显然是挣扎
这里只是一点点，

195
00:08:15,305 --> 00:08:17,995
但我们会让它在你几分钟。

196
00:08:17,995 --> 00:08:20,810

197
00:08:20,810 --> 00:08:22,020
行。

198
00:08:22,020 --> 00:08:25,900
我们只是要增加这一点。

199
00:08:25,900 --> 00:08:28,770

200
00:08:28,770 --> 00:08:29,380
行。

201
00:08:29,380 --> 00:08:31,679
种可大家看到了吗？

202
00:08:31,679 --> 00:08:32,470
也许一点点？

203
00:08:32,470 --> 00:08:33,594
我知道这是小了点。

204
00:08:33,594 --> 00:08:34,570

205
00:08:34,570 --> 00:08:37,530
你不能完全弄清楚
如何使这个更大。

206
00:08:37,530 --> 00:08:38,350
如果有人知道。

207
00:08:38,350 --> 00:08:40,309
有谁知道如何使它更大？

208
00:08:40,309 --> 00:08:40,932
行。

209
00:08:40,932 --> 00:08:42,140
我们将推出它。

210
00:08:42,140 --> 00:08:45,801
不要紧，反正，因为它只是
这是代码，你们应该

211
00:08:45,801 --> 00:08:46,300
有。

212
00:08:46,300 --> 00:08:48,310
>> 什么是更重要的
是这里的端子。

213
00:08:48,310 --> 00:08:52,840

214
00:08:52,840 --> 00:08:58,690
而我们在这里为什么会这么少呢？

215
00:08:58,690 --> 00:09:02,325

216
00:09:02,325 --> 00:09:02,825
设置。

217
00:09:02,825 --> 00:09:07,920

218
00:09:07,920 --> 00:09:08,420
呵呵。

219
00:09:08,420 --> 00:09:09,500
真正的艾克。

220
00:09:09,500 --> 00:09:10,880
这个怎么样？

221
00:09:10,880 --> 00:09:11,770
离开那里。

222
00:09:11,770 --> 00:09:19,370

223
00:09:19,370 --> 00:09:21,810
是为大家好？

224
00:09:21,810 --> 00:09:22,525
行，。

225
00:09:22,525 --> 00:09:23,025
凉爽。

226
00:09:23,025 --> 00:09:25,830

227
00:09:25,830 --> 00:09:28,220
>> 你知道，当你在CS
一流的技术困难

228
00:09:28,220 --> 00:09:32,971
是善良的the--一部分
所以，让我们澄清这一点。

229
00:09:32,971 --> 00:09:33,470
行。

230
00:09:33,470 --> 00:09:38,060
所以，这里的部分​​，
我们不得不在这里。

231
00:09:38,060 --> 00:09:40,830
凯撒是一个可执行文件。

232
00:09:40,830 --> 00:09:41,800
所以，我做到了。

233
00:09:41,800 --> 00:09:46,370
所以，有一点要实现与GDB是
它仅适用于可执行文件。

234
00:09:46,370 --> 00:09:48,040
所以，你不能在dotsy运行它。

235
00:09:48,040 --> 00:09:50,532
你要真正使
确保你的代码编译，

236
00:09:50,532 --> 00:09:51,865
并且，它可以实际运行。

237
00:09:51,865 --> 00:09:52,970

238
00:09:52,970 --> 00:09:56,186
>> 因此，请相信，如果它不
编译，得到它的编译，

239
00:09:56,186 --> 00:09:57,810
这样就可以通过它种上运行。

240
00:09:57,810 --> 00:10:04,590
因此，要启动GDB，你所要做的，
凯莱型GDB，然后就在

241
00:10:04,590 --> 00:10:06,250
文件，你想要的。

242
00:10:06,250 --> 00:10:08,240
我总是拼错撒。

243
00:10:08,240 --> 00:10:11,730
但是你要确保
因为它是一个可执行文件，

244
00:10:11,730 --> 00:10:14,210
TI的圆点闪烁，使
意味着你要

245
00:10:14,210 --> 00:10:19,240
运行CSI你要执行
此文件或者与调试。

246
00:10:19,240 --> 00:10:19,910
行。

247
00:10:19,910 --> 00:10:22,885
所以，你这样做，你会得到
这种乱码。

248
00:10:22,885 --> 00:10:24,250

249
00:10:24,250 --> 00:10:25,750
这只是所有关于调试的东西。

250
00:10:25,750 --> 00:10:28,200
你不会真的要
担心现在。

251
00:10:28,200 --> 00:10:31,460
正如你看到的，我们有这个
开括号，国内生产总值，接近括号，

252
00:10:31,460 --> 00:10:34,690
而那种只是看起来像
我们的命令行，对不对？

253
00:10:34,690 --> 00:10:37,010
>> 所以，我们要do--
 - 因此，第一件事

254
00:10:37,010 --> 00:10:39,570
就是我们要选
一个地方打破它。

255
00:10:39,570 --> 00:10:42,332
所以，有一个错误
在这个程序凯撒

256
00:10:42,332 --> 00:10:44,290
我介绍一下，这
我们要了解一下。

257
00:10:44,290 --> 00:10:45,330

258
00:10:45,330 --> 00:10:56,350
它是做什么是需要输入
Barfoo全部大写，并由于某种原因

259
00:10:56,350 --> 00:11:01,950
它只是离开它不会改变A.
孤军奋战，是一切正确，

260
00:11:01,950 --> 00:11:03,980
但第二个字母
A保持不变。

261
00:11:03,980 --> 00:11:07,120
所以，我们要尝试
弄清楚这是为什么。

262
00:11:07,120 --> 00:11:10,440
所以，第一件事情，你通常
想要每次启动GDB上做

263
00:11:10,440 --> 00:11:12,010
是从哪里打破它。

264
00:11:12,010 --> 00:11:14,956
>> 因此，凯撒是一个很短的程序。

265
00:11:14,956 --> 00:11:16,330
我们只是有一个功能，对不对？

266
00:11:16,330 --> 00:11:18,520
什么是我们的凯撒功能？

267
00:11:18,520 --> 00:11:19,590

268
00:11:19,590 --> 00:11:24,350
这里只有一个功能，主要对不对？

269
00:11:24,350 --> 00:11:26,490
主要是功能
您的所有程序。

270
00:11:26,490 --> 00:11:29,230
如果没有主，我可能会
是有点担心，现在，

271
00:11:29,230 --> 00:11:31,000
但我希望你们都在那里有主。

272
00:11:31,000 --> 00:11:34,150
所以，我们可以做的是，我们可以
刚刚突破主，就这样。

273
00:11:34,150 --> 00:11:35,190
因此，它说，OK。

274
00:11:35,190 --> 00:11:37,430
我们设置了断点，一个人也没有。

275
00:11:37,430 --> 00:11:42,870
>> 所以，现在要记住的是凯撒
需要一个命令行参数的权利

276
00:11:42,870 --> 00:11:45,150
我们还没有做到这一点还没有任何地方。

277
00:11:45,150 --> 00:11:47,560
所以，你要做的就是当
你居然去跑

278
00:11:47,560 --> 00:11:51,540
该程序，你是任何程序
在GDB运行需要的命令行

279
00:11:51,540 --> 00:11:55,010
参数，你要输入
当你第一次启动运行它。

280
00:11:55,010 --> 00:11:59,280
所以，在这种情况下，我们做
与三支一键运行。

281
00:11:59,280 --> 00:12:00,770

282
00:12:00,770 --> 00:12:02,040
它会真正开始。

283
00:12:02,040 --> 00:12:08,480
>> 所以，如果你看到这里，我们有
如果RC不等于2。

284
00:12:08,480 --> 00:12:12,210
所以，如果你们都
我送出了该文件

285
00:12:12,210 --> 00:12:15,100
你会看到，就像
第一行我们的主要功能，对不对？

286
00:12:15,100 --> 00:12:17,890
它的检查，看看是否有
正确数目的参数。

287
00:12:17,890 --> 00:12:20,620
所以，如果你想知道
如果RC是正确的，

288
00:12:20,620 --> 00:12:23,250
你可以做一些事情，就像打印RC。

289
00:12:23,250 --> 00:12:24,380

290
00:12:24,380 --> 00:12:28,640
RC为2，这是
我们所预期的，对不对？

291
00:12:28,640 --> 00:12:32,010
>> 因此，我们可以去下，
并继续通过。

292
00:12:32,010 --> 00:12:33,200
因此，我们有一些关键的有。

293
00:12:33,200 --> 00:12:34,260

294
00:12:34,260 --> 00:12:37,090
我们可以打印出我们的关键
以确保是正确的。

295
00:12:37,090 --> 00:12:38,380

296
00:12:38,380 --> 00:12:39,500
有意思的。

297
00:12:39,500 --> 00:12:41,210
并不完全符合我们的预期。

298
00:12:41,210 --> 00:12:44,810
所以，有一点认识
用GDB也，是

299
00:12:44,810 --> 00:12:49,000
它不是，直到你竟然打
接下来，你刚才看到的行

300
00:12:49,000 --> 00:12:50,720
实际执行。

301
00:12:50,720 --> 00:12:53,870
所以，在这种情况下关键
尚未分配爱好。

302
00:12:53,870 --> 00:12:57,050
所以，关键是一些垃圾的价值
您在底部有看到。

303
00:12:57,050 --> 00:13:03,680
负$ 120-- --IT坚持一个十亿
和一些奇怪的事情吧？

304
00:13:03,680 --> 00:13:05,340
这不是我们所期望的关键。

305
00:13:05,340 --> 00:13:10,720
但是，如果我们点击Next，然后我们
尝试打印键，它是三种。

306
00:13:10,720 --> 00:13:11,710
>> 大家看到了吗？

307
00:13:11,710 --> 00:13:13,780
所以，如果你得到的东西
那你喜欢，请等待。

308
00:13:13,780 --> 00:13:15,540
这是完全
错了，我不知道

309
00:13:15,540 --> 00:13:20,150
怎么会发生这种事，因为我想要的
做的是分配一个编号，变量

310
00:13:20,150 --> 00:13:22,900
试着打接下来，尝试印刷
一遍，看看是否可行。

311
00:13:22,900 --> 00:13:27,830
因为它只会执行和
之后，你实际上分配的东西

312
00:13:27,830 --> 00:13:29,340
点击Next。

313
00:13:29,340 --> 00:13:30,336
道理大家？

314
00:13:30,336 --> 00:13:30,836
嗯？

315
00:13:30,836 --> 00:13:33,220
>> 扬声器2：当你随意
数字是什么意思呢？

316
00:13:33,220 --> 00:13:34,790
>> 扬声器1：这只是随机的。

317
00:13:34,790 --> 00:13:35,710
这只是垃圾。

318
00:13:35,710 --> 00:13:38,320
这只是一些你
电脑会随机分配。

319
00:13:38,320 --> 00:13:39,721

320
00:13:39,721 --> 00:13:40,220
凉爽。

321
00:13:40,220 --> 00:13:45,760
所以，现在我们可以通过移动，等等
现在我们有这个纯文本的GetString。

322
00:13:45,760 --> 00:13:48,600
所以，让我介绍什么
会发生什么，当我们点击Next这里。

323
00:13:48,600 --> 00:13:51,320
种了GDB消失了，对不对？

324
00:13:51,320 --> 00:13:55,720
这是因为GetString的
现在执行的，对不对？

325
00:13:55,720 --> 00:14:01,460
所以，当我们看到纯文本等于
GetString的，开放的括号和括号，

326
00:14:01,460 --> 00:14:04,380
和我们打接下来，有
实际执行了。

327
00:14:04,380 --> 00:14:06,580
因此，它在等待
我们输入一些东西。

328
00:14:06,580 --> 00:14:13,560
>> 所以，我们要输入我们的食物，
就是它的失败，因为我告诉过你

329
00:14:13,560 --> 00:14:18,020
那只是说，这是
完成执行，该封闭

330
00:14:18,020 --> 00:14:19,980
支架是指它的
退出了该循环。

331
00:14:19,980 --> 00:14:21,170

332
00:14:21,170 --> 00:14:25,420
因此，我们可以接着打，而现在，因为我
确保你所有的从凯撒熟悉，

333
00:14:25,420 --> 00:14:27,260
这，这是什么行会的事情。

334
00:14:27,260 --> 00:14:32,030
这对INT I等于0，N等于
strlen的，纯文本，然后

335
00:14:32,030 --> 00:14:33,960
我是小于n，I，加，加。

336
00:14:33,960 --> 00:14:35,210
什么是这个循环怎么办呢？

337
00:14:35,210 --> 00:14:37,900

338
00:14:37,900 --> 00:14:39,160
打开你的邮件。

339
00:14:39,160 --> 00:14:39,770
凉爽。

340
00:14:39,770 --> 00:14:41,330
那么，让我们开始这样做。

341
00:14:41,330 --> 00:14:47,210
>> 因此，应此条件
匹配，我们的第一个？

342
00:14:47,210 --> 00:14:52,250
如果它是一个B，这是纯文本格式一，我们
可以了解我们当地人的信息。

343
00:14:52,250 --> 00:14:53,610

344
00:14:53,610 --> 00:14:57,970
所以，我是零​​，而如果6，其
我们希望，我们的重点是三。

345
00:14:57,970 --> 00:14:59,227
所有这一切是有意义的，对吗？

346
00:14:59,227 --> 00:15:01,310
这些数字都
正是他们应该的。

347
00:15:01,310 --> 00:15:02,590

348
00:15:02,590 --> 00:15:03,870
因此，哼？

349
00:15:03,870 --> 00:15:05,620
扬声器3：我有
随机数我的。

350
00:15:05,620 --> 00:15:09,156

351
00:15:09,156 --> 00:15:12,030
扬声器1：嗯，我们可以check--  - 我们
可以聊，在第二。

352
00:15:12,030 --> 00:15:14,110

353
00:15:14,110 --> 00:15:15,750
但是，你应该得到这个。

354
00:15:15,750 --> 00:15:17,700

355
00:15:17,700 --> 00:15:20,130
所以，如果我们有一个资本
B我们的第一个，

356
00:15:20,130 --> 00:15:22,080
这种情况下应该抓住它，对不对？

357
00:15:22,080 --> 00:15:27,120
所以，如果我们打接下来，我们看到
这如果实际执行。

358
00:15:27,120 --> 00:15:29,220
因为如果你是以下
沿着你的代码，

359
00:15:29,220 --> 00:15:33,460
这条线在这里，在纯文本我
替换为算术，

360
00:15:33,460 --> 00:15:35,720
仅当如果执行
条件是正确的吗？

361
00:15:35,720 --> 00:15:36,905

362
00:15:36,905 --> 00:15:40,240
>> GDB只是要告诉你
这是实际执行的东西。

363
00:15:40,240 --> 00:15:45,140
所以，如果没有达到这个如果条件下，它的
只是要跳到下一行。

364
00:15:45,140 --> 00:15:46,540
行？

365
00:15:46,540 --> 00:15:48,510
因此，我们有。

366
00:15:48,510 --> 00:15:51,171
这架意味着它
现在关闭了该循环。

367
00:15:51,171 --> 00:15:52,420
因此，它会重新开始。

368
00:15:52,420 --> 00:15:54,760

369
00:15:54,760 --> 00:15:56,280
就这样。

370
00:15:56,280 --> 00:15:59,120
因此，我们可以得到的信息
关于我们当地人在这里，

371
00:15:59,120 --> 00:16:02,575
我们看到，我们的第一个
信改变了，对不对？

372
00:16:02,575 --> 00:16:05,150
它现在是E，因为它应该是。

373
00:16:05,150 --> 00:16:07,360
因此，我们可以继续。

374
00:16:07,360 --> 00:16:08,500
>> 我们有这个检查。

375
00:16:08,500 --> 00:16:09,916
而这种检查应该工作了吧？

376
00:16:09,916 --> 00:16:12,570
这是A.应该改变
三个字母前进。

377
00:16:12,570 --> 00:16:14,320

378
00:16:14,320 --> 00:16:16,530
但是，如果你注意到，我们
得到不同的东西。

379
00:16:16,530 --> 00:16:17,580

380
00:16:17,580 --> 00:16:22,860
所以在这种情况下在这里，它抓
它，因此这条线执行，

381
00:16:22,860 --> 00:16:28,620
它修改了我们的B.
但是，在这里这种情况下，

382
00:16:28,620 --> 00:16:32,860
我们认为它只是跳过它，
并到[？ L SIFF。 ？]

383
00:16:32,860 --> 00:16:34,660
因此，一些对那里发生。

384
00:16:34,660 --> 00:16:37,780
什么是告诉你的是，
我们知道，它应该在这里赶，

385
00:16:37,780 --> 00:16:39,200
但事实并非如此。

386
00:16:39,200 --> 00:16:42,210
任何人都可以看到我们的
问题是在该行？

387
00:16:42,210 --> 00:16:45,380

388
00:16:45,380 --> 00:16:46,969
这是一个非常微小的事情。

389
00:16:46,969 --> 00:16:48,510
你也可以看看你的代码。

390
00:16:48,510 --> 00:16:49,980

391
00:16:49,980 --> 00:16:54,940
它也line--忘了这是什么线
在那里 - 但它在[听不清]。

392
00:16:54,940 --> 00:16:55,480
是吗？

393
00:16:55,480 --> 00:16:58,639
>> 扬声器4：这是在比大
页面，如果你在书中读到它。

394
00:16:58,639 --> 00:16:59,430
扬声器1：没错。

395
00:16:59,430 --> 00:17:02,620
所以，调试分不清楚
你说，但是调试器

396
00:17:02,620 --> 00:17:05,880
可以让你下到一条线
你知道不正常。

397
00:17:05,880 --> 00:17:09,319
有时候，特别是当
后来在学期中，当

398
00:17:09,319 --> 00:17:12,910
你处​​理了一百，一
百几行代码，你

399
00:17:12,910 --> 00:17:16,190
不知道它的失败，
这是一个伟大的方式来做到这一点。

400
00:17:16,190 --> 00:17:17,900

401
00:17:17,900 --> 00:17:18,989
所以，我们发现我们的错误。

402
00:17:18,989 --> 00:17:21,530
您可以修复它​​在你的文件，
然后，你可以再次运行它，

403
00:17:21,530 --> 00:17:23,029
一切都将正常工作。

404
00:17:23,029 --> 00:17:24,970

405
00:17:24,970 --> 00:17:30,590
而最重要的事情是
这似乎是，OK。

406
00:17:30,590 --> 00:17:31,090
是啊。

407
00:17:31,090 --> 00:17:31,370
凉爽。

408
00:17:31,370 --> 00:17:32,744
你知道你在寻找什么。

409
00:17:32,744 --> 00:17:34,910
所以，你知道该怎么做。

410
00:17:34,910 --> 00:17:39,021
>> GDB可能是因为你超级有帮助
可以打印出所有这些东西，你

411
00:17:39,021 --> 00:17:39,520
不会。

412
00:17:39,520 --> 00:17:41,160
它比的printf有用得多。

413
00:17:41,160 --> 00:17:43,440
你们有多少人使用
如printf语句

414
00:17:43,440 --> 00:17:46,200
找出其中的错误是，对不对？

415
00:17:46,200 --> 00:17:48,450
所以，这一点，你不
必须保持回去，

416
00:17:48,450 --> 00:17:51,139
和喜欢的评论
printf的，或者注释掉，

417
00:17:51,139 --> 00:17:52,930
并找出哪些
你应该打印。

418
00:17:52,930 --> 00:17:55,670
这实际上只是让你
步，打印出来的东西

419
00:17:55,670 --> 00:18:00,000
当你正在经历，所以，你可以
观察他们在现实时间的变化，

420
00:18:00,000 --> 00:18:02,190
因为你的程序正在运行。

421
00:18:02,190 --> 00:18:04,390
>> 它确实需要一点点
对习惯一下。

422
00:18:04,390 --> 00:18:07,850
我会强烈建议正中下怀
的是一个有点沮丧吧

423
00:18:07,850 --> 00:18:08,930
对于现在。

424
00:18:08,930 --> 00:18:13,450
如果你在花一个小时
下周学习如何使用GDB，

425
00:18:13,450 --> 00:18:16,140
你能救自己
如此多的时间以后。

426
00:18:16,140 --> 00:18:18,750
和字面上。告诉我们
这人年年有，

427
00:18:18,750 --> 00:18:23,890
我记得，当我把
类，我很喜欢，我会没事的。

428
00:18:23,890 --> 00:18:24,700
号

429
00:18:24,700 --> 00:18:27,030
PSET 6来了，我是
喜欢，我要学习

430
00:18:27,030 --> 00:18:29,500
如何使用GDB，因为我不
知道是怎么回事。

431
00:18:29,500 --> 00:18:32,940
>> 如果你花时间，所以，
使用它的小程序

432
00:18:32,940 --> 00:18:35,697
那你会是
工作，喜欢工作

433
00:18:35,697 --> 00:18:37,530
通过类似
Visionare，是这样的。

434
00:18:37,530 --> 00:18:38,800

435
00:18:38,800 --> 00:18:42,850
或者，如果你想要额外的练习，我敢肯定，
我可以用bug的程序上来，

436
00:18:42,850 --> 00:18:45,300
为您调试，如果你愿意的话。

437
00:18:45,300 --> 00:18:49,300
>> 但如果你只是需要一些时间来获得
习惯了，只是玩它，

438
00:18:49,300 --> 00:18:50,550
它真的会满足你的需要。

439
00:18:50,550 --> 00:18:52,591
而且它是真正的一个
那些东西，你只是

440
00:18:52,591 --> 00:18:57,340
必须尝试，并得到你的手脏
用，在你真正了解它。

441
00:18:57,340 --> 00:19:02,090
我真的只听懂了一次
我调试的东西吧，

442
00:19:02,090 --> 00:19:08,170
和它的更漂亮有一个想法
如何调试宜早不宜迟。

443
00:19:08,170 --> 00:19:08,850
行。

444
00:19:08,850 --> 00:19:09,625
凉爽。

445
00:19:09,625 --> 00:19:12,960
我知道这有点像
速成班GDB，

446
00:19:12,960 --> 00:19:16,400
我一定会努力的让
这些看起来更大下一次。

447
00:19:16,400 --> 00:19:17,590

448
00:19:17,590 --> 00:19:18,280
凉爽。

449
00:19:18,280 --> 00:19:20,390
>> 所以，如果我们回到我们的PowerPoint。

450
00:19:20,390 --> 00:19:27,194

451
00:19:27,194 --> 00:19:28,110
这是去上班？

452
00:19:28,110 --> 00:19:29,711

453
00:19:29,711 --> 00:19:30,210
AWH。

454
00:19:30,210 --> 00:19:31,101
是的。

455
00:19:31,101 --> 00:19:31,600
行。

456
00:19:31,600 --> 00:19:35,480
所以，如果你需要任何
这些再次，还有的列表。

457
00:19:35,480 --> 00:19:37,160

458
00:19:37,160 --> 00:19:40,830
所以二进制搜索，人人
记得大卫的伟大奇观

459
00:19:40,830 --> 00:19:42,259
撕成两半电话簿。

460
00:19:42,259 --> 00:19:44,050
我真的不明白了
电话簿了，

461
00:19:44,050 --> 00:19:46,530
因为喜欢你在哪里
获取电话簿可好？

462
00:19:46,530 --> 00:19:48,220
我真的不知道。

463
00:19:48,220 --> 00:19:49,840

464
00:19:49,840 --> 00:19:50,590
二进制搜索。

465
00:19:50,590 --> 00:19:52,464
有谁还记得
如何二进制搜索作品？

466
00:19:52,464 --> 00:19:54,380

467
00:19:54,380 --> 00:19:55,220
人呢？

468
00:19:55,220 --> 00:19:56,325
是吗？

469
00:19:56,325 --> 00:19:58,283
扬声器5：你知道什么时候
你看看是哪一半

470
00:19:58,283 --> 00:20:01,146
这将是在，在此基础上，
和摆脱的另一半。

471
00:20:01,146 --> 00:20:01,896
>> 扬声器1没错。

472
00:20:01,896 --> 00:20:06,290
因此，二进制搜索，它是一种A--
 - 我们喜欢叫它分而治之。

473
00:20:06,290 --> 00:20:09,170
所以，你要做的是
你将看到在中间，

474
00:20:09,170 --> 00:20:11,990
你会看它是否符合
您要查找的内容。

475
00:20:11,990 --> 00:20:15,420
如果没有，那么你尝试
搞清楚，它是将要离开

476
00:20:15,420 --> 00:20:16,450
一半或右半部。

477
00:20:16,450 --> 00:20:19,325
所以，这可能是如果你正在寻找
在东西是按字母顺序排列，

478
00:20:19,325 --> 00:20:20,720
你看，哦。

479
00:20:20,720 --> 00:20:22,750
难道佳佳来到先于M？

480
00:20:22,750 --> 00:20:23,250
是的。

481
00:20:23,250 --> 00:20:25,030
所以，我们要
看看上半场。

482
00:20:25,030 --> 00:20:26,450
>> 或者它可能是像数字。

483
00:20:26,450 --> 00:20:28,830
什么，你可以
比较，就可以进行排序。

484
00:20:28,830 --> 00:20:29,920

485
00:20:29,920 --> 00:20:31,260
您可以使用二进制搜索。

486
00:20:31,260 --> 00:20:32,340

487
00:20:32,340 --> 00:20:37,455
因此，任何人都记住了这个
图表或这是什么？

488
00:20:37,455 --> 00:20:39,520
这是渐近复杂性。

489
00:20:39,520 --> 00:20:42,830
因此，此图只
介绍了多长时间

490
00:20:42,830 --> 00:20:46,230
你需要解决一个问题，
你增加多少东西

491
00:20:46,230 --> 00:20:47,090
您正在使用。

492
00:20:47,090 --> 00:20:51,260
>> 因此，我们有N个，其是直链的时间。

493
00:20:51,260 --> 00:20:54,560
如果N超过2，略
好，还是成长超快。

494
00:20:54,560 --> 00:20:58,360
然后我们登录，这是
我们认为二分查找。

495
00:20:58,360 --> 00:21:03,630
如果我们注意到，作为您的问题
变多，大得多，

496
00:21:03,630 --> 00:21:06,600
它把你的时间来解决它
并没有真正增加那么多。

497
00:21:06,600 --> 00:21:09,010
这就像媲美
在这里开始。

498
00:21:09,010 --> 00:21:10,060
你就像，OK。

499
00:21:10,060 --> 00:21:13,000
任何事情在这里并没有真正
无论哪一种我们使用，

500
00:21:13,000 --> 00:21:16,220
但你得到了一百万，一十亿。

501
00:21:16,220 --> 00:21:20,010
你想找到some-- --you're
试图找到大海捞针。

502
00:21:20,010 --> 00:21:21,550
>> 我想你想这个问题。

503
00:21:21,550 --> 00:21:25,850
你想这种复杂性，不
线性的，因为所有你

504
00:21:25,850 --> 00:21:30,049
知道你会通过搜索来
每个单独的针，干草的事情，

505
00:21:30,049 --> 00:21:31,340
试图寻找你的针。

506
00:21:31,340 --> 00:21:34,730
而这还不是在我看来，太好玩了。

507
00:21:34,730 --> 00:21:35,500
我喜欢快。

508
00:21:35,500 --> 00:21:36,620
我喜欢有效率。

509
00:21:36,620 --> 00:21:40,450
而作为勤奋的学生，你
家伙，你知道的更聪明地工作，

510
00:21:40,450 --> 00:21:43,010
而不是更辛苦类型的事情，你怎么
可以弥补这些算法。

511
00:21:43,010 --> 00:21:45,110

512
00:21:45,110 --> 00:21:47,910
>> 所以，我们要走路
仅仅通过一个简单的例子。

513
00:21:47,910 --> 00:21:51,090
我想你们应该有
在二进制搜索手，

514
00:21:51,090 --> 00:21:54,352
但在任何情况下，一点点
模糊，要加强它，

515
00:21:54,352 --> 00:21:56,310
我们打​​算才行
通过这里的例子。

516
00:21:56,310 --> 00:21:59,490
所以，我们要寻找的，如果
该数组包含七个。

517
00:21:59,490 --> 00:22:00,540

518
00:22:00,540 --> 00:22:06,010
>> 所以，我们首先要做的就是
看在中间，对不对？

519
00:22:06,010 --> 00:22:09,340
而且你要被编码
在短短的二二分查找。

520
00:22:09,340 --> 00:22:11,310
因此，这将很有趣。

521
00:22:11,310 --> 00:22:13,710
因此，我们期待在
中间的小数组3。

522
00:22:13,710 --> 00:22:15,501
3是否等于7？

523
00:22:15,501 --> 00:22:16,000
没有。

524
00:22:16,000 --> 00:22:18,670

525
00:22:18,670 --> 00:22:19,550
这是6。

526
00:22:19,550 --> 00:22:21,480
那么，是不是小于
或大于7？

527
00:22:21,480 --> 00:22:23,080

528
00:22:23,080 --> 00:22:23,960
少于。

529
00:22:23,960 --> 00:22:24,570
是的。

530
00:22:24,570 --> 00:22:25,170
干得漂亮家伙。

531
00:22:25,170 --> 00:22:25,569

532
00:22:25,569 --> 00:22:27,360
我觉得我我应该
有糖果，因为我

533
00:22:27,360 --> 00:22:29,460
想要把它伸到码。

534
00:22:29,460 --> 00:22:30,270
这就是我将在下周的事。

535
00:22:30,270 --> 00:22:31,436
这将让你们锋利。

536
00:22:31,436 --> 00:22:32,560

537
00:22:32,560 --> 00:22:34,690
>> 所以，我们扔掉了
上半年，对不对？

538
00:22:34,690 --> 00:22:35,670
这是小于。

539
00:22:35,670 --> 00:22:39,325
我们知道，一切
在该左侧

540
00:22:39,325 --> 00:22:41,700
将是小于什么
我们实际上是在寻找。

541
00:22:41,700 --> 00:22:43,491
所以，没有必要
注意它。

542
00:22:43,491 --> 00:22:45,120
忘掉它。

543
00:22:45,120 --> 00:22:48,720
所以，现在我们看一下我们的右手边，
我们期待在中间那边，

544
00:22:48,720 --> 00:22:50,510
现在它是9。

545
00:22:50,510 --> 00:22:55,510
因此，9 is-- --Everyone？

546
00:22:55,510 --> 00:22:57,470
比我们大
找了吧？

547
00:22:57,470 --> 00:22:59,860
因此，我们要扔掉
客场的一切权利。

548
00:22:59,860 --> 00:23:00,970

549
00:23:00,970 --> 00:23:01,940
这样。

550
00:23:01,940 --> 00:23:03,700
现在，我们只剩下一个。

551
00:23:03,700 --> 00:23:07,760
所以我们检查，是这个东西
我们正在寻找什么？它是。

552
00:23:07,760 --> 00:23:08,970
我们发现我们想要的。

553
00:23:08,970 --> 00:23:10,440

554
00:23:10,440 --> 00:23:11,690
所以，我们就大功告成了。

555
00:23:11,690 --> 00:23:12,550
双线性搜索。

556
00:23:12,550 --> 00:23:15,740
>> 如果你注意到，我们
有七个输入存在。

557
00:23:15,740 --> 00:23:24,320
只花了我们喜欢的三倍，
但如果你正在做的像一个十亿，

558
00:23:24,320 --> 00:23:28,190
你们知道要走多少步会
走，如果我们有四十亿的事情呢？

559
00:23:28,190 --> 00:23:29,940

560
00:23:29,940 --> 00:23:30,455
任何猜测？

561
00:23:30,455 --> 00:23:32,286

562
00:23:32,286 --> 00:23:33,960
这是32。

563
00:23:33,960 --> 00:23:37,110
32步找到的东西
在四十亿

564
00:23:37,110 --> 00:23:39,650
因为两个大国的元素数组。

565
00:23:39,650 --> 00:23:43,550
所以，二是32个，是四十亿。

566
00:23:43,550 --> 00:23:50,430
>> 所以很疯狂怎么你还在内
像一个相当小的数目的步骤

567
00:23:50,430 --> 00:23:52,650
找东西
four十亿元素。

568
00:23:52,650 --> 00:23:55,730
所以，关于这一点，我们
将这个代码

569
00:23:55,730 --> 00:23:58,950
所以你们其实可以
样的了解其工作原理。

570
00:23:58,950 --> 00:24:01,520
好吧，让你们可以代码。

571
00:24:01,520 --> 00:24:04,100
我将让你们
聊了一点点。

572
00:24:04,100 --> 00:24:07,970
了解你周围的人，这是
从最后一节什么人想要的。

573
00:24:07,970 --> 00:24:10,280
>> 所以，了解你周围的人。

574
00:24:10,280 --> 00:24:11,305
聊了一点点。

575
00:24:11,305 --> 00:24:12,580

576
00:24:12,580 --> 00:24:15,730
和所有我想从你
你们现在只是

577
00:24:15,730 --> 00:24:17,575
尝试创建伪代码的轮廓。

578
00:24:17,575 --> 00:24:18,075
行？

579
00:24:18,075 --> 00:24:20,825

580
00:24:20,825 --> 00:24:21,325
哇。

581
00:24:21,325 --> 00:24:23,320

582
00:24:23,320 --> 00:24:29,520
所有我想从你们这些家伙是你
只是要填补这一情况时。

583
00:24:29,520 --> 00:24:32,170
所以我已经设置了这些上
界和下界哪

584
00:24:32,170 --> 00:24:35,250
代表开始
我们的阵列和末端。

585
00:24:35,250 --> 00:24:40,440
而你要真正
遍历并找出

586
00:24:40,440 --> 00:24:42,470
我们正在做的这个while循环中。

587
00:24:42,470 --> 00:24:45,810
>> 所以，如果你自己看着办out--我
暗示那里 - 是什么情况

588
00:24:45,810 --> 00:24:46,640
我们有吗？

589
00:24:46,640 --> 00:24:48,100

590
00:24:48,100 --> 00:24:51,560
所以，如果你想弄清楚的
的情况下，我们将这些伪

591
00:24:51,560 --> 00:24:53,350
然后我们就可以真的实现它们。

592
00:24:53,350 --> 00:24:55,330
而这将是我
想想，希望它会

593
00:24:55,330 --> 00:24:56,788
比预期的更容易一些。

594
00:24:56,788 --> 00:24:57,554

595
00:24:57,554 --> 00:25:00,220
因为它没有那么多的代码，
其实，这是真的很酷。

596
00:25:00,220 --> 00:25:34,110

597
00:25:34,110 --> 00:25:35,018
>> 嗯？

598
00:25:35,018 --> 00:25:35,893
>> 学生：[听不清]？

599
00:25:35,893 --> 00:25:36,984

600
00:25:36,984 --> 00:25:37,650
指导老师：是的。

601
00:25:37,650 --> 00:25:38,595
有一件事
发现在中间。

602
00:25:38,595 --> 00:25:39,552
>> 学生：所以我们可以使用它。

603
00:25:39,552 --> 00:25:39,770
行。

604
00:25:39,770 --> 00:25:40,603
>> 讲师：完美。

605
00:25:40,603 --> 00:25:42,950
所以这是我们需要做的第一件事。

606
00:25:42,950 --> 00:25:44,330
所以，找到中间。

607
00:25:44,330 --> 00:25:45,415

608
00:25:45,415 --> 00:25:45,915
太好了。

609
00:25:45,915 --> 00:25:47,770

610
00:25:47,770 --> 00:25:55,010
所以，你有一个想法，我们怎么可能
实际上找到的代码中间？

611
00:25:55,010 --> 00:25:55,980
>> 学生：是啊。

612
00:25:55,980 --> 00:25:57,000
ñ超过2？

613
00:25:57,000 --> 00:25:58,500

614
00:25:58,500 --> 00:25:59,500
讲师：因此n超过2。

615
00:25:59,500 --> 00:26:05,170
所以，有一点要记住的是，
你的上界和下界改变。

616
00:26:05,170 --> 00:26:08,110
我们不断收缩的部分
数组的，我们正在寻找。

617
00:26:08,110 --> 00:26:11,970
因此n超过2只会工作
对于第一件事，我们做的。

618
00:26:11,970 --> 00:26:17,810
因此服用上下兼顾，
怎么可能，我们得到了中量元素？

619
00:26:17,810 --> 00:26:20,640
因为我们想要中间
之间的上，下，右？

620
00:26:20,640 --> 00:26:21,730

621
00:26:21,730 --> 00:26:22,494
嗯？

622
00:26:22,494 --> 00:26:23,369
>> 学生：[听不清]。

623
00:26:23,369 --> 00:26:26,170

624
00:26:26,170 --> 00:26:28,080
>> 讲师：所以我们有一些中间。

625
00:26:28,080 --> 00:26:32,730
而这将是上加下超过2。

626
00:26:32,730 --> 00:26:34,740

627
00:26:34,740 --> 00:26:35,690
真棒。

628
00:26:35,690 --> 00:26:36,570
在那里，我们走了。

629
00:26:36,570 --> 00:26:37,280
一号线下来。

630
00:26:37,280 --> 00:26:38,560
你们是在用自己的方式。

631
00:26:38,560 --> 00:26:41,400
所以，现在，我们有我们
中间，有什么事我们想干什么？

632
00:26:41,400 --> 00:26:45,050

633
00:26:45,050 --> 00:26:45,900
只是一般。

634
00:26:45,900 --> 00:26:47,734
您不必编写它。

635
00:26:47,734 --> 00:26:48,335
是的。

636
00:26:48,335 --> 00:26:49,210
学生：[听不清]？

637
00:26:49,210 --> 00:27:00,310

638
00:27:00,310 --> 00:27:10,310
讲师：所以这是加，因为你
发现两者之间的平均

639
00:27:10,310 --> 00:27:10,810
对他们。

640
00:27:10,810 --> 00:27:11,890

641
00:27:11,890 --> 00:27:17,370
所以，如果你认为它们是一种
在从侧面增加，

642
00:27:17,370 --> 00:27:21,640
想想看，当你接近
中间，你想这样的。

643
00:27:21,640 --> 00:27:27,150
所以，如果你是对的两边
中间，我们有像5和7。

644
00:27:27,150 --> 00:27:31,440
当你把它们加起来，你
得到12，你除以2，就是6。

645
00:27:31,440 --> 00:27:33,726
>> 有时候很难
解释为什么这样的作品，

646
00:27:33,726 --> 00:27:35,600
但如果你的工作，通过
一个例子有时候，

647
00:27:35,600 --> 00:27:37,962
它会帮你计算出，如果
它应该是正或负。

648
00:27:37,962 --> 00:27:38,846
是的。

649
00:27:38,846 --> 00:27:40,830
>> 学生：[听不清]
恰好在中间

650
00:27:40,830 --> 00:27:43,950
如果他们的情况
还有很多小的数字

651
00:27:43,950 --> 00:27:45,860
而像一个大的数量？

652
00:27:45,860 --> 00:27:49,750
>> 讲师：所以你需要
是阵列的中间。

653
00:27:49,750 --> 00:27:53,010
所以，如果你有一堆小数字
再一个真正大量

654
00:27:53,010 --> 00:27:54,799
在末端，也没关系。

655
00:27:54,799 --> 00:27:56,840
所有的事情是，
他们排序，你只要

656
00:27:56,840 --> 00:27:59,339
想看看中间
数组是因为你还

657
00:27:59,339 --> 00:28:00,700
一半切片您的问题。

658
00:28:00,700 --> 00:28:03,020

659
00:28:03,020 --> 00:28:03,680
凉爽。

660
00:28:03,680 --> 00:28:06,430
所以，现在，我们有
中间，我们接下来做什么？

661
00:28:06,430 --> 00:28:07,150
>> 学生：比较。

662
00:28:07,150 --> 00:28:08,150
讲师：当比较。

663
00:28:08,150 --> 00:28:11,670
所以比较中间value_wanted。

664
00:28:11,670 --> 00:28:14,300

665
00:28:14,300 --> 00:28:15,160
凉爽。

666
00:28:15,160 --> 00:28:17,950
所以你看在这里，我们有
我们要在这里这个值。

667
00:28:17,950 --> 00:28:22,012

668
00:28:22,012 --> 00:28:23,095
请记住，这是一个数组。

669
00:28:23,095 --> 00:28:24,100

670
00:28:24,100 --> 00:28:26,970
所以中间是指索引。

671
00:28:26,970 --> 00:28:29,785
所以，我们要做的中间值。

672
00:28:29,785 --> 00:28:32,380

673
00:28:32,380 --> 00:28:35,650
如果你想不要忘记
比较，双等号。

674
00:28:35,650 --> 00:28:38,250
你做单等于你
只是要重新分配它，

675
00:28:38,250 --> 00:28:41,090
然后，当然，它们也
会是你想要的值。

676
00:28:41,090 --> 00:28:42,300
所以，不要那样做。

677
00:28:42,300 --> 00:28:44,350
>> 所以，我们要如果看
在中间的值

678
00:28:44,350 --> 00:28:46,460
等于我们想要的值。

679
00:28:46,460 --> 00:28:47,749

680
00:28:47,749 --> 00:28:48,790
不要忘了你的牙套。

681
00:28:48,790 --> 00:28:50,520

682
00:28:50,520 --> 00:28:52,235
Dropbox的应该消失。

683
00:28:52,235 --> 00:28:54,140

684
00:28:54,140 --> 00:28:56,200
那么，我们在这种情况下怎么办？

685
00:28:56,200 --> 00:28:59,360
如果它是什么，我们要回去呢？

686
00:28:59,360 --> 00:29:01,510

687
00:29:01,510 --> 00:29:02,626
我们想说的。

688
00:29:02,626 --> 00:29:03,440
>> 学生：打印关闭。

689
00:29:03,440 --> 00:29:05,314
>> 讲师：嗯，我们
不想打印出来。

690
00:29:05,314 --> 00:29:08,220
因此，这是这里的布尔值，因此我们
要返回true或false。

691
00:29:08,220 --> 00:29:12,280
我们要说的，就是这个号码
一个[？ RRA？ ？]因此，如果它是，

692
00:29:12,280 --> 00:29:13,788
我们只是回到它真实的。

693
00:29:13,788 --> 00:29:16,780

694
00:29:16,780 --> 00:29:17,760
如果我能拼写正确。

695
00:29:17,760 --> 00:29:18,830

696
00:29:18,830 --> 00:29:20,805
>> 学生：你为什么不回零？

697
00:29:20,805 --> 00:29:22,930
讲师：所以，你可以
返回零，如果你想要的。

698
00:29:22,930 --> 00:29:26,780
但在这种情况下，因为
我们的函数返回一个布尔值，

699
00:29:26,780 --> 00:29:28,962
我们需要返回true或false。

700
00:29:28,962 --> 00:29:30,920
学生：当你
话说布尔表达式，

701
00:29:30,920 --> 00:29:33,450
你可以将其设置为假？

702
00:29:33,450 --> 00:29:39,860
就像如果我想说，如果这种情况
没有得到满足时，象是上等于false。

703
00:29:39,860 --> 00:29:42,332
如果你只是将它理解
把假的另一边？

704
00:29:42,332 --> 00:29:43,040
指导老师：是啊。

705
00:29:43,040 --> 00:29:44,820
因此，实际上，如果你
曾经做的事情

706
00:29:44,820 --> 00:29:49,600
象是上还是下，
返回true或false

707
00:29:49,600 --> 00:29:53,850
它实际上是不好的风格
比方说等于等于true或等于

708
00:29:53,850 --> 00:29:54,840
等于false。

709
00:29:54,840 --> 00:30:00,210
要使用该结果
因为本身你的支票。

710
00:30:00,210 --> 00:30:04,720

711
00:30:04,720 --> 00:30:05,860
不是我想要的。

712
00:30:05,860 --> 00:30:08,150

713
00:30:08,150 --> 00:30:09,240
这就是我想要的。

714
00:30:09,240 --> 00:30:13,205
所以，在你的情况你问
关于像保存在C。

715
00:30:13,205 --> 00:30:16,320

716
00:30:16,320 --> 00:30:25,150
>> 所以，如果我们有INT主要（无效）
而这样的事情。

717
00:30:25,150 --> 00:30:31,922
你有，如果是上
一些输入你的

718
00:30:31,922 --> 00:30:33,630
问如果你能做到
这样的事情？

719
00:30:33,630 --> 00:30:35,010

720
00:30:35,010 --> 00:30:35,679
对不对？

721
00:30:35,679 --> 00:30:37,470
学生：我是想
要做到这一点[听不清]。

722
00:30:37,470 --> 00:30:38,450
因为如果it's--

723
00:30:38,450 --> 00:30:39,200
指导老师：对。

724
00:30:39,200 --> 00:30:41,197
所以，你希望这是假的，对不对？

725
00:30:41,197 --> 00:30:41,780
学生：是啊。

726
00:30:41,780 --> 00:30:45,960
讲师：所以在这种情况下，你
希望它执行的，如果它是不正确的。

727
00:30:45,960 --> 00:30:50,510
所以，你在那里做的很酷的事情是这样的。

728
00:30:50,510 --> 00:30:52,900

729
00:30:52,900 --> 00:30:55,650
所以请记住惊叹号
点否定的东西呢？

730
00:30:55,650 --> 00:30:58,270
它说[听不清]表示不。

731
00:30:58,270 --> 00:31:03,590
因此，如果我们看一下刚刚
这部分在这里，你会

732
00:31:03,590 --> 00:31:05,740
说，计算结果为
只要你想为false。

733
00:31:05,740 --> 00:31:06,790

734
00:31:06,790 --> 00:31:09,880
不是假的是真的，
这意味着将执行。

735
00:31:09,880 --> 00:31:11,037
这是否有道理？

736
00:31:11,037 --> 00:31:11,620
学生：是啊。

737
00:31:11,620 --> 00:31:12,453
讲师：真棒。

738
00:31:12,453 --> 00:31:13,800

739
00:31:13,800 --> 00:31:14,300
行。

740
00:31:14,300 --> 00:31:16,330
因此，我们可以只返回
真在这种情况下。

741
00:31:16,330 --> 00:31:20,357
所以，现在我们有两个
例在这种情况下。

742
00:31:20,357 --> 00:31:21,565
什么是我们的另外两个情况？

743
00:31:21,565 --> 00:31:31,610

744
00:31:31,610 --> 00:31:32,900
让我们只是做这种方式。

745
00:31:32,900 --> 00:31:40,660
所以，让我们开始其他
如果在中间值

746
00:31:40,660 --> 00:31:43,230
不到我们想要的值。

747
00:31:43,230 --> 00:31:47,200

748
00:31:47,200 --> 00:31:52,020
所以我们在中间的值小于
不是我们要寻找的价值。

749
00:31:52,020 --> 00:31:53,765

750
00:31:53,765 --> 00:31:56,720
>> 那么，哪绑定你
我们认为要更新？

751
00:31:56,720 --> 00:31:57,870

752
00:31:57,870 --> 00:31:58,780
上或下？

753
00:31:58,780 --> 00:32:01,440

754
00:32:01,440 --> 00:32:01,940
上？

755
00:32:01,940 --> 00:32:03,230

756
00:32:03,230 --> 00:32:06,470
因此，该阵列的一侧
我们将要在看什么？

757
00:32:06,470 --> 00:32:07,500
>> 学生：下部。

758
00:32:07,500 --> 00:32:09,750
>> 教师：我们岂不是
可以看左边。

759
00:32:09,750 --> 00:32:11,120
所以，如果别人没有什么价值较少。

760
00:32:11,120 --> 00:32:14,730
所以，你的中间值在这里
不到我们想要的。

761
00:32:14,730 --> 00:32:17,202
因此，我们要采取
右侧我们的阵列。

762
00:32:17,202 --> 00:32:18,910
所以，我们要
更新我们的下界。

763
00:32:18,910 --> 00:32:20,210

764
00:32:20,210 --> 00:32:23,020
因此，我们将重新分配我们的低。

765
00:32:23,020 --> 00:32:25,221
那你觉得下应该是什么？

766
00:32:25,221 --> 00:32:26,304
学生：中间值？

767
00:32:26,304 --> 00:32:27,446

768
00:32:27,446 --> 00:32:28,820
讲师：所以中间value--

769
00:32:28,820 --> 00:32:30,136
学生：加1。

770
00:32:30,136 --> 00:32:31,010
讲师：--plus 1。

771
00:32:31,010 --> 00:32:32,300

772
00:32:32,300 --> 00:32:34,380
谁能告诉我为什么
我们有一个加1？

773
00:32:34,380 --> 00:32:35,730
>> 学生：[？没有价值？]
更等于它。

774
00:32:35,730 --> 00:32:36,120
>> 指导老师：对。

775
00:32:36,120 --> 00:32:38,661
因为我们已经知道，
我们的中间值不等于

776
00:32:38,661 --> 00:32:42,750
它和我们要排除
所有后续搜索。

777
00:32:42,750 --> 00:32:46,360
如果你忘了加1，这
会喜欢无限循环。

778
00:32:46,360 --> 00:32:49,620
而你只是陷入了
无限循环，然后你​​就会出现段错误

779
00:32:49,620 --> 00:32:50,370
而事情变坏。

780
00:32:50,370 --> 00:32:54,780
因此，始终确保你不
其中包括价值，你只是

781
00:32:54,780 --> 00:32:55,380
看了看。

782
00:32:55,380 --> 00:32:58,530
因此，我们照顾与加1。

783
00:32:58,530 --> 00:33:04,840
>> 所以，现在我们有我们的最后一个条件
我总是为了安全着想

784
00:33:04,840 --> 00:33:12,664
您可以点击这里，否则，如果在值
中间的是大于该值

785
00:33:12,664 --> 00:33:13,163
我们想要的。

786
00:33:13,163 --> 00:33:16,260

787
00:33:16,260 --> 00:33:20,230
这意味着，我们要
左手一半。

788
00:33:20,230 --> 00:33:21,350

789
00:33:21,350 --> 00:33:23,260
那么，哪一个我们要更新？

790
00:33:23,260 --> 00:33:23,760
上。

791
00:33:23,760 --> 00:33:25,470

792
00:33:25,470 --> 00:33:26,970
什么是这个打算一样的吗？

793
00:33:26,970 --> 00:33:31,630

794
00:33:31,630 --> 00:33:33,690
中间减1，因为，
当然，我们要

795
00:33:33,690 --> 00:33:38,370
以确保我们不
再看那中间值。

796
00:33:38,370 --> 00:33:41,830

797
00:33:41,830 --> 00:33:45,110
然后，我们有它。

798
00:33:45,110 --> 00:33:45,610
就是这样。

799
00:33:45,610 --> 00:33:46,820
这是所有的二进制搜索。

800
00:33:46,820 --> 00:33:48,190
这并不是说不好，对不对？

801
00:33:48,190 --> 00:33:51,590
这就像10行
用空格代码。

802
00:33:51,590 --> 00:33:57,510
所以很强大，很实用，你会
在你以后的pset中的一个使用它。

803
00:33:57,510 --> 00:33:59,360
也许不是这一个，但后来。

804
00:33:59,360 --> 00:34:00,670
所以，学习它。

805
00:34:00,670 --> 00:34:01,510
爱它。

806
00:34:01,510 --> 00:34:02,980
它会善待你。

807
00:34:02,980 --> 00:34:05,370
因此，没有人有任何
在二进制搜索的问题？

808
00:34:05,370 --> 00:34:06,196
是的。

809
00:34:06,196 --> 00:34:09,840
>> 学生：它的问题
您是否n为偶数或奇数？

810
00:34:09,840 --> 00:34:10,750
>> 导师：第

811
00:34:10,750 --> 00:34:18,150
因为我们投它中间的
一个int，它只会截断。

812
00:34:18,150 --> 00:34:21,600
所以它会留一个整数，它会
通过一切最终排序。

813
00:34:21,600 --> 00:34:23,909
所以，你不必担心。

814
00:34:23,909 --> 00:34:24,580
大家好？

815
00:34:24,580 --> 00:34:25,659

816
00:34:25,659 --> 00:34:26,850
真棒。

817
00:34:26,850 --> 00:34:27,919
凉爽。

818
00:34:27,919 --> 00:34:30,836
所以，你们得到这个。

819
00:34:30,836 --> 00:34:33,380

820
00:34:33,380 --> 00:34:33,880
幻灯片。

821
00:34:33,880 --> 00:34:35,719

822
00:34:35,719 --> 00:34:43,270
因此，当我们在谈论，我知道
大卫提到的复杂的运行时间。

823
00:34:43,270 --> 00:34:44,420

824
00:34:44,420 --> 00:34:50,340
>> 因此，在最好的情况下，它只是
1，我们称之为恒定时间。

825
00:34:50,340 --> 00:34:51,909
谁能告诉我为什么，可能是？

826
00:34:51,909 --> 00:34:52,969

827
00:34:52,969 --> 00:34:55,800
什么类型的场景会是意味着什么？

828
00:34:55,800 --> 00:34:58,260

829
00:34:58,260 --> 00:34:58,760
嗯。

830
00:34:58,760 --> 00:34:59,926
>> 学生：[听不清] first--

831
00:34:59,926 --> 00:35:00,789

832
00:35:00,789 --> 00:35:03,830
讲师：所以中间作为
我们来到了第一个元素，对不对？

833
00:35:03,830 --> 00:35:08,167
这样的一个数组或
无论我们正在寻找的只是

834
00:35:08,167 --> 00:35:09,750
正好是在中间嫌民建联。

835
00:35:09,750 --> 00:35:11,190

836
00:35:11,190 --> 00:35:13,380
所以这是我们最好的情况。

837
00:35:13,380 --> 00:35:17,540
你进入真正的问题，恐怕不是
要达到[听不清]经常。

838
00:35:17,540 --> 00:35:18,667

839
00:35:18,667 --> 00:35:19,750
那么我们最坏的情况？

840
00:35:19,750 --> 00:35:21,270
我们最糟的情况是日志ñ。

841
00:35:21,270 --> 00:35:25,360
并且，是因为有全
两件事，我谈到的权力。

842
00:35:25,360 --> 00:35:30,930
>> 所以在最坏的情况下这将意味着
我们不得不砍了下来阵列

843
00:35:30,930 --> 00:35:33,270
直到它是1的一个元素。

844
00:35:33,270 --> 00:35:34,810

845
00:35:34,810 --> 00:35:38,930
因此，我们不得不砍了下去一半
因为很多时候，我们可能会。

846
00:35:38,930 --> 00:35:41,430
这就是为什么它的日志N，因为
你只是保持除以二。

847
00:35:41,430 --> 00:35:42,890

848
00:35:42,890 --> 00:35:45,830
所以假设，你的东西
要知道，如果你曾经

849
00:35:45,830 --> 00:35:48,050
要使用二进制搜索。

850
00:35:48,050 --> 00:35:50,680
你必须元素进行排序。

851
00:35:50,680 --> 00:35:53,890
他们进行排序，因为
这是你唯一的出路

852
00:35:53,890 --> 00:35:57,060
可以知道，如果你能
扔了出来一半。

853
00:35:57,060 --> 00:36:00,260
>> 如果你有这个混乱的包包
号码和你说，

854
00:36:00,260 --> 00:36:05,380
好了，我要去检查中间
号码和我正在寻找数

855
00:36:05,380 --> 00:36:08,510
小于说，我只是去
随意扔掉一半。

856
00:36:08,510 --> 00:36:11,130
你不会知道你的
在另一半的数字。

857
00:36:11,130 --> 00:36:12,655
列表中的排序。

858
00:36:12,655 --> 00:36:14,030

859
00:36:14,030 --> 00:36:16,560
同样，这可能是
要提前一点点，

860
00:36:16,560 --> 00:36:18,360
但你需要有随机访问。

861
00:36:18,360 --> 00:36:21,940
你需要能够公正
去那个中间的元素。

862
00:36:21,940 --> 00:36:25,110
如果你必须遍历
通过什么

863
00:36:25,110 --> 00:36:28,630
或者你花额外的步骤
去了中间的元素，

864
00:36:28,630 --> 00:36:31,750
它没有日志N了，因为
您要添加更多的工作了进去。

865
00:36:31,750 --> 00:36:34,800
这将使一点
在两周更有意义，

866
00:36:34,800 --> 00:36:37,950
但我就是那种想要前言，
给你们一个什么样的想法

867
00:36:37,950 --> 00:36:38,999
来。

868
00:36:38,999 --> 00:36:40,790
但就是这两种
重要的假设

869
00:36:40,790 --> 00:36:44,804
你需要一个二进制名单。

870
00:36:44,804 --> 00:36:45,720
请确保它的排序。

871
00:36:45,720 --> 00:36:47,920
这是大个的
你们现在。

872
00:36:47,920 --> 00:36:52,170
和我们能进入
我们各种各样的休息。

873
00:36:52,170 --> 00:36:56,444
所以4选择产品类别泡沫，
插入，选择和合并。

874
00:36:56,444 --> 00:36:57,485
他们都很酷。

875
00:36:57,485 --> 00:37:02,860
如果你们决定采取CS 124，
您将了解各种不爽。

876
00:37:02,860 --> 00:37:07,575
如果你是一个XKCD风扇，有
是一个非常酷的漫画有关

877
00:37:07,575 --> 00:37:11,530
就像真的无效的种种，我
强烈建议你去看看。

878
00:37:11,530 --> 00:37:16,170
其中之一是喜欢那种恐慌，这
就像是，哦，不，返回随机数组。

879
00:37:16,170 --> 00:37:16,991
关闭系统。

880
00:37:16,991 --> 00:37:17,490
离开。

881
00:37:17,490 --> 00:37:19,070

882
00:37:19,070 --> 00:37:21,500
所以古怪的幽默总是好的。

883
00:37:21,500 --> 00:37:22,620

884
00:37:22,620 --> 00:37:25,750
>> 因此，没有人记得那种
像只是一个总体思路

885
00:37:25,750 --> 00:37:27,810
如何冒泡排序工作。

886
00:37:27,810 --> 00:37:31,130

887
00:37:31,130 --> 00:37:32,155
你还记得吗？

888
00:37:32,155 --> 00:37:32,755
>> 学生：是啊。

889
00:37:32,755 --> 00:37:33,970
>> 讲师：大胆试试吧。

890
00:37:33,970 --> 00:37:38,980
>> 学生：所以你要通过和
如果是做大，那么你交换两个。

891
00:37:38,980 --> 00:37:39,820
>> 指导老师：嗯。

892
00:37:39,820 --> 00:37:40,564
没错。

893
00:37:40,564 --> 00:37:41,730
所以你只要遍历。

894
00:37:41,730 --> 00:37:43,050
您检查两个数字。

895
00:37:43,050 --> 00:37:46,510
如果前一个比较大
比一算账，

896
00:37:46,510 --> 00:37:50,230
你只要将它们使得在
这样一来所有的高数

897
00:37:50,230 --> 00:37:54,990
气泡向着列表的末尾向上
和所有的数字低泡下来。

898
00:37:54,990 --> 00:37:59,355
>> 他有没有告诉你家伙很酷
音效分拣的视频？

899
00:37:59,355 --> 00:38:00,480
这是一种很酷的。

900
00:38:00,480 --> 00:38:01,510

901
00:38:01,510 --> 00:38:05,200
所以罗伯特刚才说的，该算法
您在列表中只是一步，

902
00:38:05,200 --> 00:38:07,930
交换相邻的值
如果他们不正常。

903
00:38:07,930 --> 00:38:10,975
然后自顾自地重复
直到你不作任何交换。

904
00:38:10,975 --> 00:38:11,990

905
00:38:11,990 --> 00:38:12,740
所以，还不错吧？

906
00:38:12,740 --> 00:38:14,080

907
00:38:14,080 --> 00:38:16,319
所以我们只需要一个简单的例子在这里。

908
00:38:16,319 --> 00:38:18,360
所以，这是怎么回事排序
他们按升序排列。

909
00:38:18,360 --> 00:38:19,470

910
00:38:19,470 --> 00:38:23,470
所以，当我们经过第一
时间，我们期待通过八个

911
00:38:23,470 --> 00:38:26,880
六显然不
为了我们交换它们。

912
00:38:26,880 --> 00:38:27,985
>> 所以，看看下一个。

913
00:38:27,985 --> 00:38:29,430
八，以4没有。

914
00:38:29,430 --> 00:38:30,450
交换它们。

915
00:38:30,450 --> 00:38:32,530
然后8两，交换它们。

916
00:38:32,530 --> 00:38:33,470
在那里，我们走了。

917
00:38:33,470 --> 00:38:39,519
所以，你第一遍之后，你
知道你最多

918
00:38:39,519 --> 00:38:41,810
将是一路
在顶部，因为它只是

919
00:38:41,810 --> 00:38:44,210
要不断地
比一切更大

920
00:38:44,210 --> 00:38:46,810
它只是将泡沫
向上一路到底那里。

921
00:38:46,810 --> 00:38:48,226
这是否有道理给大家？

922
00:38:48,226 --> 00:38:48,560

923
00:38:48,560 --> 00:38:49,060
凉爽。

924
00:38:49,060 --> 00:38:51,310

925
00:38:51,310 --> 00:38:53,920
>> 所以，接下来我们来看看我们的第二次。

926
00:38:53,920 --> 00:38:54,980
6个和4，开关。

927
00:38:54,980 --> 00:38:55,920
六两，开关。

928
00:38:55,920 --> 00:38:58,700
现在我们有为了几件事情。

929
00:38:58,700 --> 00:39:02,240
因此，对于每一个传球，我们
让我们的整个列表，

930
00:39:02,240 --> 00:39:06,320
我们知道，像许多号码
在年底将被排序。

931
00:39:06,320 --> 00:39:07,690

932
00:39:07,690 --> 00:39:09,610
所以我们做了第三次，
这是一个交换。

933
00:39:09,610 --> 00:39:10,860

934
00:39:10,860 --> 00:39:15,910
然后在我们的第四个
过去，我们是零插槽。

935
00:39:15,910 --> 00:39:18,570
因此，我们知道，我们的
数组已排序。

936
00:39:18,570 --> 00:39:20,900
>> 那就是大
与冒泡排序的事情。

937
00:39:20,900 --> 00:39:23,720
我们知道，当我们
具有零掉期，即

938
00:39:23,720 --> 00:39:26,497
意味着一切
是完整的订单。

939
00:39:26,497 --> 00:39:27,580
这是一种怎样检查。

940
00:39:27,580 --> 00:39:28,740

941
00:39:28,740 --> 00:39:36,480
因此，我们也要去泡代码
排序也并不坏。

942
00:39:36,480 --> 00:39:38,120
这些都不是那么糟糕。

943
00:39:38,120 --> 00:39:40,210
我知道他们看起来有点吓人。

944
00:39:40,210 --> 00:39:42,124
我知道，当我把
类，甚至当我

945
00:39:42,124 --> 00:39:44,290
教的班
第一次，去年，

946
00:39:44,290 --> 00:39:46,165
我当时想，我该怎么办呢？

947
00:39:46,165 --> 00:39:48,540
是有意义的理论，但
我们如何真正做到这一点？

948
00:39:48,540 --> 00:39:51,420
这就是为什么我还不想走
通过与你们这里的代码。

949
00:39:51,420 --> 00:39:54,915
所以，我有一个伪
对你们这段时间。

950
00:39:54,915 --> 00:39:55,950

951
00:39:55,950 --> 00:39:58,970
因此，只要记住这一点作为
我们要转型了。

952
00:39:58,970 --> 00:40:04,210
因此，我们有一些反了
让我们的掉期交易的轨道，

953
00:40:04,210 --> 00:40:08,370
因为我们需要确保
我们正在检查。

954
00:40:08,370 --> 00:40:11,830
我们遍历整个数组
因为我们只是做了这个例子。

955
00:40:11,830 --> 00:40:12,900

956
00:40:12,900 --> 00:40:17,325
如果元素之前大于
之后，我们是在元素，

957
00:40:17,325 --> 00:40:20,760
我们交换他们，我们增加我们的
计数器，因为只要我们交换，

958
00:40:20,760 --> 00:40:23,850
我们要让我们的柜台都知道。

959
00:40:23,850 --> 00:40:26,247
有什么问题吗？

960
00:40:26,247 --> 00:40:27,580
有些事情似乎好笑在这里。

961
00:40:27,580 --> 00:40:29,225

962
00:40:29,225 --> 00:40:32,350
学生：你设置计数器为零
每次经过循环？

963
00:40:32,350 --> 00:40:34,339
难道你不坚持下去
回零每次？

964
00:40:34,339 --> 00:40:35,505
讲师：不一定。

965
00:40:35,505 --> 00:40:39,710
那么，什么情况是我们经过这里。

966
00:40:39,710 --> 00:40:43,830
所以，做一段时间，记住，这
将执行一次没有失败。

967
00:40:43,830 --> 00:40:46,480
因此，它会设置
计数器等于零，

968
00:40:46,480 --> 00:40:48,070
然后，它会遍历。

969
00:40:48,070 --> 00:40:50,590
由于它遍历，
它会更新计数器。

970
00:40:50,590 --> 00:40:51,870

971
00:40:51,870 --> 00:40:56,900
由于它更新计数器，当它完成，
当它到达数组的末尾，

972
00:40:56,900 --> 00:41:00,830
如果我们的名单还没有被排序，
计数器将被更新。

973
00:41:00,830 --> 00:41:01,840

974
00:41:01,840 --> 00:41:07,150
>> 那样的话就检查情况，并
说，OK，就是柜台大于零。

975
00:41:07,150 --> 00:41:09,290
如果是，再这样做。

976
00:41:09,290 --> 00:41:14,340
要重置，这样，当你
经过，计数器等于零。

977
00:41:14,340 --> 00:41:18,240
如果你通过一个排序
阵，没有什么变化，

978
00:41:18,240 --> 00:41:21,355
失败了，你
返回的排序列表。

979
00:41:21,355 --> 00:41:23,104

980
00:41:23,104 --> 00:41:24,020
这是否有道理？

981
00:41:24,020 --> 00:41:24,940

982
00:41:24,940 --> 00:41:26,356
学生：它可能在一点点。

983
00:41:26,356 --> 00:41:27,147
讲师：OK。

984
00:41:27,147 --> 00:41:28,980
如果有任何其他
问题的出现。

985
00:41:28,980 --> 00:41:30,180

986
00:41:30,180 --> 00:41:30,680
是的。

987
00:41:30,680 --> 00:41:33,760
>> 学生：你会的功能
对于交换的元素呢？

988
00:41:33,760 --> 00:41:36,900
>> 讲师：所以我们其实可以写
如果我们现在要的权利。

989
00:41:36,900 --> 00:41:37,801

990
00:41:37,801 --> 00:41:38,300
凉爽。

991
00:41:38,300 --> 00:41:42,155
所以，关于这一点，艾莉森是怎么回事
切换回设备。

992
00:41:42,155 --> 00:41:43,080
这将很有趣。

993
00:41:43,080 --> 00:41:45,170

994
00:41:45,170 --> 00:41:47,390
我们有我们的好
在这里冒泡排序的事情。

995
00:41:47,390 --> 00:41:50,800
所以，我已经做了骑自行车
通过该阵列。

996
00:41:50,800 --> 00:41:53,030
我们有我们互换了
都等于零。

997
00:41:53,030 --> 00:41:54,480

998
00:41:54,480 --> 00:41:58,440
因此，我们要交换相邻
元素，如果他们太过份了。

999
00:41:58,440 --> 00:42:03,020
所以，第一件事，我们需要
做的是通过我们的数组遍历。

1000
00:42:03,020 --> 00:42:04,500

1001
00:42:04,500 --> 00:42:08,260
>> 那么，你如何认为我们也许
通过我们遍历数组？

1002
00:42:08,260 --> 00:42:09,720

1003
00:42:09,720 --> 00:42:13,990
我们有和我等于0。

1004
00:42:13,990 --> 00:42:16,950

1005
00:42:16,950 --> 00:42:22,454
我们希望我要少
大于n减1负ķ。

1006
00:42:22,454 --> 00:42:23,870
我会解释说，在第二。

1007
00:42:23,870 --> 00:42:26,280

1008
00:42:26,280 --> 00:42:32,830
所以这是一个最优化在这些地方，
记得我每次传球后是怎么说的

1009
00:42:32,830 --> 00:42:36,655
通过数组我们
知道什么是on--

1010
00:42:36,655 --> 00:42:43,590

1011
00:42:43,590 --> 00:42:46,295
>> 打完一遍我们
知道这是排序。

1012
00:42:46,295 --> 00:42:47,370

1013
00:42:47,370 --> 00:42:50,060
经过两道我们知道
这一切进行排序。

1014
00:42:50,060 --> 00:42:52,750
经过三关我们
知道的排序。

1015
00:42:52,750 --> 00:42:55,620
所以，我现在的迭代
通过阵列这里，

1016
00:42:55,620 --> 00:43:01,090
是它确保只有走
通过我们所知道的是未排序的。

1017
00:43:01,090 --> 00:43:01,644
行？

1018
00:43:01,644 --> 00:43:02,810
这只是一个优化。

1019
00:43:02,810 --> 00:43:04,430

1020
00:43:04,430 --> 00:43:08,210
你可以写它只是天真
通过迭代的一切，

1021
00:43:08,210 --> 00:43:09,970
它只是需要更长的时间。

1022
00:43:09,970 --> 00:43:12,470
与此四环路是
一个不错的优化

1023
00:43:12,470 --> 00:43:18,460
因为我们知道，以后每满
通过数组迭代这里，

1024
00:43:18,460 --> 00:43:24,050
喜欢这里的每一个完整的循环，我们知道
一个多这些元素

1025
00:43:24,050 --> 00:43:25,760
在最后进行排序。

1026
00:43:25,760 --> 00:43:28,294
>> 所以我们不必担心这些。

1027
00:43:28,294 --> 00:43:29,710
这是否有道理给大家？

1028
00:43:29,710 --> 00:43:30,950
很酷的小把戏？

1029
00:43:30,950 --> 00:43:32,060

1030
00:43:32,060 --> 00:43:37,270
因此，在这种情况下，如果
我们通过迭代，

1031
00:43:37,270 --> 00:43:50,590
我们知道，我们要检查
数组n和n加1是为了。

1032
00:43:50,590 --> 00:43:52,640

1033
00:43:52,640 --> 00:43:53,559
行。

1034
00:43:53,559 --> 00:43:54,600
因此，这里的伪代码。

1035
00:43:54,600 --> 00:43:57,540
我们要检查数组ñ
和N加1是为了。

1036
00:43:57,540 --> 00:43:59,520
那么，什么可能我们有吗？

1037
00:43:59,520 --> 00:44:01,090

1038
00:44:01,090 --> 00:44:03,120
这将是一些条件。

1039
00:44:03,120 --> 00:44:04,220
这将是如果一个。

1040
00:44:04,220 --> 00:44:07,066
>> 学生：如果array n是
比数组n与1少。

1041
00:44:07,066 --> 00:44:07,816
指导老师：嗯。

1042
00:44:07,816 --> 00:44:09,000

1043
00:44:09,000 --> 00:44:10,699
那么，小于或大于。

1044
00:44:10,699 --> 00:44:11,615
学生：大于。

1045
00:44:11,615 --> 00:44:15,850

1046
00:44:15,850 --> 00:44:17,620
然后，我们要交换他们。

1047
00:44:17,620 --> 00:44:18,570
没错。

1048
00:44:18,570 --> 00:44:23,570
所以，现在我们进入有什么
机制交换呢？

1049
00:44:23,570 --> 00:44:24,840

1050
00:44:24,840 --> 00:44:28,137
因此，我们通过这个简短去了，
一种交换功能的最后一周。

1051
00:44:28,137 --> 00:44:29,595
有谁还记得它是如何工作的？

1052
00:44:29,595 --> 00:44:32,300

1053
00:44:32,300 --> 00:44:34,950
因此，我们不能只是重新分配，对不对？

1054
00:44:34,950 --> 00:44:36,640
因为其中一人将得到丢失。

1055
00:44:36,640 --> 00:44:41,696
如果我们说，A等于B，然后B
等于A，突然两个人

1056
00:44:41,696 --> 00:44:43,150
只是等于B.

1057
00:44:43,150 --> 00:44:45,720
>> 所以，我们要做的是我们
有一个临时变量，是

1058
00:44:45,720 --> 00:44:49,055
将要举办的我们，而一个
我们在交换的过程中。

1059
00:44:49,055 --> 00:44:50,200

1060
00:44:50,200 --> 00:44:56,464
所以，我们所拥有的是我们​​有一些INT
温度等于to--你可以指定它

1061
00:44:56,464 --> 00:44:59,130
到任何一个你想要的，只是
请确保你跟踪它 - 的

1062
00:44:59,130 --> 00:45:01,840
所以在这种情况下，我要去
它分配给数组n与1。

1063
00:45:01,840 --> 00:45:03,360

1064
00:45:03,360 --> 00:45:07,674
所以这是将要举办什么
值是在该第二块

1065
00:45:07,674 --> 00:45:08,590
我们正在寻找。

1066
00:45:08,590 --> 00:45:09,700

1067
00:45:09,700 --> 00:45:13,240
>> 然后我们可以做的是，我们可以去
提前并重新分配数组n与1，

1068
00:45:13,240 --> 00:45:14,990
因为我们知道，我们
有存储该值。

1069
00:45:14,990 --> 00:45:16,645

1070
00:45:16,645 --> 00:45:19,270
这也是大的一个
things--我不知道你们中的任何

1071
00:45:19,270 --> 00:45:23,780
曾：如果你切换的两个问题
代码行突然事情的来龙去脉。

1072
00:45:23,780 --> 00:45:25,880
为了在CS非常重要的。

1073
00:45:25,880 --> 00:45:29,450
所以一定要确保你关系图
事情是否可能

1074
00:45:29,450 --> 00:45:31,230
至于什么是实际发生的事情。

1075
00:45:31,230 --> 00:45:34,256
所以，现在我们要
重新分配数组n与1，

1076
00:45:34,256 --> 00:45:36,005
因为我们知道，我们
有存储该值。

1077
00:45:36,005 --> 00:45:37,090

1078
00:45:37,090 --> 00:45:41,560
>> 我们可以将它赋值给数组
在这种情况下，阵列I n或。

1079
00:45:41,560 --> 00:45:50,540

1080
00:45:50,540 --> 00:45:51,465
太多的变数。

1081
00:45:51,465 --> 00:45:54,230

1082
00:45:54,230 --> 00:45:55,470
行。

1083
00:45:55,470 --> 00:46:01,500
所以，现在我们已经重新分配数组我
加1等于什么阵我。

1084
00:46:01,500 --> 00:46:08,240
现在我们可以回去
分配数组我的是什么？

1085
00:46:08,240 --> 00:46:10,680

1086
00:46:10,680 --> 00:46:11,180
任何人吗？

1087
00:46:11,180 --> 00:46:13,490

1088
00:46:13,490 --> 00:46:14,010
>> 学生：10。

1089
00:46:14,010 --> 00:46:14,680
>> 讲师：10。

1090
00:46:14,680 --> 00:46:15,180
没错。

1091
00:46:15,180 --> 00:46:16,930

1092
00:46:16,930 --> 00:46:18,640
而最后一件事。

1093
00:46:18,640 --> 00:46:21,840
如果我们现在已经换了，
什么，我们需要做什么？

1094
00:46:21,840 --> 00:46:23,740
什么是一件事
这是怎么回事告诉我们

1095
00:46:23,740 --> 00:46:27,542
如果我们终止这项计划？

1096
00:46:27,542 --> 00:46:29,250
什么告诉我们
有一个排序的列表？

1097
00:46:29,250 --> 00:46:31,560

1098
00:46:31,560 --> 00:46:33,750
如果我们不进行任何交换，对不对？

1099
00:46:33,750 --> 00:46:36,900
如果互换等于
在此结束零。

1100
00:46:36,900 --> 00:46:42,975
所以每当你完成一个交换，因为我们
只是在这里做，我们要更新掉。

1101
00:46:42,975 --> 00:46:45,002

1102
00:46:45,002 --> 00:46:47,210
我知道有一个
刚才的问题能左右你

1103
00:46:47,210 --> 00:46:49,689
用零次或一次，而不是
true或false。

1104
00:46:49,689 --> 00:46:50,980
而这正是这并不在这里。

1105
00:46:50,980 --> 00:46:52,750
因此，这如果不是掉期说。

1106
00:46:52,750 --> 00:47:01,310
所以，如果掉期为零，这is--我总是
让我的真理，我falses混淆。

1107
00:47:01,310 --> 00:47:03,960
我们希望我们能够评估
以真实，事实并非如此。

1108
00:47:03,960 --> 00:47:07,680

1109
00:47:07,680 --> 00:47:09,630
所以，如果是零，那么它是假的。

1110
00:47:09,630 --> 00:47:12,560
如果你有一个否定它
[？一声？]成为事实。

1111
00:47:12,560 --> 00:47:13,975
那么接下来这条线执行。

1112
00:47:13,975 --> 00:47:15,060

1113
00:47:15,060 --> 00:47:17,370
>> 真理与虚假，
零和一弄疯了。

1114
00:47:17,370 --> 00:47:20,690
只是，如果你慢慢走
通过它它才有意义。

1115
00:47:20,690 --> 00:47:23,320
但是，这就是这个小
代码位在这里呢。

1116
00:47:23,320 --> 00:47:26,490
因此，这将检查
我们做任何交换。

1117
00:47:26,490 --> 00:47:30,054
所以，如果它的任何东西，除了
零，这将是错误的

1118
00:47:30,054 --> 00:47:31,970
而整个事情是
要再次执行。

1119
00:47:31,970 --> 00:47:33,150

1120
00:47:33,150 --> 00:47:33,650
酷？

1121
00:47:33,650 --> 00:47:34,660

1122
00:47:34,660 --> 00:47:36,000
>> 学生：什么突破呢？

1123
00:47:36,000 --> 00:47:38,990
>> 讲师：刚刚突破
打破你跳出循环。

1124
00:47:38,990 --> 00:47:41,570
所以在这种情况下，它会
只是想结束程序

1125
00:47:41,570 --> 00:47:43,828
而你只想
有你的排序列表。

1126
00:47:43,828 --> 00:47:44,536
学生：惊人的。

1127
00:47:44,536 --> 00:47:48,094

1128
00:47:48,094 --> 00:47:49,010
讲师：对不起？

1129
00:47:49,010 --> 00:47:52,110
学生：因为以前我们
用过写1比写零

1130
00:47:52,110 --> 00:47:54,170
提出，如果
将工作或没有。

1131
00:47:54,170 --> 00:47:54,878
>> 指导老师：是啊。

1132
00:47:54,878 --> 00:47:56,410
所以，你可以返回零个或1。

1133
00:47:56,410 --> 00:47:58,950
在这种情况下，因为我们没有真正
做什么用的功能，

1134
00:47:58,950 --> 00:48:00,150
我们只是希望它打破。

1135
00:48:00,150 --> 00:48:02,680
我们真的不关心它。

1136
00:48:02,680 --> 00:48:06,960
刹车也不错，如果
它是用于突破

1137
00:48:06,960 --> 00:48:10,710
四个环或条件的那
你不希望继续执行。

1138
00:48:10,710 --> 00:48:12,110
它只是需要你了出来。

1139
00:48:12,110 --> 00:48:13,587

1140
00:48:13,587 --> 00:48:14,795
这是一个有点细微的事情。

1141
00:48:14,795 --> 00:48:16,737

1142
00:48:16,737 --> 00:48:18,445
我觉得有
很多摆手的，

1143
00:48:18,445 --> 00:48:19,740
就像你将了解这一声。

1144
00:48:19,740 --> 00:48:20,955
>> 但是，你将了解这一声。

1145
00:48:20,955 --> 00:48:21,500
我保证。

1146
00:48:21,500 --> 00:48:22,670

1147
00:48:22,670 --> 00:48:23,170
行。

1148
00:48:23,170 --> 00:48:24,840
因此，每个人都得到冒泡排序？

1149
00:48:24,840 --> 00:48:25,550
差不太多。

1150
00:48:25,550 --> 00:48:31,910
遍历，使用交换的东西
临时变量，我们都设在那里？

1151
00:48:31,910 --> 00:48:32,960
凉爽。

1152
00:48:32,960 --> 00:48:34,080
真棒。

1153
00:48:34,080 --> 00:48:34,807
行。

1154
00:48:34,807 --> 00:48:35,765
回到PowerPoint文件。

1155
00:48:35,765 --> 00:48:38,140

1156
00:48:38,140 --> 00:48:40,130
一般来说任何问题
这些这么远吗？

1157
00:48:40,130 --> 00:48:41,200

1158
00:48:41,200 --> 00:48:41,700
凉爽。

1159
00:48:41,700 --> 00:48:43,110

1160
00:48:43,110 --> 00:48:43,695
嗯。

1161
00:48:43,695 --> 00:48:45,279
>> 学生：[听不清]诠释主通常。

1162
00:48:45,279 --> 00:48:46,695
你必须有这个？

1163
00:48:46,695 --> 00:48:48,400

1164
00:48:48,400 --> 00:48:53,550
>> 讲师：所以我们只是在寻找
只是在实际的排序算法。

1165
00:48:53,550 --> 00:48:54,559

1166
00:48:54,559 --> 00:48:56,350
如果你在有它
像一个更大的程序，

1167
00:48:56,350 --> 00:48:57,891
你将有一个int的主要地方。

1168
00:48:57,891 --> 00:49:00,070

1169
00:49:00,070 --> 00:49:02,880
这取决于你在哪里
使用这种算法，

1170
00:49:02,880 --> 00:49:05,860
这将决定什么
由它返回。

1171
00:49:05,860 --> 00:49:09,960
但对于我们而言，我们是严格
着眼于如何真正做这个

1172
00:49:09,960 --> 00:49:11,300
遍历数组。

1173
00:49:11,300 --> 00:49:12,570
所以，我们并不担心。

1174
00:49:12,570 --> 00:49:14,150

1175
00:49:14,150 --> 00:49:19,830
>> 因此，我们在谈论最好的情况和
最坏的情况下为二进制搜索。

1176
00:49:19,830 --> 00:49:22,470
因此，这也是非常重要的做
对于每一个我们的排序。

1177
00:49:22,470 --> 00:49:24,200

1178
00:49:24,200 --> 00:49:27,560
所以你认为是什么做的是最差的
冒泡排序的情况下运行？

1179
00:49:27,560 --> 00:49:29,560

1180
00:49:29,560 --> 00:49:30,700
你们还记得吗？

1181
00:49:30,700 --> 00:49:31,784
>> 学生：N减1。

1182
00:49:31,784 --> 00:49:32,700
讲师：N减1。

1183
00:49:32,700 --> 00:49:35,070
因此，这意味着有
ñ减1的比较。

1184
00:49:35,070 --> 00:49:40,060
所以，有一点认识是
即在第一次迭代中，

1185
00:49:40,060 --> 00:49:43,360
我们经历，我们比较
这些two--所以这是1。

1186
00:49:43,360 --> 00:49:46,685
这两个，三个，四个。

1187
00:49:46,685 --> 00:49:48,070

1188
00:49:48,070 --> 00:49:55,050
所以一次迭代后，我们
已经有四个比较。

1189
00:49:55,050 --> 00:49:58,230
当我说的是运行和n。

1190
00:49:58,230 --> 00:50:04,680
N表示比较的数量
有多少元素的函数

1191
00:50:04,680 --> 00:50:05,570
我们有。

1192
00:50:05,570 --> 00:50:06,430
行？

1193
00:50:06,430 --> 00:50:08,860
>> 因此，我们过不去，我们有四个。

1194
00:50:08,860 --> 00:50:11,780
下一次当你知道我们不
要利用这一服务。

1195
00:50:11,780 --> 00:50:15,140
我们比较这两个，
这两个，这两个，

1196
00:50:15,140 --> 00:50:20,050
如果我们没有这个优化
与四循环，我写的，

1197
00:50:20,050 --> 00:50:22,750
你会比较这里反正。

1198
00:50:22,750 --> 00:50:26,170
所以，你必须
通过阵列上运行

1199
00:50:26,170 --> 00:50:34,380
而从N比较ñ
次，因为每次我们

1200
00:50:34,380 --> 00:50:36,670
运行通过它我们排序的一件事。

1201
00:50:36,670 --> 00:50:38,300

1202
00:50:38,300 --> 00:50:41,475
>> 每次我们通过运行时间
数组，我们从N比较。

1203
00:50:41,475 --> 00:50:42,920

1204
00:50:42,920 --> 00:50:46,330
因此，我们运行的是
实际上Ñ平方，其中

1205
00:50:46,330 --> 00:50:48,400
是更糟糕了
日志末尾，因为这

1206
00:50:48,400 --> 00:50:51,965
也就是说，如果我们有四个
十亿元素，它的

1207
00:50:51,965 --> 00:50:55,260
我们要花费four十亿
平方，而不是32。

1208
00:50:55,260 --> 00:51:01,240
所以不是最好的运行时间，
但对于某些事情，

1209
00:51:01,240 --> 00:51:04,610
你知道，如果你是内
在一定范围内的元素

1210
00:51:04,610 --> 00:51:06,540
冒泡排序可能会比较好用。

1211
00:51:06,540 --> 00:51:07,530
>> 行。

1212
00:51:07,530 --> 00:51:12,290
所以，现在什么是最好的情况下运行？

1213
00:51:12,290 --> 00:51:14,357

1214
00:51:14,357 --> 00:51:14,940
学生：零？

1215
00:51:14,940 --> 00:51:16,420
还是1？

1216
00:51:16,420 --> 00:51:18,140
>> 教师：那么1人
是一次比较。

1217
00:51:18,140 --> 00:51:19,114
右。

1218
00:51:19,114 --> 00:51:20,002
>> 学生：N减1？

1219
00:51:20,002 --> 00:51:21,380

1220
00:51:21,380 --> 00:51:22,320
>> 讲师：所以，是的。

1221
00:51:22,320 --> 00:51:22,990
因此n减1。

1222
00:51:22,990 --> 00:51:26,510
当你有一个像N A概念
减去1，我们往往只是把它关闭

1223
00:51:26,510 --> 00:51:31,680
我们只说N，因为你有
比较每个these--每对。

1224
00:51:31,680 --> 00:51:36,470
所以它会为n减去1，这是我们
我们刚刚说的是大约ñ。

1225
00:51:36,470 --> 00:51:39,280
当你正在处理的运行时间，
一切都在接近。

1226
00:51:39,280 --> 00:51:43,860
只要指数是
正确的，你很不错。

1227
00:51:43,860 --> 00:51:45,700
>> 这就是我们如何处理它。

1228
00:51:45,700 --> 00:51:47,410

1229
00:51:47,410 --> 00:51:51,780
所以，最好的情况下是n，这
意味着该列表已经排序，

1230
00:51:51,780 --> 00:51:54,320
而我们要做的就是通过运行
并检查它的排序。

1231
00:51:54,320 --> 00:51:56,110

1232
00:51:56,110 --> 00:51:56,855
凉爽。

1233
00:51:56,855 --> 00:51:57,355
行。

1234
00:51:57,355 --> 00:51:58,980

1235
00:51:58,980 --> 00:52:01,920
所以，当你看到这里，我们
只是有一些更多的图形。

1236
00:52:01,920 --> 00:52:02,660
因此n的平方。

1237
00:52:02,660 --> 00:52:03,780

1238
00:52:03,780 --> 00:52:05,120
好玩的。

1239
00:52:05,120 --> 00:52:09,730
远小于n更糟，因为我们看到了，
多，比数2n个糟糕得多。

1240
00:52:09,730 --> 00:52:12,060
然后你也进入日志记录。

1241
00:52:12,060 --> 00:52:18,020
你拿124，你进入
像日志的明星，这是像疯了似的。

1242
00:52:18,020 --> 00:52:20,172
所以，如果你有兴趣，
查询日志的明星。

1243
00:52:20,172 --> 00:52:20,880
这是一种乐趣。

1244
00:52:20,880 --> 00:52:22,800

1245
00:52:22,800 --> 00:52:24,220
因此，我们有这个伟大的图表。

1246
00:52:24,220 --> 00:52:25,360

1247
00:52:25,360 --> 00:52:28,720
只是抬起头，这是一个
精彩图有

1248
00:52:28,720 --> 00:52:31,350
为您的中期，因为我们
长问你这些变薄。

1249
00:52:31,350 --> 00:52:36,090
所以才抬起头来，这个对你
对你的好小抄中期

1250
00:52:36,090 --> 00:52:36,616
那里。

1251
00:52:36,616 --> 00:52:37,990
所以，我们只是看着冒泡排序。

1252
00:52:37,990 --> 00:52:39,510

1253
00:52:39,510 --> 00:52:42,370
最坏的情况下，N的平方，最好的情况下，N。

1254
00:52:42,370 --> 00:52:43,367

1255
00:52:43,367 --> 00:52:44,950
而且我们要看看其他人。

1256
00:52:44,950 --> 00:52:47,940
>> 正如你所看到的，唯一的
一个真正做得好

1257
00:52:47,940 --> 00:52:50,910
是归并排序，我们将进入的原因。

1258
00:52:50,910 --> 00:52:52,690

1259
00:52:52,690 --> 00:52:55,215
所以我们要去的
下一个这里 - 选择排序。

1260
00:52:55,215 --> 00:52:56,360

1261
00:52:56,360 --> 00:52:58,420
有谁还记得
选择排序工作？

1262
00:52:58,420 --> 00:53:05,200

1263
00:53:05,200 --> 00:53:05,700
去了。

1264
00:53:05,700 --> 00:53:08,210
>> 学生：基本上经历
一种秩序，创造一个新的列表。

1265
00:53:08,210 --> 00:53:11,001
而且，正如你把元素
中，把他们在正确的地方

1266
00:53:11,001 --> 00:53:11,750
在新的清单。

1267
00:53:11,750 --> 00:53:14,040
>> 讲师：这样的声音
更像是插入排序。

1268
00:53:14,040 --> 00:53:15,040
但是你真的很近。

1269
00:53:15,040 --> 00:53:15,915
他们是非常相似的。

1270
00:53:15,915 --> 00:53:17,440
就算我让他们混在一起的时候。

1271
00:53:17,440 --> 00:53:18,981
这部分我像以前一样，等待。

1272
00:53:18,981 --> 00:53:20,130

1273
00:53:20,130 --> 00:53:20,630
行。

1274
00:53:20,630 --> 00:53:24,141
所以，你要
做的是选择排序，

1275
00:53:24,141 --> 00:53:25,890
你能想到的方式
它和方式

1276
00:53:25,890 --> 00:53:30,140
我要确保我尽量不要让
它们混合起来，是它通过

1277
00:53:30,140 --> 00:53:33,280
的情况下选择
最小数目和它

1278
00:53:33,280 --> 00:53:36,070
提出，在列表的开头。

1279
00:53:36,070 --> 00:53:37,730
它交换它与第一点。

1280
00:53:37,730 --> 00:53:42,600

1281
00:53:42,600 --> 00:53:45,370
他们居然对我有一个例子。

1282
00:53:45,370 --> 00:53:46,540
真棒。

1283
00:53:46,540 --> 00:53:50,130
所以，只是一个方式去思考它 - 选择
排序，选择最小的值。

1284
00:53:50,130 --> 00:53:51,940
而我们要
通过一个实例运行

1285
00:53:51,940 --> 00:53:55,320
我认为这将有助于因
我觉得视觉效果总是帮助。

1286
00:53:55,320 --> 00:53:58,510
因此，我们的东西开始了
这是完全无序。

1287
00:53:58,510 --> 00:54:00,730
红会未排序的，
绿色进行排序。

1288
00:54:00,730 --> 00:54:02,190
它将所有的意义在第二。

1289
00:54:02,190 --> 00:54:08,950
>> 所以，我们通过我们遍历
从开始到结束。

1290
00:54:08,950 --> 00:54:12,320
我们说好，2
我们最小的号码。

1291
00:54:12,320 --> 00:54:15,680
因此，我们要采取2，我们要
将它移动到我们的数组的前面

1292
00:54:15,680 --> 00:54:17,734
因为它是
最小数，我们有。

1293
00:54:17,734 --> 00:54:19,150
所以，这就是这是在这里做。

1294
00:54:19,150 --> 00:54:20,820
它只是要交换这两个。

1295
00:54:20,820 --> 00:54:21,850

1296
00:54:21,850 --> 00:54:25,450
所以，现在我们有一个排序
部分和未分类的一部分。

1297
00:54:25,450 --> 00:54:27,810
什么是好记
关于选择排序

1298
00:54:27,810 --> 00:54:30,690
是我们唯一的选择
从无序的一部分。

1299
00:54:30,690 --> 00:54:32,220

1300
00:54:32,220 --> 00:54:34,527
>> 排序的一部分，你只是独自离开。

1301
00:54:34,527 --> 00:54:35,660
嗯？

1302
00:54:35,660 --> 00:54:38,452
>> 学生：它是如何知道什么是
最小无它比较

1303
00:54:38,452 --> 00:54:39,868
到阵列中的每一个其它值。

1304
00:54:39,868 --> 00:54:41,250
讲师：它确实进行比较。

1305
00:54:41,250 --> 00:54:42,041
我们喜欢跳过它。

1306
00:54:42,041 --> 00:54:43,850
这只是一般的整体。

1307
00:54:43,850 --> 00:54:44,831
是啊。

1308
00:54:44,831 --> 00:54:47,205
当我们编写我的代码
相信你会更加满意。

1309
00:54:47,205 --> 00:54:48,696

1310
00:54:48,696 --> 00:54:53,030
但是，你保存这第一
元件为最小。

1311
00:54:53,030 --> 00:54:56,110
你比较，你
说好，是不是更小？

1312
00:54:56,110 --> 00:54:56,660
是的。

1313
00:54:56,660 --> 00:54:57,460
保留它。

1314
00:54:57,460 --> 00:54:58,640
这里是小？

1315
00:54:58,640 --> 00:54:59,660
不是吗？

1316
00:54:59,660 --> 00:55:02,510
>> 这是你最小，
它重新分配给你的价值。

1317
00:55:02,510 --> 00:55:06,340
你会感到非常的快乐
当我们通过代码。

1318
00:55:06,340 --> 00:55:07,510

1319
00:55:07,510 --> 00:55:13,970
因此，我们过不去，我们交换了，所以再
我们看一下这个排序的部分。

1320
00:55:13,970 --> 00:55:15,810
所以，我们要选择三个出来。

1321
00:55:15,810 --> 00:55:18,890
我们打​​算把它在
我们的排序的部分的端部。

1322
00:55:18,890 --> 00:55:20,267

1323
00:55:20,267 --> 00:55:23,100
而我们只是要继续做
这，做那，而这样做。

1324
00:55:23,100 --> 00:55:24,130

1325
00:55:24,130 --> 00:55:27,420
因此，这是我们的一种伪这里。

1326
00:55:27,420 --> 00:55:29,470

1327
00:55:29,470 --> 00:55:31,380
我们将在这里编写它在一秒钟。

1328
00:55:31,380 --> 00:55:34,140

1329
00:55:34,140 --> 00:55:37,270
但只是一些走
通过在一个高的水平。

1330
00:55:37,270 --> 00:55:40,275
你会从去
i等于0到n减去2。

1331
00:55:40,275 --> 00:55:41,570

1332
00:55:41,570 --> 00:55:43,530
这是另一种优化。

1333
00:55:43,530 --> 00:55:45,020
不要太担心了。

1334
00:55:45,020 --> 00:55:46,620
所以，当你在说什么。

1335
00:55:46,620 --> 00:55:49,660

1336
00:55:49,660 --> 00:55:54,406
正如雅各说，我们怎么
跟踪我们什么是最小的？

1337
00:55:54,406 --> 00:55:55,030
我们怎么知道？

1338
00:55:55,030 --> 00:55:57,060
我们来比较
一切都在我们的名单。

1339
00:55:57,060 --> 00:55:59,600
>> 因此，最小等于我。

1340
00:55:59,600 --> 00:56:03,870
它只是说，在这种情况下，
我们的最低值的索引。

1341
00:56:03,870 --> 00:56:07,660
这样的话它会遍历
而它从j为我加1。

1342
00:56:07,660 --> 00:56:11,420
因此，我们已经知道，
这是我们的第一个元素。

1343
00:56:11,420 --> 00:56:13,240
我们不必把它比作自己。

1344
00:56:13,240 --> 00:56:16,970
所以，我们开始把它比作下一个
1这就是为什么它是我加1到n

1345
00:56:16,970 --> 00:56:20,110
减1，这是
阵列那里的端部。

1346
00:56:20,110 --> 00:56:25,090
我们说，如果数组
j是小于阵列分钟，

1347
00:56:25,090 --> 00:56:29,200
那么，我们在那里重新分配
我们的最低指标是。

1348
00:56:29,200 --> 00:56:37,470
>> 而如果分不等于i，如
在这里我们又回到了这里。

1349
00:56:37,470 --> 00:56:38,950

1350
00:56:38,950 --> 00:56:41,790
所以像我们当初做这个。

1351
00:56:41,790 --> 00:56:49,310
在这种情况下，它会开始
零，这将最终被两人。

1352
00:56:49,310 --> 00:56:53,010
所以分也不会等于我到底。

1353
00:56:53,010 --> 00:56:55,720
让我们知道，
我们需要交换它们。

1354
00:56:55,720 --> 00:56:57,420

1355
00:56:57,420 --> 00:57:00,470
我觉得自己像一个具体的例子
将帮助远不止此。

1356
00:57:00,470 --> 00:57:04,970
因此，我将这个代码与你们
现在，我认为这将是更好的。

1357
00:57:04,970 --> 00:57:07,380

1358
00:57:07,380 --> 00:57:11,350
>> 排序往往工作方式在
它往往只是为了更好地看到它们。

1359
00:57:11,350 --> 00:57:12,780

1360
00:57:12,780 --> 00:57:17,280
所以我们想要做的是
我们首先需要的最小

1361
00:57:17,280 --> 00:57:19,890
元件在它的阵列中的位置。

1362
00:57:19,890 --> 00:57:21,280
正是雅各说的话。

1363
00:57:21,280 --> 00:57:23,090
你需要存储，不知怎的。

1364
00:57:23,090 --> 00:57:25,900
因此，我们要在这里开始
遍历数组。

1365
00:57:25,900 --> 00:57:28,970
我们会说这是我们的
第一次只是开始。

1366
00:57:28,970 --> 00:57:38,308
因此，我们将不得不INT
最小等于阵列在岛

1367
00:57:38,308 --> 00:57:40,500

1368
00:57:40,500 --> 00:57:45,050
>> 所以，有一点要注意，每
这个时间循环执行，

1369
00:57:45,050 --> 00:57:48,550
我们开始一起又进了一步。

1370
00:57:48,550 --> 00:57:54,780

1371
00:57:54,780 --> 00:57:57,440
当我们开始我们看这一个。

1372
00:57:57,440 --> 00:58:00,840
接下来的时间，我们遍历，
我们已经开始在这一个

1373
00:58:00,840 --> 00:58:02,680
而分配给它我们的最小值。

1374
00:58:02,680 --> 00:58:10,450
所以这是非常相似的冒泡排序
我们知道，一个传球后，

1375
00:58:10,450 --> 00:58:11,700
这最后一个元素进行排序。

1376
00:58:11,700 --> 00:58:12,810

1377
00:58:12,810 --> 00:58:15,120
与选择排序，
它正好相反。

1378
00:58:15,120 --> 00:58:18,950
>> 在每一个传球，我们知道，
第一个是排序。

1379
00:58:18,950 --> 00:58:21,360
第二次通过后，将
第二个将被排序。

1380
00:58:21,360 --> 00:58:26,470
正如你看到的幻灯片的例子，
我们来分类的部分只是不断增长。

1381
00:58:26,470 --> 00:58:34,020
因此，通过设置我们最小的一个
到数组我，所有它做

1382
00:58:34,020 --> 00:58:37,340
收缩是什么
我们正在寻找这样

1383
00:58:37,340 --> 00:58:40,164
最小化的数量
比较我们做。

1384
00:58:40,164 --> 00:58:41,770
这是否有意义大家？

1385
00:58:41,770 --> 00:58:42,920

1386
00:58:42,920 --> 00:58:46,380
你需要我通过运行
再慢，或者在不同的话吗？

1387
00:58:46,380 --> 00:58:47,180
我很高兴。

1388
00:58:47,180 --> 00:58:48,095

1389
00:58:48,095 --> 00:58:48,595
行。

1390
00:58:48,595 --> 00:58:50,060

1391
00:58:50,060 --> 00:58:55,540
>> 因此，我们的存储
在这点上的值，

1392
00:58:55,540 --> 00:58:57,840
但是我们也希望来存储索引。

1393
00:58:57,840 --> 00:59:01,010
所以我们要保存
最小的位置

1394
00:59:01,010 --> 00:59:02,770
1，这是只是要我。

1395
00:59:02,770 --> 00:59:04,357

1396
00:59:04,357 --> 00:59:05,440
所以，现在雅各是满意的。

1397
00:59:05,440 --> 00:59:06,870
我们所储存的东西。

1398
00:59:06,870 --> 00:59:08,240

1399
00:59:08,240 --> 00:59:11,870
现在我们需要看看通过
阵列的未分类的一部分。

1400
00:59:11,870 --> 00:59:18,170
所以在这种情况下，这
将是我们未排序的。

1401
00:59:18,170 --> 00:59:20,980

1402
00:59:20,980 --> 00:59:22,462
这就是我。

1403
00:59:22,462 --> 00:59:25,430

1404
00:59:25,430 --> 00:59:26,210
行。

1405
00:59:26,210 --> 00:59:30,040
>> 所以，我们要做些什么
将是一个循环。

1406
00:59:30,040 --> 00:59:32,066
每当你需要
遍历数组，

1407
00:59:32,066 --> 00:59:33,440
你的头脑会去为一个循环。

1408
00:59:33,440 --> 00:59:34,760

1409
00:59:34,760 --> 00:59:38,090
因此，对于一些INTķ
equals--什么，我们认为

1410
00:59:38,090 --> 00:59:39,700
k被要等于开始？

1411
00:59:39,700 --> 00:59:41,580

1412
00:59:41,580 --> 00:59:44,766
这是我们设置了最小
价值，我们要进行比较。

1413
00:59:44,766 --> 00:59:47,090
我们究竟要比较它？

1414
00:59:47,090 --> 00:59:48,730
这将是该下一个，对不对？

1415
00:59:48,730 --> 00:59:53,200
所以我们要k，进而进行初始化
要我加1开始。

1416
00:59:53,200 --> 00:59:55,350

1417
00:59:55,350 --> 01:00:02,800
>> 我们希望K的这种情况下，我们
已经存储的大小在这里，

1418
01:00:02,800 --> 01:00:03,930
所以我们可以只使用尺寸。

1419
01:00:03,930 --> 01:00:06,240
大小作为数组的大小。

1420
01:00:06,240 --> 01:00:09,620
我们只是想
一，每次更新ķ。

1421
01:00:09,620 --> 01:00:17,410

1422
01:00:17,410 --> 01:00:17,910
凉爽。

1423
01:00:17,910 --> 01:00:19,650

1424
01:00:19,650 --> 01:00:23,430
所以，现在我们需要找到
这里的最小元素。

1425
01:00:23,430 --> 01:00:24,470

1426
01:00:24,470 --> 01:00:31,380
因此，如果我们遍历，我们
想说，如果数组日K

1427
01:00:31,380 --> 01:00:37,080
小于我们最小value--
这就是我们实际上

1428
01:00:37,080 --> 01:00:42,950
跟踪是什么
最小这里 - 

1429
01:00:42,950 --> 01:00:47,740
那么我们要重新分配
就是我们最小的值是。

1430
01:00:47,740 --> 01:00:50,645
>> 这意味着，哦，我们是
迭代经过这里。

1431
01:00:50,645 --> 01:00:51,699

1432
01:00:51,699 --> 01:00:53,740
无论值是这里
不是我们最小的事情。

1433
01:00:53,740 --> 01:00:54,448
我们不希望它。

1434
01:00:54,448 --> 01:00:56,100
我们要重新分配它。

1435
01:00:56,100 --> 01:01:02,050
所以，如果我们要重新分配它，做什么
你觉得可能是这里的代码？

1436
01:01:02,050 --> 01:01:04,160
我们要重新分配
最小的位置。

1437
01:01:04,160 --> 01:01:05,740

1438
01:01:05,740 --> 01:01:07,010
还等什么，现在是最小的？

1439
01:01:07,010 --> 01:01:08,422

1440
01:01:08,422 --> 01:01:09,130
学生：列K。

1441
01:01:09,130 --> 01:01:09,963
讲师：列K。

1442
01:01:09,963 --> 01:01:13,480

1443
01:01:13,480 --> 01:01:15,956
是什么位置呢？

1444
01:01:15,956 --> 01:01:20,940

1445
01:01:20,940 --> 01:01:23,000
什么的指数
我们最小的价值？

1446
01:01:23,000 --> 01:01:24,030

1447
01:01:24,030 --> 01:01:24,530
它只是ķ。

1448
01:01:24,530 --> 01:01:25,690

1449
01:01:25,690 --> 01:01:27,790
所以列K中，k，它们相匹配。

1450
01:01:27,790 --> 01:01:31,670

1451
01:01:31,670 --> 01:01:33,120
因此，我们要重新分配。

1452
01:01:33,120 --> 01:01:34,390

1453
01:01:34,390 --> 01:01:39,950
再之后，我们发现我们最小的，
因此在今年年底for循环

1454
01:01:39,950 --> 01:01:45,100
在这里我们找到了我们的最小
值，所以我们只是换了。

1455
01:01:45,100 --> 01:01:47,100

1456
01:01:47,100 --> 01:01:50,816
在这种情况下，像说我们的
最小值是出在这里。

1457
01:01:50,816 --> 01:01:51,940
这是我们的最小值。

1458
01:01:51,940 --> 01:01:57,690
>> 我们只是想在这里交换，这是
是什么在底部的交换功能

1459
01:01:57,690 --> 01:02:01,270
的确，这是我们刚刚写了
同时几分钟前。

1460
01:02:01,270 --> 01:02:02,775
所以它应该很熟悉。

1461
01:02:02,775 --> 01:02:04,320

1462
01:02:04,320 --> 01:02:08,030
然后它只会重复
通过直到它到达一路

1463
01:02:08,030 --> 01:02:13,100
到结束，这意味着你
具有零个元素是无序

1464
01:02:13,100 --> 01:02:14,800
和其他一切已排序。

1465
01:02:14,800 --> 01:02:16,216

1466
01:02:16,216 --> 01:02:16,715
有意义吗？

1467
01:02:16,715 --> 01:02:18,010

1468
01:02:18,010 --> 01:02:19,280
有一点更具体？

1469
01:02:19,280 --> 01:02:19,990
该代码的帮助？

1470
01:02:19,990 --> 01:02:21,720

1471
01:02:21,720 --> 01:02:26,410
>> 学生：对于一个规模，你永远不
真正定义它或改变它，

1472
01:02:26,410 --> 01:02:27,340
它是怎么知道的？

1473
01:02:27,340 --> 01:02:32,380
>> 教师：那么一回事，
注意在这里为int的大小。

1474
01:02:32,380 --> 01:02:35,680
所以我们说在这个类别 - 排序
是在这样的函数case--它

1475
01:02:35,680 --> 01:02:40,770
选择排序，它通过
同的功能。

1476
01:02:40,770 --> 01:02:43,460
所以，如果它没有通过
中，你会做什么

1477
01:02:43,460 --> 01:02:47,840
像与所述阵列的长度
或者你会遍历

1478
01:02:47,840 --> 01:02:49,390
找到的长度。

1479
01:02:49,390 --> 01:02:52,680
但由于它的传递
中，我们可以只使用它。

1480
01:02:52,680 --> 01:02:55,720
你刚才假设用户
给你一个有效的尺寸

1481
01:02:55,720 --> 01:02:57,698
实际上代表
一个大小的数组。

1482
01:02:57,698 --> 01:02:59,461

1483
01:02:59,461 --> 01:02:59,960
酷？

1484
01:02:59,960 --> 01:03:01,610

1485
01:03:01,610 --> 01:03:05,870
>> 如果你们有这些任何麻烦
还是要多练编码排序

1486
01:03:05,870 --> 01:03:08,050
在你自己的，你应该
去study.cs50。

1487
01:03:08,050 --> 01:03:11,560

1488
01:03:11,560 --> 01:03:12,670
这是一个工具。

1489
01:03:12,670 --> 01:03:15,040
他们有一个检查器
你其实可以写。

1490
01:03:15,040 --> 01:03:16,180
他们这样做伪。

1491
01:03:16,180 --> 01:03:19,310
他们有更多的视频和幻灯片
包括那些我在这里使用。

1492
01:03:19,310 --> 01:03:23,150
所以，如果你仍然感觉
有点模糊，尝试了这一点。

1493
01:03:23,150 --> 01:03:25,670
与往常一样，来和我说话了。

1494
01:03:25,670 --> 01:03:26,320
问题？

1495
01:03:26,320 --> 01:03:28,611
>> 学生：你说的
大小是预先定义的？

1496
01:03:28,611 --> 01:03:29,234

1497
01:03:29,234 --> 01:03:29,900
指导老师：是的。

1498
01:03:29,900 --> 01:03:35,570
大小是预先定义了
这里的函数声明。

1499
01:03:35,570 --> 01:03:39,060
所以，你认为它已经通过了
由用户，并且为简单起见，

1500
01:03:39,060 --> 01:03:41,896
我们将假设
用户给了我们正确的大小。

1501
01:03:41,896 --> 01:03:43,240
凉爽。

1502
01:03:43,240 --> 01:03:44,390
所以这是选择排序。

1503
01:03:44,390 --> 01:03:45,590

1504
01:03:45,590 --> 01:03:47,640
伙计们，我知道我们今天学习了很多。

1505
01:03:47,640 --> 01:03:49,710
这是一个密集的数据部分。

1506
01:03:49,710 --> 01:03:51,880

1507
01:03:51,880 --> 01:03:57,340
于是就这样，我们将
去插入排序。

1508
01:03:57,340 --> 01:04:01,550

1509
01:04:01,550 --> 01:04:02,510
>> 行。

1510
01:04:02,510 --> 01:04:06,100
所以，在这之前，我们需要做的
我们这里的运行时分析。

1511
01:04:06,100 --> 01:04:10,190
所以，在最好的情况下，
理所当然，因为我给你

1512
01:04:10,190 --> 01:04:11,960
表我已经
种就将它丢弃。

1513
01:04:11,960 --> 01:04:15,430
但是，最好的情况下运行时，我们会怎么想？

1514
01:04:15,430 --> 01:04:17,310

1515
01:04:17,310 --> 01:04:18,130
一切都来分类的。

1516
01:04:18,130 --> 01:04:21,040

1517
01:04:21,040 --> 01:04:22,070
Ñ​​平方。

1518
01:04:22,070 --> 01:04:24,780
任何人都有一个解释
为什么你觉得呢？

1519
01:04:24,780 --> 01:04:29,060

1520
01:04:29,060 --> 01:04:30,519
>> 学生：你比较through--

1521
01:04:30,519 --> 01:04:31,268
指导老师：对。

1522
01:04:31,268 --> 01:04:32,540
你比较过。

1523
01:04:32,540 --> 01:04:35,630
在每一次迭代中，即使
我们正在递减这一个，

1524
01:04:35,630 --> 01:04:38,950
你还在寻找通过
一切都找到了最小的一个。

1525
01:04:38,950 --> 01:04:42,390
所以，即使你的最小值
就是在这里开始，

1526
01:04:42,390 --> 01:04:44,710
你还在比较其
反对一切

1527
01:04:44,710 --> 01:04:46,550
以确保它是最小的事情。

1528
01:04:46,550 --> 01:04:49,820
所以，你最终会通过运行
大约ñ平方倍。

1529
01:04:49,820 --> 01:04:51,090

1530
01:04:51,090 --> 01:04:51,590
行。

1531
01:04:51,590 --> 01:04:52,785
什么是最糟糕的情况？

1532
01:04:52,785 --> 01:04:54,350

1533
01:04:54,350 --> 01:04:57,980
也可为N的平方，因为你会
在做了同样的过程。

1534
01:04:57,980 --> 01:05:01,670
所以在这种情况下，选择
排序有什么

1535
01:05:01,670 --> 01:05:04,010
我们也呼吁预期运行。

1536
01:05:04,010 --> 01:05:07,400
因此，在别人，我们只知道
的上限和下限。

1537
01:05:07,400 --> 01:05:11,180
这取决于如何疯狂我们
列表或者如何排序的是，

1538
01:05:11,180 --> 01:05:15,350
它们n或n的平方之间变化。

1539
01:05:15,350 --> 01:05:16,550
我们不知道。

1540
01:05:16,550 --> 01:05:22,820
>> 但由于选择排序有相同的
最坏和最好的情况下，这告诉我们，

1541
01:05:22,820 --> 01:05:25,880
无论输入什么类型的，我们
有，无论是完全

1542
01:05:25,880 --> 01:05:29,130
排序或完全
反向排序，这是

1543
01:05:29,130 --> 01:05:30,740
要采取的相同的时间量。

1544
01:05:30,740 --> 01:05:33,760
因此，在这种情况下，如果
从表中我们还记得，

1545
01:05:33,760 --> 01:05:38,610
它实际上有一个值，该值
这两类没有，

1546
01:05:38,610 --> 01:05:40,390
这是预期运行。

1547
01:05:40,390 --> 01:05:43,350
所以我们知道，每当
我们运行选择排序，

1548
01:05:43,350 --> 01:05:45,380
它保证
运行一个n的平方时间。

1549
01:05:45,380 --> 01:05:46,630
没有可变性存在。

1550
01:05:46,630 --> 01:05:47,630
这只是预期。

1551
01:05:47,630 --> 01:05:48,820

1552
01:05:48,820 --> 01:05:52,140
并再次，如果你想学习
更多的，拿CS 124的春天。

1553
01:05:52,140 --> 01:05:55,370

1554
01:05:55,370 --> 01:05:56,712
行。

1555
01:05:56,712 --> 01:05:57,545
我们已经看到了这一点。

1556
01:05:57,545 --> 01:05:58,530

1557
01:05:58,530 --> 01:05:59,030
凉爽。

1558
01:05:59,030 --> 01:06:00,930
所以插入排序。

1559
01:06:00,930 --> 01:06:03,330
而且我可能会
走出一条通过此。

1560
01:06:03,330 --> 01:06:05,440
我不会有你们编写它。

1561
01:06:05,440 --> 01:06:06,580
我们将步行穿过它。

1562
01:06:06,580 --> 01:06:10,500
所以插入排序是怎么样
类似于选择排序

1563
01:06:10,500 --> 01:06:14,460
在我们有两个未排序
和排序的阵列的一部分。

1564
01:06:14,460 --> 01:06:20,260
>> 但不同的是，
因为我们通过一个接一个，

1565
01:06:20,260 --> 01:06:24,210
我们只取什么数
接下来是我们未排序的，

1566
01:06:24,210 --> 01:06:28,507
并正确排序
到我们的排序的数组。

1567
01:06:28,507 --> 01:06:30,090
它会更有意义，用一个例子。

1568
01:06:30,090 --> 01:06:31,140

1569
01:06:31,140 --> 01:06:35,430
所以一切开始作为未分类，
只是想用选择排序。

1570
01:06:35,430 --> 01:06:38,740
而我们要在此排序
升序因为我们一直。

1571
01:06:38,740 --> 01:06:40,360

1572
01:06:40,360 --> 01:06:43,340
因此，我们第一遍
我们采取的第一个值

1573
01:06:43,340 --> 01:06:46,700
我们说好，你是
现在在列表中自己。

1574
01:06:46,700 --> 01:06:49,150
>> 因为你是在一个列表
由自己，你的排序。

1575
01:06:49,150 --> 01:06:52,460
恭喜您成为了
此数组第一个元素。

1576
01:06:52,460 --> 01:06:54,800
你已经排序的所有靠自己了。

1577
01:06:54,800 --> 01:06:58,900
所以，现在我们有一个排序
和一个未排序的数组。

1578
01:06:58,900 --> 01:07:01,760
所以，现在我们采取的第一个。

1579
01:07:01,760 --> 01:07:05,600
在此之间会发生什么
这里就是我们说的，

1580
01:07:05,600 --> 01:07:08,890
OK，我们要去看看
我们排序的数组的第一个值

1581
01:07:08,890 --> 01:07:13,270
而且我们要投入在其
正确的位置排序数组中。

1582
01:07:13,270 --> 01:07:21,460
>> 所以，我们要做的是，我们采取5
我们说好，5大于3，

1583
01:07:21,460 --> 01:07:24,630
所以我们只是将它的权利
到的，该权利。

1584
01:07:24,630 --> 01:07:25,130
我们是很好的。

1585
01:07:25,130 --> 01:07:26,200

1586
01:07:26,200 --> 01:07:28,420
那么接下来，我们继续我们的下一个。

1587
01:07:28,420 --> 01:07:29,720
我们采取2。

1588
01:07:29,720 --> 01:07:34,330
我们说好，2少
比3，所以我们知道它

1589
01:07:34,330 --> 01:07:36,220
需要是在
我们的名单前面了。

1590
01:07:36,220 --> 01:07:41,800
所以，我们做的是我们推3和5下
我们提出2成第一个插槽。

1591
01:07:41,800 --> 01:07:42,990

1592
01:07:42,990 --> 01:07:45,870
所以，我们只是将其插入
正确的位置是应该的。

1593
01:07:45,870 --> 01:07:46,960

1594
01:07:46,960 --> 01:07:49,470
>> 然后我们来看看我们的
下一个，我们说6。

1595
01:07:49,470 --> 01:07:53,620
行，6大于
一切都在我们的排序的数组，

1596
01:07:53,620 --> 01:07:56,000
所以我们只是将其标记到结束。

1597
01:07:56,000 --> 01:07:56,960
然后我们来看看4。

1598
01:07:56,960 --> 01:07:58,130

1599
01:07:58,130 --> 01:08:03,020
图4是小于6，就少
比5，但它是大于3。

1600
01:08:03,020 --> 01:08:06,270
所以我们只是把它插入到正确的
3和5之间的中间。

1601
01:08:06,270 --> 01:08:07,380

1602
01:08:07,380 --> 01:08:10,530
因此，为了使这一点
多一点具体的，

1603
01:08:10,530 --> 01:08:12,280
这里是怎么样的
想法发生了什么事。

1604
01:08:12,280 --> 01:08:16,430
因此，对于每一个未排序的元素，我们
确定在排序部分

1605
01:08:16,430 --> 01:08:17,090
它是。

1606
01:08:17,090 --> 01:08:20,680
>> 所以，牢记
分类和未分类，

1607
01:08:20,680 --> 01:08:26,080
我们已经遍历和数字
出它的排序的数组能容纳。

1608
01:08:26,080 --> 01:08:31,460
我们通过移动插入
元素，它的降权。

1609
01:08:31,460 --> 01:08:34,910
然后，我们只是不停
通过迭代，直到我们

1610
01:08:34,910 --> 01:08:39,270
有一个完全排序的列表
其中，无序现在是零

1611
01:08:39,270 --> 01:08:41,720
和排序占用
我们的全部名单。

1612
01:08:41,720 --> 01:08:43,146

1613
01:08:43,146 --> 01:08:45,854
所以，再一次，为了让事情
更具体的，我们有伪代码。

1614
01:08:45,854 --> 01:08:47,979

1615
01:08:47,979 --> 01:08:52,410
>> 所以基本上对我是
等于0到n减1，

1616
01:08:52,410 --> 01:08:54,790
这是我们阵中仅有的长度。

1617
01:08:54,790 --> 01:09:00,979
我们有一些元件，它等于
第一阵列或第一索引。

1618
01:09:00,979 --> 01:09:03,200
我们集合的J相等。

1619
01:09:03,200 --> 01:09:04,649

1620
01:09:04,649 --> 01:09:09,210
因此，虽然j大于
零和阵列，J减去1

1621
01:09:09,210 --> 01:09:11,660
大于
元素，让所有的做

1622
01:09:11,660 --> 01:09:17,479
为确保
您Ĵ真正代表

1623
01:09:17,479 --> 01:09:20,010
阵列的未分类的部分。

1624
01:09:20,010 --> 01:09:30,745
>> 因此，尽管还有事
排序和j减一is--什么

1625
01:09:30,745 --> 01:09:31,840
是她的元素？

1626
01:09:31,840 --> 01:09:34,760
J以从来没有在这里定义。

1627
01:09:34,760 --> 01:09:35,677
这是一种烦人。

1628
01:09:35,677 --> 01:09:36,176
行。

1629
01:09:36,176 --> 01:09:36,689
反正。

1630
01:09:36,689 --> 01:09:39,899
所以Ĵ减1，你检查
之前的元素。

1631
01:09:39,899 --> 01:09:46,460
你说，OK，是元素
之前，无论我am--我们

1632
01:09:46,460 --> 01:09:47,540
实际绘制了这一点。

1633
01:09:47,540 --> 01:09:52,580

1634
01:09:52,580 --> 01:09:56,830
所以我们可以说，这是
就像我们的第二次。

1635
01:09:56,830 --> 01:09:59,525
所以我将是相等
为1，这是在这里。

1636
01:09:59,525 --> 01:10:03,310

1637
01:10:03,310 --> 01:10:06,025
>> 所以我将是等于1。

1638
01:10:06,025 --> 01:10:09,510

1639
01:10:09,510 --> 01:10:13,702
这将是2，4，5，6，7。

1640
01:10:13,702 --> 01:10:16,060

1641
01:10:16,060 --> 01:10:16,750
行。

1642
01:10:16,750 --> 01:10:20,945
因此，我们在这种情况下，元素
将是等于4。

1643
01:10:20,945 --> 01:10:22,110

1644
01:10:22,110 --> 01:10:24,946
我们有一些Ĵ这
将等于1。

1645
01:10:24,946 --> 01:10:29,770

1646
01:10:29,770 --> 01:10:30,971
哦，j被递减。

1647
01:10:30,971 --> 01:10:31,720
那它是什么。

1648
01:10:31,720 --> 01:10:35,680
所以j等于我，所以这个是什么
说的是，我们向前迈进，

1649
01:10:35,680 --> 01:10:37,530
我们只是要确保
我们不是在

1650
01:10:37,530 --> 01:10:43,520
索引这样，当我们试图
插入的东西到我们的排序列表。

1651
01:10:43,520 --> 01:10:49,850
>> 因此，当j等于1在这种情况下，与
阵列Ĵ减埃德蒙顿所以数组Ĵ减1

1652
01:10:49,850 --> 01:10:54,610
2本case--如果这就是
大于所述元件，

1653
01:10:54,610 --> 01:10:57,700
那么这一切是做
被转移下来。

1654
01:10:57,700 --> 01:11:04,790
所以在这种情况下，阵列Ĵ减一
将阵列为零，这是2。

1655
01:11:04,790 --> 01:11:08,430
图2为不大于4，
所以这不会执行。

1656
01:11:08,430 --> 01:11:11,460
这样的移位，并不会向下移动。

1657
01:11:11,460 --> 01:11:18,790
这里做的事情在这里只是
移动你的排序的数组下来。

1658
01:11:18,790 --> 01:11:22,340

1659
01:11:22,340 --> 01:11:26,400
在这种情况下，实际上，我们
可以do--让我们做这3。

1660
01:11:26,400 --> 01:11:28,080

1661
01:11:28,080 --> 01:11:31,970
所以，如果我们穿行与
这个例子，我们现在在这里。

1662
01:11:31,970 --> 01:11:32,740
这是排序。

1663
01:11:32,740 --> 01:11:34,492

1664
01:11:34,492 --> 01:11:35,200
这是未排序的。

1665
01:11:35,200 --> 01:11:39,090

1666
01:11:39,090 --> 01:11:39,860
酷？

1667
01:11:39,860 --> 01:11:46,620
所以i等于2，所以
我们的元素等于3。

1668
01:11:46,620 --> 01:11:47,920

1669
01:11:47,920 --> 01:11:52,270
与我们的j等于2。

1670
01:11:52,270 --> 01:12:00,620
因此，我们期待通过我们
说好，是数组Ĵ减一

1671
01:12:00,620 --> 01:12:03,470
大于所述元件
那我们看什么？

1672
01:12:03,470 --> 01:12:05,540
答案是肯定的，对不对？

1673
01:12:05,540 --> 01:12:11,275
图4是大于3和j
是2，那么该代码执行。

1674
01:12:11,275 --> 01:12:12,510

1675
01:12:12,510 --> 01:12:18,550
>> 所以，现在我们做的一个数组
2，所以在这里，我们交换它们。

1676
01:12:18,550 --> 01:12:25,620
所以，我们只是说，OK，阵列
2，现在将是3。

1677
01:12:25,620 --> 01:12:28,130

1678
01:12:28,130 --> 01:12:32,340
和j是要等于
Ĵ减1，为1。

1679
01:12:32,340 --> 01:12:34,590

1680
01:12:34,590 --> 01:12:37,200
这是可怕的，但
你们的想法。

1681
01:12:37,200 --> 01:12:38,360
J是现在等于1。

1682
01:12:38,360 --> 01:12:44,360
和阵列j的只是要
等于我们的元件，为4。

1683
01:12:44,360 --> 01:12:45,950

1684
01:12:45,950 --> 01:12:48,570
我删除的东西我不应该
有或miswrote东西，

1685
01:12:48,570 --> 01:12:49,910
但是你们的想法。

1686
01:12:49,910 --> 01:12:50,640
>> 它移动以n。

1687
01:12:50,640 --> 01:12:51,920

1688
01:12:51,920 --> 01:12:57,960
然后，如果这是，它会循环
再次，它会说，OK，j是1了。

1689
01:12:57,960 --> 01:13:00,665
和阵列Ĵ减1现在是2。

1690
01:13:00,665 --> 01:13:01,750

1691
01:13:01,750 --> 01:13:03,760
2小于我们的元素？

1692
01:13:03,760 --> 01:13:04,540
不是吗？

1693
01:13:04,540 --> 01:13:07,970
这意味着，我们已经
插入这个元素

1694
01:13:07,970 --> 01:13:10,110
在我们排序的数组中的正确位置。

1695
01:13:10,110 --> 01:13:14,400
然后，我们就可以利用这个和我们说，
OK，我们的排序的数组是在这里。

1696
01:13:14,400 --> 01:13:19,940
它会采取这个数字6，并
就像，OK，比这个数少6？

1697
01:13:19,940 --> 01:13:20,480
不是吗？

1698
01:13:20,480 --> 01:13:21,080
凉爽。

1699
01:13:21,080 --> 01:13:22,680
我们很好。

1700
01:13:22,680 --> 01:13:23,530
>> 再次这样做。

1701
01:13:23,530 --> 01:13:24,740
我们说7。

1702
01:13:24,740 --> 01:13:29,010
比所述端部7少
我们的排序的数组？

1703
01:13:29,010 --> 01:13:29,520
号

1704
01:13:29,520 --> 01:13:30,430
所以，我们很好。

1705
01:13:30,430 --> 01:13:32,760
所以这将被排序。

1706
01:13:32,760 --> 01:13:38,610
基本上，这一切确实
它是在说拿

1707
01:13:38,610 --> 01:13:42,060
的第一个元素
您排序的数组，

1708
01:13:42,060 --> 01:13:46,010
找出通向哪里
在排序的数组。

1709
01:13:46,010 --> 01:13:48,780
而这只是照顾
掉期来做到这一点。

1710
01:13:48,780 --> 01:13:51,300
你基本上只是交换
直到它在正确的位置。

1711
01:13:51,300 --> 01:13:53,600

1712
01:13:53,600 --> 01:13:56,990
视觉形象是你
移动都记录下来做的。

1713
01:13:56,990 --> 01:13:59,420
>> 所以，这就像半冒泡排序式的。

1714
01:13:59,420 --> 01:14:02,280

1715
01:14:02,280 --> 01:14:03,420
退房研究50。

1716
01:14:03,420 --> 01:14:06,000
我强烈建议尝试
编写这个你自己。

1717
01:14:06,000 --> 01:14:07,220

1718
01:14:07,220 --> 01:14:12,450
如果您有任何问题，或者您想
参见示例代码插入排序，

1719
01:14:12,450 --> 01:14:13,750
请告诉我。

1720
01:14:13,750 --> 01:14:14,500
我总是四处。

1721
01:14:14,500 --> 01:14:16,600

1722
01:14:16,600 --> 01:14:20,200
因此，最坏的情况下运行
和最好的情况下运行。

1723
01:14:20,200 --> 01:14:30,700
当你的家伙从表中看到，我已经
表现出你，这既是ñ平方和n。

1724
01:14:30,700 --> 01:14:35,590
>> 种这么打算过什么，我们聊
关于我们以前的种种，最糟糕的

1725
01:14:35,590 --> 01:14:38,760
情况下运行时，如果
它是完全不排序，

1726
01:14:38,760 --> 01:14:42,530
我们必须比较所有这些n次。

1727
01:14:42,530 --> 01:14:47,020
我们做了一大堆的比较
因为如果它以相反的顺序，

1728
01:14:47,020 --> 01:14:50,360
我们会说，OK，这
是相同的，这是很好的，

1729
01:14:50,360 --> 01:14:54,650
而这一次将要被比较
相对于第一个要被移动回。

1730
01:14:54,650 --> 01:14:56,710
而且随着我们走向
尾部，我们有

1731
01:14:56,710 --> 01:14:59,440
比较，比较和
与之比较的一切。

1732
01:14:59,440 --> 01:15:03,030
>> 因此它最终被
大约Ñ平方。

1733
01:15:03,030 --> 01:15:09,510
如果它是正确的，那么你
说好，2，你是​​好。

1734
01:15:09,510 --> 01:15:11,330
3，你比2。

1735
01:15:11,330 --> 01:15:12,310
你很厉害。

1736
01:15:12,310 --> 01:15:14,150
4，你只是比较的尾巴。

1737
01:15:14,150 --> 01:15:14,990
你很厉害。

1738
01:15:14,990 --> 01:15:17,140
6，比较的尾巴，你的罚款。

1739
01:15:17,140 --> 01:15:20,870
因此，对于每一个点，如果它已经
排序，你正在做一次比较。

1740
01:15:20,870 --> 01:15:22,320
所以它只是ñ。

1741
01:15:22,320 --> 01:15:26,840
因为我们有最好的情况下运行
n及n的最坏情况的运行时的

1742
01:15:26,840 --> 01:15:28,680
方，我们也没有预期的运行。

1743
01:15:28,680 --> 01:15:31,290

1744
01:15:31,290 --> 01:15:34,020
>> 这只是取决于
乱我们的名单中出现。

1745
01:15:34,020 --> 01:15:35,860

1746
01:15:35,860 --> 01:15:39,530
又一次，另一
图形和另一个表。

1747
01:15:39,530 --> 01:15:41,170
所以各种各样的差异。

1748
01:15:41,170 --> 01:15:44,180
我只是微风过，我
感觉我们已经谈过了广泛

1749
01:15:44,180 --> 01:15:46,570
有关他们都怎么样
的变化，并且连接到一起。

1750
01:15:46,570 --> 01:15:50,564
所以合并排序是最后一个
我要你承担家伙。

1751
01:15:50,564 --> 01:15:52,105
我们也有一个漂亮的多彩画卷。

1752
01:15:52,105 --> 01:15:53,860

1753
01:15:53,860 --> 01:15:56,040
所以，归并排序是递归算法。

1754
01:15:56,040 --> 01:15:59,910
所以，不要你们知道是什么
递归函数是？

1755
01:15:59,910 --> 01:16:01,550

1756
01:16:01,550 --> 01:16:03,320
>> 任何想说的？

1757
01:16:03,320 --> 01:16:04,739
你想试试吗？

1758
01:16:04,739 --> 01:16:07,280
因此，一个递归函数就是
一个函数调用自身。

1759
01:16:07,280 --> 01:16:08,570

1760
01:16:08,570 --> 01:16:11,590
所以，如果你们熟悉
与斐波那契序列，

1761
01:16:11,590 --> 01:16:15,670
该公司认为，因为递归
你把前面的两个

1762
01:16:15,670 --> 01:16:17,530
并把它们相加
让你的下一个。

1763
01:16:17,530 --> 01:16:21,440
这样循环，我一直认为
递归如像一个螺旋形的

1764
01:16:21,440 --> 01:16:24,430
所以你像螺旋式下降了进去。

1765
01:16:24,430 --> 01:16:27,150
但它只是一个功能
调用自身。

1766
01:16:27,150 --> 01:16:32,660
>> 而且，实际上，真的很快我
可以告诉你那是什么样子。

1767
01:16:32,660 --> 01:16:34,260

1768
01:16:34,260 --> 01:16:41,840
所以递归这里，如果我们看，这是
递归的方式来总结一个数组。

1769
01:16:41,840 --> 01:16:45,900

1770
01:16:45,900 --> 01:16:47,880
因此，所有我们要做的就是
我们有求和函数

1771
01:16:47,880 --> 01:16:52,210
总之，需要一个大小和数组。

1772
01:16:52,210 --> 01:16:55,210
如果你注意到，大小
减一各一次。

1773
01:16:55,210 --> 01:17:00,365
和所有它的作用是，如果x等于
zero--因此，如果该数组的大小

1774
01:17:00,365 --> 01:17:02,710
等于zero--返回零。

1775
01:17:02,710 --> 01:17:10,440
>> 否则，这个总结
所述阵列的最后一个元素，

1776
01:17:10,440 --> 01:17:14,790
然后采取的总和
该阵列的其余部分。

1777
01:17:14,790 --> 01:17:17,555
所以它只是将它分解
成越来越小的问题。

1778
01:17:17,555 --> 01:17:18,990

1779
01:17:18,990 --> 01:17:21,890
长话短说，递归，
函数调用自身。

1780
01:17:21,890 --> 01:17:25,740
如果这是你离开了这一点，
这就是一个递归函数。

1781
01:17:25,740 --> 01:17:29,870
如果你51，你会得到非常，
很舒服的递归。

1782
01:17:29,870 --> 01:17:31,110

1783
01:17:31,110 --> 01:17:32,370
这真的很酷。

1784
01:17:32,370 --> 01:17:34,660
它以有意义像
上午03点一晚了。

1785
01:17:34,660 --> 01:17:37,900
我当时想，为什么
我也从来没有用这个？

1786
01:17:37,900 --> 01:17:39,170

1787
01:17:39,170 --> 01:17:42,430
>> 因此，对于归并排序，基本上
什么是要做的是它的

1788
01:17:42,430 --> 01:17:45,620
要打破它，打破它
直到它只是单一的元素。

1789
01:17:45,620 --> 01:17:47,570
单个元件很容易就可以进行排序。

1790
01:17:47,570 --> 01:17:48,070
我们看到这一点。

1791
01:17:48,070 --> 01:17:50,760
如果你有一个元素，它的
已经考虑排序。

1792
01:17:50,760 --> 01:17:53,800
等n个元素的一个输入端，
如果n小于2，

1793
01:17:53,800 --> 01:17:58,120
刚回来，因为那意味着
它是0或1，因为我们已经看到了。

1794
01:17:58,120 --> 01:18:00,050
那些被认为是排序的元素。

1795
01:18:00,050 --> 01:18:02,170
>> 否则，打破它的一半。

1796
01:18:02,170 --> 01:18:06,336
排序上半年，排序第二
一半，然后将它们合并在一起。

1797
01:18:06,336 --> 01:18:07,460
为什么它被称为归并排序。

1798
01:18:07,460 --> 01:18:08,700

1799
01:18:08,700 --> 01:18:12,155
所以，我们在这里，我们将整理这些。

1800
01:18:12,155 --> 01:18:13,410

1801
01:18:13,410 --> 01:18:17,210
因此，我们继续让他们
直到数组大小为1。

1802
01:18:17,210 --> 01:18:20,790
所以，当它的1，我们只返回
因为这是一个排序后的数组，

1803
01:18:20,790 --> 01:18:23,940
这是一个排序的数组，而这
一个排序的数组，我们都来分类的。

1804
01:18:23,940 --> 01:18:25,390

1805
01:18:25,390 --> 01:18:29,420
那么接下来我们要做的是我们
启动它们合并在一起。

1806
01:18:29,420 --> 01:18:31,820
>> 所以，这样就可以
想想合并是

1807
01:18:31,820 --> 01:18:36,240
你只是删除小
各子阵列中的数

1808
01:18:36,240 --> 01:18:38,330
而只是将其追加到数组中出现。

1809
01:18:38,330 --> 01:18:44,290
所以，如果你看看这里，当我们有
这些集我们有4,6和1。

1810
01:18:44,290 --> 01:18:47,280
当我们要合并这些，
我们看一下前两个

1811
01:18:47,280 --> 01:18:50,730
我们说好，1越小，
它会向前方。

1812
01:18:50,730 --> 01:18:54,330
4和6，有没有什么比较
它，只是将其标记上到结束。

1813
01:18:54,330 --> 01:18:58,020
>> 当我们结合这两个，我们只是
取这两个中较小的一个，

1814
01:18:58,020 --> 01:18:59,310
所以它的1。

1815
01:18:59,310 --> 01:19:01,690
现在我们采取的
这两个，所以2的小。

1816
01:19:01,690 --> 01:19:03,330
这两个，3个较小的。

1817
01:19:03,330 --> 01:19:06,260
这两个，4，5，6以下。

1818
01:19:06,260 --> 01:19:08,630
所以，你刚才拉过这些。

1819
01:19:08,630 --> 01:19:11,210
而且由于他们把
以前被排序，

1820
01:19:11,210 --> 01:19:14,300
你只有一个
比较有各一次。

1821
01:19:14,300 --> 01:19:19,610
因此，更多的代码在这里，只是表示。

1822
01:19:19,610 --> 01:19:24,410
所以你在开始，中间和
您排序左右

1823
01:19:24,410 --> 01:19:26,180
然后你只要这些合并。

1824
01:19:26,180 --> 01:19:30,080
>> 我们没有代码
对于合并就在这里。

1825
01:19:30,080 --> 01:19:34,110
但是，再说一次，如果你去上
研究50，它会在那里。

1826
01:19:34,110 --> 01:19:36,860
否则，来跟我说话
如果你还在迷茫。

1827
01:19:36,860 --> 01:19:42,340
因此，这里很酷的事情是最好的情况下，
最坏的情况下，与预期的运行时

1828
01:19:42,340 --> 01:19:46,250
都在日志中N，其中
远不如我们已经

1829
01:19:46,250 --> 01:19:48,000
看到了我们各种各样的休息。

1830
01:19:48,000 --> 01:19:51,840
我们已经看到ñ平方
而其实我们

1831
01:19:51,840 --> 01:19:54,380
拿到这里的n log N，这是伟大的。

1832
01:19:54,380 --> 01:19:55,830
>> 看看这是多么要好的多。

1833
01:19:55,830 --> 01:19:56,780
这样一个漂亮的曲线。

1834
01:19:56,780 --> 01:19:58,130

1835
01:19:58,130 --> 01:20:00,120
因此，更有效。

1836
01:20:00,120 --> 01:20:03,510
如果你可以，使用归并排序。

1837
01:20:03,510 --> 01:20:04,810
这将节省您的时间。

1838
01:20:04,810 --> 01:20:07,670
话又说回来，正如我们所说的，如果
你倒在这个较低的地区，

1839
01:20:07,670 --> 01:20:09,480
它不会作出这样的
多大的差别。

1840
01:20:09,480 --> 01:20:11,360
你得到多达数千
和数以千计的投入，

1841
01:20:11,360 --> 01:20:13,318
你一定要一个
更有效的算法。

1842
01:20:13,318 --> 01:20:14,730

1843
01:20:14,730 --> 01:20:19,400
并再次，我们可爱的表
各种各样，你们今天学到。

1844
01:20:19,400 --> 01:20:21,157
>> 所以，我知道这是一个密集的一天。

1845
01:20:21,157 --> 01:20:23,490
这不一定要去
帮助您与您的PSET。

1846
01:20:23,490 --> 01:20:28,250
但我只想做一个免责声明
该节不只是pset中。

1847
01:20:28,250 --> 01:20:31,240
所有这些材料是公平的
游戏中为你的期中考试。

1848
01:20:31,240 --> 01:20:35,430
而且如果你继续用CS，
这些都是非常重要的基础

1849
01:20:35,430 --> 01:20:37,870
你需要知道的。

1850
01:20:37,870 --> 01:20:41,700
所以，有些日子将是一个
多一点PSET的帮助，

1851
01:20:41,700 --> 01:20:44,600
但几个星期会
更多的实际内容

1852
01:20:44,600 --> 01:20:46,600
这似乎并不超
现在对你有用，

1853
01:20:46,600 --> 01:20:51,215
但如果你继续我答应
上会非常，非常有用。

1854
01:20:51,215 --> 01:20:52,560

1855
01:20:52,560 --> 01:20:54,250
>> 所以这是它的一节。

1856
01:20:54,250 --> 01:20:55,250
下来的电线。

1857
01:20:55,250 --> 01:20:56,570
我做了一分钟之内。

1858
01:20:56,570 --> 01:20:58,262

1859
01:20:58,262 --> 01:20:58,970
但你去那里。

1860
01:20:58,970 --> 01:21:01,240
我也有甜甜圈或糖果。

1861
01:21:01,240 --> 01:21:03,464
有没有人过敏
任何事情，顺便？

1862
01:21:03,464 --> 01:21:05,307

1863
01:21:05,307 --> 01:21:05,890
鸡蛋和牛奶。

1864
01:21:05,890 --> 01:21:08,120
因此，甜甜圈是一个没有？

1865
01:21:08,120 --> 01:21:09,400

1866
01:21:09,400 --> 01:21:10,160
行。

1867
01:21:10,160 --> 01:21:10,770
行。

1868
01:21:10,770 --> 01:21:12,120
巧克力不？

1869
01:21:12,120 --> 01:21:12,620
星爆。

1870
01:21:12,620 --> 01:21:13,837

1871
01:21:13,837 --> 01:21:14,670
星形图案都不错。

1872
01:21:14,670 --> 01:21:15,170
行。

1873
01:21:15,170 --> 01:21:17,045
我们将有
下周爆吧。

1874
01:21:17,045 --> 01:21:18,240
这就是我去拿。

1875
01:21:18,240 --> 01:21:19,690
你们有一个伟大的一周。

1876
01:21:19,690 --> 01:21:20,460
看了你的天赋。

1877
01:21:20,460 --> 01:21:22,130
>> 让我知道，如果你有任何问题。

1878
01:21:22,130 --> 01:21:25,300
PSET两个档次应该是
出来给你周四。

1879
01:21:25,300 --> 01:21:28,320
如果您有任何问题
我是如何分级的事情

1880
01:21:28,320 --> 01:21:32,250
为什么我的东西渐变的方式，我
没有，请给我发电子邮件，来和我说话。

1881
01:21:32,250 --> 01:21:34,210
我有点疯了这
一周，但我保证

1882
01:21:34,210 --> 01:21:36,340
我仍然会在24小时内回复。

1883
01:21:36,340 --> 01:21:38,240
所以，有一个伟大的一周，每一个人。

1884
01:21:38,240 --> 01:21:40,090
祝你PSET。

1885
01:21:40,090 --> 01:21:41,248