1
00:00:00,000 --> 00:00:03,332
>> [音乐播放]

2
00:00:03,332 --> 00:00:06,490
>> ANDI鹏：欢迎来到第3个星期

3
00:00:06,490 --> 00:00:09,550
谢谢你们，所有的未来
到今天这个较早的开始时间。

4
00:00:09,550 --> 00:00:11,466
我们已经有了一个很好的，小
今天的亲密组。

5
00:00:11,466 --> 00:00:14,570
所以希望我们会得到
说完，或许，早，

6
00:00:14,570 --> 00:00:15,780
一点点今天一早。

7
00:00:15,780 --> 00:00:22,057
那么快，只是一些
今天议程公告。

8
00:00:22,057 --> 00:00:23,890
在我们开始之前，我们
要只走了过来

9
00:00:23,890 --> 00:00:28,910
一些简单的后勤问题，PSET
题，汇报，这样的事情。

10
00:00:28,910 --> 00:00:30,250
然后，我们将深入权利英寸

11
00:00:30,250 --> 00:00:34,710
我们将使用一个名为GDB来调试程序
启动揭穿我们的代码，大卫

12
00:00:34,710 --> 00:00:36,550
有一天在课堂解释。

13
00:00:36,550 --> 00:00:39,420
我们就去了四种类型的排序。

14
00:00:39,420 --> 00:00:42,310
我们会去超过他们很快
因为他们非常密集。

15
00:00:42,310 --> 00:00:45,710
但是要知道，所有的幻灯片和
源代码是永远在线。

16
00:00:45,710 --> 00:00:50,810
所以感到自由，在你细读，以
回去看看那个。

17
00:00:50,810 --> 00:00:53,930
>> 我们将通过
渐近符号，这

18
00:00:53,930 --> 00:00:55,944
仅仅是一个奇特的方式
说“运行时间”

19
00:00:55,944 --> 00:00:58,360
在这里，我们有大O，从而
大卫在演讲解释。

20
00:00:58,360 --> 00:01:01,550
而且我们也有欧米茄，这
是下界运行时。

21
00:01:01,550 --> 00:01:06,450
我们将讨论多一点
深入的关于如何将这些工作。

22
00:01:06,450 --> 00:01:10,160
最后，我们就去了二进制搜索，
因为很多你谁已经

23
00:01:10,160 --> 00:01:15,190
看了一眼你的pset便知
这是一个问题，在你的pset中。

24
00:01:15,190 --> 00:01:17,470
所以，你都会很高兴
我们管这个今天。

25
00:01:17,470 --> 00:01:20,610
>> 最后，根据您的
部分反馈意见，其实我

26
00:01:20,610 --> 00:01:23,000
在离开约15分钟
年底刚刚走了过来

27
00:01:23,000 --> 00:01:27,730
pset3物流，如有问题，
也许有点指导，如果你愿意，

28
00:01:27,730 --> 00:01:28,990
我们开始编程了。

29
00:01:28,990 --> 00:01:30,890
因此，让我们试着打通
该材料很快。

30
00:01:30,890 --> 00:01:33,880
然后我们就可以花一些时间
同时为处理器集更多的问题。

31
00:01:33,880 --> 00:01:35,230
好。

32
00:01:35,230 --> 00:01:39,570
>> 很快，所以只是少数
我们之前宣布从今天开始。

33
00:01:39,570 --> 00:01:45,410
首先，欢迎来制作
它通过两个你的pset中。

34
00:01:45,410 --> 00:01:49,432
我看了看your--是啊，让我们
获得掌声的那一个。

35
00:01:49,432 --> 00:01:51,140
其实，我是真的，
真的很感动。

36
00:01:51,140 --> 00:01:55,800
我分级的第一个PSET为你们
上周，你们做了令人难以置信的。

37
00:01:55,800 --> 00:01:58,290
>> 风格是在点
除了一些意见。

38
00:01:58,290 --> 00:02:00,660
请确保你总是
注释你的代码。

39
00:02:00,660 --> 00:02:03,040
但是，你的pset中都点上。

40
00:02:03,040 --> 00:02:05,549
并保持了起来。

41
00:02:05,549 --> 00:02:08,090
而且它的良好的平地机到
看到你们是把

42
00:02:08,090 --> 00:02:10,704
在你的风格尽可能多的努力
和你在你的代码设计

43
00:02:10,704 --> 00:02:12,120
我们想给你看。

44
00:02:12,120 --> 00:02:16,450
所以我路过沿着我的谢意
为助教的其余部分。

45
00:02:16,450 --> 00:02:19,210
>> 然而，有一个
一些汇报的问题

46
00:02:19,210 --> 00:02:22,010
我只是想说明一下
可使两个我的生活

47
00:02:22,010 --> 00:02:24,900
和许多其它的
助教的生活更容易一点。

48
00:02:24,900 --> 00:02:28,220
首先，我注意到这个
过去week--你们有多少人

49
00:02:28,220 --> 00:02:32,301
已经运行check50
在你的代码提交？

50
00:02:32,301 --> 00:02:32,800
好。

51
00:02:32,800 --> 00:02:36,690
所以每个人都应该做的check50，
因为 - 一个secret--我们实际上

52
00:02:36,690 --> 00:02:41,540
运行check50作为我们的正确性的一部分
脚本测试代码。

53
00:02:41,540 --> 00:02:45,480
所以，如果你的代码是失败的
check50，在所有的可能性，

54
00:02:45,480 --> 00:02:47,570
它可能会
失败我们检查为好。

55
00:02:47,570 --> 00:02:49,320
有时候你们
有正确的答案。

56
00:02:49,320 --> 00:02:52,200
像，在贪婪的，一些
你有正确的号码，

57
00:02:52,200 --> 00:02:53,960
你只需打印出一些额外的东西。

58
00:02:53,960 --> 00:02:55,940
而这额外的东西
实际上未通过检查，

59
00:02:55,940 --> 00:02:58,440
因为电脑不
真的知道它在寻找。

60
00:02:58,440 --> 00:03:00,981
因此，这将只运行通过，
看到你的输出不

61
00:03:00,981 --> 00:03:03,810
符合我们所期待的答​​案
要，并注明这是错误的。

62
00:03:03,810 --> 00:03:06,560
>> 我知道，发生在
你的一些情况下，这个星期。

63
00:03:06,560 --> 00:03:09,870
所以，我回去和手动
regraded每个人的代码。

64
00:03:09,870 --> 00:03:12,780
在未来虽然，
请，请确保

65
00:03:12,780 --> 00:03:14,570
你正在运行
在你的代码检查50。

66
00:03:14,570 --> 00:03:17,970
因为它是一种为TA疼痛
不得不回去手动再分类

67
00:03:17,970 --> 00:03:21,197
每一个每一个PSET
单，很少错过实例。

68
00:03:21,197 --> 00:03:22,530
所以，我没有脱任何积分。

69
00:03:22,530 --> 00:03:25,210
我想，我脱下也许
的一个或两个用于设计。

70
00:03:25,210 --> 00:03:27,710
在未来虽然，如果
你失败check50，

71
00:03:27,710 --> 00:03:31,330
点将会采取
关闭正确性。

72
00:03:31,330 --> 00:03:35,020
>> 此外，pset中是
由于周五中午。

73
00:03:35,020 --> 00:03:38,990
我觉得有一个7分钟
我们给你迟到宽限期。

74
00:03:38,990 --> 00:03:42,434
每哈佛的时候，他们获准
为7分钟迟到的一切。

75
00:03:42,434 --> 00:03:44,350
因此，这里在耶鲁，我们将
坚持这一点。

76
00:03:44,350 --> 00:03:47,910
但相当多，在12:07，
如果你的PSET不在，

77
00:03:47,910 --> 00:03:49,720
这将是为后期标记。

78
00:03:49,720 --> 00:03:53,160
因此，虽然它被标记为
为末，TA--我

79
00:03:53,160 --> 00:03:54,870
还是会被分级您的pset。

80
00:03:54,870 --> 00:03:56,760
所以，你仍然会看到一个档次的出现。

81
00:03:56,760 --> 00:03:58,820
但是，要知道，在
学期结束时，

82
00:03:58,820 --> 00:04:02,270
所有后期的pset将只是
由计算机自动归零。

83
00:04:02,270 --> 00:04:04,490
>> 我们这样做有两个原因。

84
00:04:04,490 --> 00:04:09,220
其中，有时我们得到
原谅，就像院长的借口，

85
00:04:09,220 --> 00:04:10,762
后来，我不知道呢。

86
00:04:10,762 --> 00:04:13,761
因此，我们希望确保我们分级
一切都为了以防万一，比如，我

87
00:04:13,761 --> 00:04:15,080
缺少院长的借口。

88
00:04:15,080 --> 00:04:17,000
其次，要
心中，你仍然可以

89
00:04:17,000 --> 00:04:19,370
摔个PSET的
有完整的范围点。

90
00:04:19,370 --> 00:04:21,430
因此，我们要分级
所有的pset只是

91
00:04:21,430 --> 00:04:24,730
以确保您的范围的
那里，你想他们。

92
00:04:24,730 --> 00:04:29,150
因此，即使是晚了，你还是会
获得信贷的范围点，我想。

93
00:04:29,150 --> 00:04:33,730
>> 因此，道德的故事，使
确保你的pset是导通时间。

94
00:04:33,730 --> 00:04:38,350
并且如果它们不是在导通时间，
知道这是不是很大。

95
00:04:38,350 --> 00:04:41,678
是啊，在我继续前进，没有任何人有
有关PSET反馈有任何疑问？

96
00:04:41,678 --> 00:04:42,178
是啊。

97
00:04:42,178 --> 00:04:43,630
>> 听众：你是说，我​​们
可以去掉的pset之一？

98
00:04:43,630 --> 00:04:44,296
>> ANDI彭：是的。

99
00:04:44,296 --> 00:04:47,050
因此，有九pset中整体
在这学期的课程。

100
00:04:47,050 --> 00:04:50,610
如果你有范围
points--因此范围是正义的，

101
00:04:50,610 --> 00:04:53,567
相当多，你尝试了
问题是，你投入的时间，

102
00:04:53,567 --> 00:04:56,150
你表明你已经
表明您已经阅读了规范。

103
00:04:56,150 --> 00:04:57,191
这是相当多的范围。

104
00:04:57,191 --> 00:04:59,370
如果你正在履行
范围点，我们

105
00:04:59,370 --> 00:05:03,360
可以降最低
一出的全部范围。

106
00:05:03,360 --> 00:05:06,790
所以这是你的优势，
完成并想尽一切PSET。

107
00:05:06,790 --> 00:05:10,320
>> 即使upload--如果没有
他们的工作，快点上传所有。

108
00:05:10,320 --> 00:05:13,711
然后我们就希望能够
给你一些这些点回来。

109
00:05:13,711 --> 00:05:14,210
酷。

110
00:05:14,210 --> 00:05:16,780
其他问题吗？

111
00:05:16,780 --> 00:05:17,840
太好了。

112
00:05:17,840 --> 00:05:21,960
>> 其次，办公hours--数
有关办公时间快速笔记。

113
00:05:21,960 --> 00:05:24,300
因此，首先，走在了本周初。

114
00:05:24,300 --> 00:05:26,909
没有人是曾经在
办公时间周一休息。

115
00:05:26,909 --> 00:05:28,700
Christabel来到
昨晚办公时间。

116
00:05:28,700 --> 00:05:29,691
是啊，Christabel。

117
00:05:29,691 --> 00:05:32,190
和我们有在办公室什么
小时昨晚，Christabel？

118
00:05:32,190 --> 00:05:33,020
>> 听众：我们有冰淇淋。

119
00:05:33,020 --> 00:05:36,160
>> ANDI彭：所以这是正确的，我们有
冰淇淋办公时间昨晚。

120
00:05:36,160 --> 00:05:39,390
虽然我不能答应你，
我们将有冰淇淋办公时间

121
00:05:39,390 --> 00:05:43,230
每个星期，我可以向你保证
的是，将有显著

122
00:05:43,230 --> 00:05:45,380
更好的学生到TA的比例。

123
00:05:45,380 --> 00:05:47,650
像合法的，它像三一。

124
00:05:47,650 --> 00:05:50,350
然而，对比，与
周四，你已经得到了约150

125
00:05:50,350 --> 00:05:52,830
真正强调的孩子和没有冰淇淋。

126
00:05:52,830 --> 00:05:55,360
而且它只是没有生产任何人。

127
00:05:55,360 --> 00:05:58,730
所以这个故事的寓意是，来得早
在办公时间，办好事

128
00:05:58,730 --> 00:06:00,310
会发生。

129
00:06:00,310 --> 00:06:02,110
>> 此外，有备而来提问。

130
00:06:02,110 --> 00:06:03,200
你懂的？

131
00:06:03,200 --> 00:06:05,420
不管什么助教，我
想，一直在说，

132
00:06:05,420 --> 00:06:10,710
我们已经获得一对学生情侣
谁在周四进来的一样，10:50

133
00:06:10,710 --> 00:06:15,100
不看了规范
是一样帮助我，帮助我。

134
00:06:15,100 --> 00:06:18,200
不幸的是，在这一点上，还有
没有多少，我们可以做些什么来帮助你。

135
00:06:18,200 --> 00:06:19,590
所以，请进来本周初。

136
00:06:19,590 --> 00:06:22,040
来得早在办公时间。

137
00:06:22,040 --> 00:06:23,350
有备而来的提问。

138
00:06:23,350 --> 00:06:25,310
请确保您作为
一个学生，都在那里

139
00:06:25,310 --> 00:06:27,620
你必须使得
助教可以引导你前进，

140
00:06:27,620 --> 00:06:32,850
这正是办公时间
应分配的。

141
00:06:32,850 --> 00:06:37,380
>> 其次，所以我知道教授
喜欢我们测试的惊喜。

142
00:06:37,380 --> 00:06:39,439
我有一个教授的
像哟，顺便说一下，

143
00:06:39,439 --> 00:06:41,230
请记住，中期
你下周一。

144
00:06:41,230 --> 00:06:42,855
是啊，我不知道是中期。

145
00:06:42,855 --> 00:06:45,630
所以我将是那个TA
提醒大家，测验

146
00:06:45,630 --> 00:06:47,270
0--因为，你知道，我们是CS。

147
00:06:47,270 --> 00:06:50,730
现在，我们已经做了数组，你会得到
为什么它的测验0，没有测验1，是吗？

148
00:06:50,730 --> 00:06:51,320
好。

149
00:06:51,320 --> 00:06:52,490
呵呵，我得到了一个有些笑。

150
00:06:52,490 --> 00:06:53,120
好。

151
00:06:53,120 --> 00:06:59,710
>> 因此，测验0将是10月14日，如果
你在周一至周三节

152
00:06:59,710 --> 00:07:02,920
而10月15日，如果你在
周二至周四部分。

153
00:07:02,920 --> 00:07:05,630
这不适用于
那些你在哈佛

154
00:07:05,630 --> 00:07:10,350
who--我想你会都是
以14号的测验。

155
00:07:10,350 --> 00:07:13,560
>> 所以呀，在下周，如果
大卫在演讲中，云，

156
00:07:13,560 --> 00:07:15,747
是啊，所以有关
竞猜下周，大家

157
00:07:15,747 --> 00:07:17,580
将不会因为震惊
您来第

158
00:07:17,580 --> 00:07:19,664
你知道你的
测验0是在两个星期。

159
00:07:19,664 --> 00:07:21,580
而且我们必须检讨
会议和一切。

160
00:07:21,580 --> 00:07:26,360
所以不愁
被吓到了点。

161
00:07:26,360 --> 00:07:29,890
如有任何疑问before--任何疑问
在所有有关的后勤问题，

162
00:07:29,890 --> 00:07:32,591
分级，办公时间，部分？

163
00:07:32,591 --> 00:07:33,090
是啊。

164
00:07:33,090 --> 00:07:35,100
>> 听众：所以小测验
将要演讲期间？

165
00:07:35,100 --> 00:07:35,766
>> ANDI彭：是的。

166
00:07:35,766 --> 00:07:39,460
所以测验，我想，是60
分配在时隙分钟

167
00:07:39,460 --> 00:07:42,240
你会只拿
在报告厅。

168
00:07:42,240 --> 00:07:44,810
所以，你不必进来
上一样，随机下午7:00。

169
00:07:44,810 --> 00:07:46,140
都很好。

170
00:07:46,140 --> 00:07:47,100
是啊。

171
00:07:47,100 --> 00:07:50,060
酷。

172
00:07:50,060 --> 00:07:50,840
>> 好吧。

173
00:07:50,840 --> 00:07:54,330
所以，我们要
介绍一个概念，你

174
00:07:54,330 --> 00:08:00,760
本周大卫早已种
这个过去一周触及的讲座。

175
00:08:00,760 --> 00:08:02,010
这就是所谓的GDB。

176
00:08:02,010 --> 00:08:05,570
你们有多少人而且，当
写你的pset的过程中，

177
00:08:05,570 --> 00:08:09,981
已经注意到一个很大的按钮，上面写着
在您的IDE顶部的“调试”？

178
00:08:09,981 --> 00:08:10,480
好。

179
00:08:10,480 --> 00:08:13,770
所以，现在，我们将真正得到挖掘
其实什么按钮的奥秘

180
00:08:13,770 --> 00:08:14,270
确实。

181
00:08:14,270 --> 00:08:16,790
我向你保证，这是一个
美丽的，美丽的东西。

182
00:08:16,790 --> 00:08:20,740
>> 所以到现在为止，我觉得
还有的是两件事情

183
00:08:20,740 --> 00:08:23,320
学生已通常
调试的pset在做。

184
00:08:23,320 --> 00:08:27,635
一，他们要么加入
printf（）的 - 所以每几行字，

185
00:08:27,635 --> 00:08:29,760
他们加入一个printf（） - 
哦，这是什么变量？

186
00:08:29,760 --> 00:08:32,551
哦，这是什么变量now--
样的，你会看到进展

187
00:08:32,551 --> 00:08:33,940
你的代码，因为它运行。

188
00:08:33,940 --> 00:08:37,030
或者第二种方法孩子们做的是
他们只写了整个事情

189
00:08:37,030 --> 00:08:38,610
然后转到这样在末端。

190
00:08:38,610 --> 00:08:39,970
希望它的工作原理。

191
00:08:39,970 --> 00:08:44,851
我向你保证，GDB更好
比两者的那些方法。

192
00:08:44,851 --> 00:08:45,350
是啊。

193
00:08:45,350 --> 00:08:46,980
因此，这将是你最好的朋友。

194
00:08:46,980 --> 00:08:51,780
因为它是一个美丽的东西
在视觉上同时显示

195
00:08:51,780 --> 00:08:54,850
你的代码做
在特定点

196
00:08:54,850 --> 00:08:57,486
以及所有的你的
变量都在进行，

197
00:08:57,486 --> 00:08:59,610
喜欢什么他们的价值观，
在该特定的点。

198
00:08:59,610 --> 00:09:02,670
而这样一来，你才能真正
设置在代码中的断点。

199
00:09:02,670 --> 00:09:04,350
您可以通过一行一行地运行。

200
00:09:04,350 --> 00:09:07,324
和GDB只会有
您，向您显示，

201
00:09:07,324 --> 00:09:09,490
什么你所有的变量
是，他们在做什么，

202
00:09:09,490 --> 00:09:10,656
这是怎么回事代码。

203
00:09:10,656 --> 00:09:13,240
并且在这样的方式，它的
所以更容易看到

204
00:09:13,240 --> 00:09:17,120
发生了什么的printf的-ING代替
或写下你的陈述。

205
00:09:17,120 --> 00:09:19,160
>> 所以我们会做后面的一个例子。

206
00:09:19,160 --> 00:09:20,660
因此，这似乎有点抽象。

207
00:09:20,660 --> 00:09:23,490
不用担心，我们会做的例子。

208
00:09:23,490 --> 00:09:29,170
所以本质上，三个最大的，
最常用的功能，你需要在GDB

209
00:09:29,170 --> 00:09:32,500
是接下来，步过，
而步入按钮。

210
00:09:32,500 --> 00:09:34,860
我将头以上
在那里，其实，就是现在。

211
00:09:34,860 --> 00:09:40,930
>> 所以你们可以都看到，
或者我应该放大一点？

212
00:09:40,930 --> 00:09:43,220

213
00:09:43,220 --> 00:09:44,470
在后面，你能看到吗？

214
00:09:44,470 --> 00:09:45,730
我应该放大？

215
00:09:45,730 --> 00:09:46,480
只是一点点？

216
00:09:46,480 --> 00:09:49,390
嗯不错。

217
00:09:49,390 --> 00:09:50,280
在那里，我们走了。

218
00:09:50,280 --> 00:09:50,960
好。

219
00:09:50,960 --> 00:09:57,000
>> 所以我在这里，我
实现贪婪。

220
00:09:57,000 --> 00:10:01,430
虽然很多你们的写
贪婪form--，虽然环

221
00:10:01,430 --> 00:10:04,890
是一种完全可以接受的方式做
它 - 另一种方式来做到这一点是根​​本

222
00:10:04,890 --> 00:10:06,280
在分模。

223
00:10:06,280 --> 00:10:09,290
因为那样的话，你可以有你
值，然后让你的其余部分。

224
00:10:09,290 --> 00:10:11,150
然后你可以只
加上它一起。

225
00:10:11,150 --> 00:10:13,390
请问对我在做什么逻辑
这里是有意义的每一个人，

226
00:10:13,390 --> 00:10:14,117
之前我们开始？

227
00:10:14,117 --> 00:10:16,760

228
00:10:16,760 --> 00:10:17,980
有点？

229
00:10:17,980 --> 00:10:18,710
酷。

230
00:10:18,710 --> 00:10:19,210
太好了。

231
00:10:19,210 --> 00:10:21,290
这是一个非常性感的一块
的代码，我会说。

232
00:10:21,290 --> 00:10:23,502
就像我说的，大卫，在
讲课，过了一段时间，

233
00:10:23,502 --> 00:10:25,960
你们都开始看到的代码
作为东西是美丽的。

234
00:10:25,960 --> 00:10:29,950
有时，当你看到漂亮
代码，它是这样一个美妙的感觉。

235
00:10:29,950 --> 00:10:35,410
>> 因此然而，尽管这个代码是非常
美丽的，它不能正常工作。

236
00:10:35,410 --> 00:10:37,750
因此，让我们在这个运行check50。

237
00:10:37,750 --> 00:10:39,440
检查50 20--空中接力。

238
00:10:39,440 --> 00:10:43,221

239
00:10:43,221 --> 00:10:43,720
2？

240
00:10:43,720 --> 00:10:44,990
那是pset2？

241
00:10:44,990 --> 00:10:46,870
是啊。

242
00:10:46,870 --> 00:10:47,520
哦，PSET1。

243
00:10:47,520 --> 00:10:50,970

244
00:10:50,970 --> 00:10:52,890
好。

245
00:10:52,890 --> 00:10:53,900
所以我们运行check50。

246
00:10:53,900 --> 00:11:01,550

247
00:11:01,550 --> 00:11:07,170
>> 正如你们所看到的，
它的失败一对夫妇的案件。

248
00:11:07,170 --> 00:11:10,165
而对于一些你，在
做你的问题集的过程中，

249
00:11:10,165 --> 00:11:11,110
你喜欢啊，为什么不工作。

250
00:11:11,110 --> 00:11:13,318
为什么工作一段
值，而不是为别人？

251
00:11:13,318 --> 00:11:17,760
那么，GDB是要帮助你的身影
为什么这些投入并没有工作。

252
00:11:17,760 --> 00:11:18,320
>> 好。

253
00:11:18,320 --> 00:11:21,640
所以，让我们来看看，之一
检查我是失败的check50

254
00:11:21,640 --> 00:11:24,920
为0.41的输入值。

255
00:11:24,920 --> 00:11:27,830
所以正确答案
你应该得到一个4。

256
00:11:27,830 --> 00:11:33,090
而是我所打印出
是3-n中，这是不正确。

257
00:11:33,090 --> 00:11:36,190
因此，让我们只是手动运行它，只是
确保check50正常工作。

258
00:11:36,190 --> 00:11:36,940
让我们做./greedy。

259
00:11:36,940 --> 00:11:40,130

260
00:11:40,130 --> 00:11:43,340
哎呀，我一定要贪婪。

261
00:11:43,340 --> 00:11:43,840
在那里，我们走了。

262
00:11:43,840 --> 00:11:44,381
现在./greedy。

263
00:11:44,381 --> 00:11:46,950

264
00:11:46,950 --> 00:11:47,670
>> 多少钱是欠？

265
00:11:47,670 --> 00:11:49,550
让我们做0.41。

266
00:11:49,550 --> 00:11:52,590
而且是的，我们在这里看到
，它的输出3

267
00:11:52,590 --> 00:11:55,160
当正确的答案，
事实上，应为4。

268
00:11:55,160 --> 00:12:01,460
因此，让我们进入GDB，看看我们如何
可以去解决这个问题。

269
00:12:01,460 --> 00:12:03,992
>> 因此在第一步骤中
一直调试代码

270
00:12:03,992 --> 00:12:05,950
是设置一个断点，
或在这一点，你

271
00:12:05,950 --> 00:12:09,079
希望计算机或
调试器开始寻找。

272
00:12:09,079 --> 00:12:11,120
所以，如果你真的不
知道你的问题是什么，

273
00:12:11,120 --> 00:12:14,670
通常情况下，一般的事情，我们要
做的是设置了断点为主。

274
00:12:14,670 --> 00:12:18,520
所以，如果你们可以看到这
红色按钮就在那里，

275
00:12:18,520 --> 00:12:22,860
是的，这是我的设置
断点的主要功能。

276
00:12:22,860 --> 00:12:24,130
我点击了。

277
00:12:24,130 --> 00:12:26,130
>> 然后我就可以去了我的Debug按钮。

278
00:12:26,130 --> 00:12:27,036
我打那个按钮。

279
00:12:27,036 --> 00:12:31,710

280
00:12:31,710 --> 00:12:36,555
让我放大了，如果我能。

281
00:12:36,555 --> 00:12:38,020
在那里，我们走了。

282
00:12:38,020 --> 00:12:40,730
因此，我们有，在这里，在面板上的权利。

283
00:12:40,730 --> 00:12:43,680
我很抱歉，伙计们在后面，你
实在看不出真的很好。

284
00:12:43,680 --> 00:12:49,090
但本质上，所有的
该右侧面板做

285
00:12:49,090 --> 00:12:53,130
被跟踪的两个突出
线，这是代码行

286
00:12:53,130 --> 00:12:56,640
计算机正在运行，
以及所有的变量

287
00:12:56,640 --> 00:12:57,600
到这里。

288
00:12:57,600 --> 00:13:00,487
>> 所以，你有美分，硬币，N，
所有申报不同的东西

289
00:13:00,487 --> 00:13:01,070
在此刻。

290
00:13:01,070 --> 00:13:04,850
不用担心，因为我们没有真正
它们初始化的变量呢。

291
00:13:04,850 --> 00:13:07,200
因此，在你的电脑，你
电脑只是看到，

292
00:13:07,200 --> 00:13:14,376
哦，32767是最后使用的功能
在我的电脑的内存空间。

293
00:13:14,376 --> 00:13:16,000
所以这就是美分是目前。

294
00:13:16,000 --> 00:13:19,360
但是，没有，一旦运行该代码，
它应该成为初始化。

295
00:13:19,360 --> 00:13:24,110
>> 因此，让我们通过，一行
行，这是怎么回事的。

296
00:13:24,110 --> 00:13:25,350
好。

297
00:13:25,350 --> 00:13:29,400
所以，在这里是三个
按钮，我刚才解释。

298
00:13:29,400 --> 00:13:34,090
你有玩，或者运行功能，
按钮，你有步骤结束按钮，

299
00:13:34,090 --> 00:13:36,600
你也有步骤为按钮。

300
00:13:36,600 --> 00:13:41,260
并且基本上，所有三个
他们只是通过你的代码

301
00:13:41,260 --> 00:13:42,690
而做不同的事情。

302
00:13:42,690 --> 00:13:45,680
>> 所以通常情况下，当你正在调试，
我们不希望只是打游戏，

303
00:13:45,680 --> 00:13:47,930
因为比赛将只运行
你的代码，它的结束。

304
00:13:47,930 --> 00:13:49,070
然后，你不会真的
知道你的问题

305
00:13:49,070 --> 00:13:51,432
除非你设置多个断点。

306
00:13:51,432 --> 00:13:53,890
如果设置了多个断点，
它只是自动

307
00:13:53,890 --> 00:13:56,030
从一个断点运行，
到下一个，到下一个。

308
00:13:56,030 --> 00:13:58,030
但是，在这种情况下，我们已经
只是那一个，因为我们

309
00:13:58,030 --> 00:13:59,970
希望我们的工作方式
从顶部向下至底部。

310
00:13:59,970 --> 00:14:04,830
所以，我们要忽略按钮
现在为了这个计划。

311
00:14:04,830 --> 00:14:08,230
>> 因此，在步函数只是
在每一行的步骤

312
00:14:08,230 --> 00:14:11,510
并告诉您
计算机在做什么。

313
00:14:11,510 --> 00:14:14,630
该步骤为函数去
到实际的功能

314
00:14:14,630 --> 00:14:16,000
这是对你的代码行。

315
00:14:16,000 --> 00:14:19,070
因此，例如，如printf（），
这是一个函数，对不对？

316
00:14:19,070 --> 00:14:21,980
如果我想在物理上一步
到printf（）函数，

317
00:14:21,980 --> 00:14:25,610
我真的进入片
其中，printf（）的写，看看代码

318
00:14:25,610 --> 00:14:26,730
这是怎么回事那里。

319
00:14:26,730 --> 00:14:29,924
>> 但通常，我们假设
我们为您提供的代码工作。

320
00:14:29,924 --> 00:14:31,340
我们假设printf（）的正常工作。

321
00:14:31,340 --> 00:14:33,170
我们假设调用getInt（）的工作。

322
00:14:33,170 --> 00:14:35,170
因此，有没有必要
走进这些功能。

323
00:14:35,170 --> 00:14:37,170
但是，如果有功能
你写你自己

324
00:14:37,170 --> 00:14:39,060
要检查
发生了什么事情，

325
00:14:39,060 --> 00:14:41,200
你会想一步
入该功能。

326
00:14:41,200 --> 00:14:43,940
>> 所以现在我们只是
跨过这段代码。

327
00:14:43,940 --> 00:14:44,485
所以，让我们来看看。

328
00:14:44,485 --> 00:14:46,547
哦，打印，“哦，海，怎么样
多大的改变是欠？“

329
00:14:46,547 --> 00:14:47,130
我们不关心。

330
00:14:47,130 --> 00:14:49,830
我们知道的工作，
所以我们跳过它。

331
00:14:49,830 --> 00:14:53,290
>> 因此n，这是我们的浮动是
我们已经initialized--或declared--

332
00:14:53,290 --> 00:14:56,810
在顶部，我们现在是
等于说，以GetFloat（）。

333
00:14:56,810 --> 00:14:57,810
因此，让我们跨过这道。

334
00:14:57,810 --> 00:14:59,580
而我们在看
底部这里，程序

335
00:14:59,580 --> 00:15:03,360
这促使我输入一个值。

336
00:15:03,360 --> 00:15:08,580
因此，让我们输入我们想要的值
在这里测试，这是0.41。

337
00:15:08,580 --> 00:15:09,160
太好了。

338
00:15:09,160 --> 00:15:12,780
>> 所以，现在N--做你们看
这里，在bottom--它的

339
00:15:12,780 --> 00:15:15,140
stored--因为我们
还没有四舍五入的是，它

340
00:15:15,140 --> 00:15:19,540
存储在这个像巨大
浮动是0.4099999996，

341
00:15:19,540 --> 00:15:22,550
这是足够接近我们的
目的，现在，到0.41。

342
00:15:22,550 --> 00:15:26,090
然后，我们将在后面看到，因为我们
继续加强在该程序，

343
00:15:26,090 --> 00:15:29,850
后这里，正变得
圆润和分成为41。

344
00:15:29,850 --> 00:15:30,350
太好了。

345
00:15:30,350 --> 00:15:32,230
因此，我们知道，我们的舍入的工作。

346
00:15:32,230 --> 00:15:34,700
我们知道，我们有
正确的数量美分，

347
00:15:34,700 --> 00:15:36,990
所以我们知道，这是
没有真正的问题。

348
00:15:36,990 --> 00:15:40,050
>> 因此，我们将继续加强
在此计划。

349
00:15:40,050 --> 00:15:40,900
我们去这里。

350
00:15:40,900 --> 00:15:46,139
而这行代码之后的话，我们
要知道我们有多少个季度有。

351
00:15:46,139 --> 00:15:46,680
我们跳过。

352
00:15:46,680 --> 00:15:52,040
而且你看我们做什么，其实，有一个
季度，因为我们已经减去25

353
00:15:52,040 --> 00:15:53,790
从41我们的初始值。

354
00:15:53,790 --> 00:15:55,890
我们有16个左右为我们美分。

355
00:15:55,890 --> 00:15:58,830
>> 大家是否明白如何
该程序是通过步进

356
00:15:58,830 --> 00:16:02,980
为什么美分现已成为16
为什么，现在，硬币已经成为1？

357
00:16:02,980 --> 00:16:04,610
是每个人以下的逻辑是什么？

358
00:16:04,610 --> 00:16:05,110
酷。

359
00:16:05,110 --> 00:16:07,860
因此，作为这一点的，在
计划的工作，对不对？

360
00:16:07,860 --> 00:16:09,797
我们知道这是做完全
我们希望它。

361
00:16:09,797 --> 00:16:11,880
而我们实际上并没有
要打印出来，哦，

362
00:16:11,880 --> 00:16:14,430
是仙在这一点上，
什么是硬币在此点。

363
00:16:14,430 --> 00:16:17,170
>> 我们将继续经历的程序。

364
00:16:17,170 --> 00:16:18,100
跨越。

365
00:16:18,100 --> 00:16:18,620
酷。

366
00:16:18,620 --> 00:16:19,700
我们去了助攻。

367
00:16:19,700 --> 00:16:20,200
太好了。

368
00:16:20,200 --> 00:16:22,367
我们看到，它采取
关闭$ 0.10一角钱。

369
00:16:22,367 --> 00:16:23,450
而现在我们有两个硬币。

370
00:16:23,450 --> 00:16:25,260
这是正确的。

371
00:16:25,260 --> 00:16:31,555
>> 我们去了几个便士而我们看到的
我们已经得到了遗留美分。

372
00:16:31,555 --> 00:16:32,680
嗯，这很奇怪。

373
00:16:32,680 --> 00:16:37,540
在这里，在该程序中，我应该
已减去我便士。

374
00:16:37,540 --> 00:16:39,400
也许我只是没有
这样做行权。

375
00:16:39,400 --> 00:16:42,190
唉，你可以看到
在这里，因为我们知道

376
00:16:42,190 --> 00:16:44,360
我们正在加紧
通过线32和33，

377
00:16:44,360 --> 00:16:50,560
这就是我们的计划
不当有变量运行。

378
00:16:50,560 --> 00:16:55,136
因此，我们可以看看，看看，哦，
我在这里减去美分，

379
00:16:55,136 --> 00:16:57,010
但我没有实际
添加到我的币值。

380
00:16:57,010 --> 00:16:57,860
我加入到美分。

381
00:16:57,860 --> 00:17:00,234
我不希望添加到
分钱，我要添加到硬币。

382
00:17:00,234 --> 00:17:05,420
因此，如果我们改变，要硬币，
我们已经有了一个工作程序。

383
00:17:05,420 --> 00:17:06,730
我可以运行check50。

384
00:17:06,730 --> 00:17:11,063
你可以只退出的GDB右出
这里，然后再次运行check50。

385
00:17:11,063 --> 00:17:11,938
我可以做到这一点。

386
00:17:11,938 --> 00:17:14,822

387
00:17:14,822 --> 00:17:18,480
我一定要贪婪。

388
00:17:18,480 --> 00:17:19,940
0.41。

389
00:17:19,940 --> 00:17:22,819
而在这里，它的印刷
出正确的答案。

390
00:17:22,819 --> 00:17:26,569
>> 所以当你们可以看到，GDB
是一个非常强大的工具

391
00:17:26,569 --> 00:17:29,940
当我们有这么多的代码
怎么回事，这么多的变数

392
00:17:29,940 --> 00:17:32,510
它很难对我们来说，作为
一个人，来跟踪。

393
00:17:32,510 --> 00:17:35,360
计算机，在GDB
调试器，有能力

394
00:17:35,360 --> 00:17:37,020
多事的。

395
00:17:37,020 --> 00:17:40,480
我知道，在VISIONAIRE，你们可能
可能击中了一些段故障

396
00:17:40,480 --> 00:17:43,150
因为你正在运行
从你的阵列的界限。

397
00:17:43,150 --> 00:17:46,510
在凯撒的例子，这是
正是我在这里实现。

398
00:17:46,510 --> 00:17:50,060
>> 所以，我忘了检查
如果会发生什么，我

399
00:17:50,060 --> 00:17:52,510
没有两个命令行参数。

400
00:17:52,510 --> 00:17:53,880
我只是没有摆在那检查。

401
00:17:53,880 --> 00:17:57,380
所以，如果我跑Debug--我设置
我的断点就在这里。

402
00:17:57,380 --> 00:17:58,055
我运行调试。

403
00:17:58,055 --> 00:18:15,880

404
00:18:15,880 --> 00:18:16,550
>> 好。

405
00:18:16,550 --> 00:18:17,050
是啊。

406
00:18:17,050 --> 00:18:20,350
所以实际上，GDB应该
已经告诉我，

407
00:18:20,350 --> 00:18:22,300
是分割故障出现。

408
00:18:22,300 --> 00:18:24,883
我不知道发生了什么事情
在那里，但是当我运行它，

409
00:18:24,883 --> 00:18:25,590
这是工作。

410
00:18:25,590 --> 00:18:29,410
当您运行通过行代码
GDB可能只是突然退出你，

411
00:18:29,410 --> 00:18:31,540
上去看看红色的错误是什么。

412
00:18:31,540 --> 00:18:33,930
它会告诉你的，嘿嘿，你
有段错误，

413
00:18:33,930 --> 00:18:38,550
这意味着您尝试访问
以阵列的空间不存在的。

414
00:18:38,550 --> 00:18:39,050
是啊。

415
00:18:39,050 --> 00:18:43,280
>> 因此，在接下来的问题
本周集，你们

416
00:18:43,280 --> 00:18:45,600
可能有很多
变量左右浮动。

417
00:18:45,600 --> 00:18:48,560
你不会是知道
它们都是指在某一点。

418
00:18:48,560 --> 00:18:53,560
因此，广发行将真正帮助你在盘算
它们是什么都等于

419
00:18:53,560 --> 00:18:55,940
并能够看到直观。

420
00:18:55,940 --> 00:19:01,995
有没有人困惑于如何
任何被工作？

421
00:19:01,995 --> 00:19:02,495
酷。

422
00:19:02,495 --> 00:19:10,121

423
00:19:10,121 --> 00:19:10,620
好吧。

424
00:19:10,620 --> 00:19:14,260
所以在这之后，我们
去潜水权

425
00:19:14,260 --> 00:19:17,562
成四种不同的
排序类型本周。

426
00:19:17,562 --> 00:19:19,520
你们有多少人，第一次
所有的人，在我们开始之前，

427
00:19:19,520 --> 00:19:23,020
读完整个规范的pset3？

428
00:19:23,020 --> 00:19:23,824
好。

429
00:19:23,824 --> 00:19:24,740
我是你们的骄傲。

430
00:19:24,740 --> 00:19:29,110
这就像半个班，这
是显著超过上一次。

431
00:19:29,110 --> 00:19:33,950
>> 所以，这是伟大的，因为当
我们谈论的内容

432
00:19:33,950 --> 00:19:36,170
在lecture--还是遗憾，
在section--我喜欢

433
00:19:36,170 --> 00:19:38,210
以涉及了很多的
回PSET是什么

434
00:19:38,210 --> 00:19:40,210
你想如何
实现在你的pset中。

435
00:19:40,210 --> 00:19:42,400
所以，如果你来有
读取规格，它会

436
00:19:42,400 --> 00:19:45,510
是一个更容易让你明白
我说的是，当我说，

437
00:19:45,510 --> 00:19:48,720
嘿，这可能是一个真正的
实现这种好地方。

438
00:19:48,720 --> 00:19:52,870
所以，你们谁读了
SPEC知道，作为你的PSET的一部分，

439
00:19:52,870 --> 00:19:54,900
你将不得不
写一个排序的类型。

440
00:19:54,900 --> 00:19:58,670
所以，这可能是非常有帮助
今天很多你。

441
00:19:58,670 --> 00:20:01,760
>> 因此，我们将刚开始时，
本质上，最简单类型

442
00:20:01,760 --> 00:20:04,580
排序，选择排序。

443
00:20:04,580 --> 00:20:06,800
典型的算法
我们怎么会去这

444
00:20:06,800 --> 00:20:10,460
is--大卫通过这些全都走了进去
讲座，所以我会很快待着

445
00:20:10,460 --> 00:20:13,900
这里 - 本质上，你
有值的数组。

446
00:20:13,900 --> 00:20:17,170
然后你找到
最小的未分类的价值

447
00:20:17,170 --> 00:20:20,200
和你交换与价值
第一个未排序的值。

448
00:20:20,200 --> 00:20:22,700
然后你只是不断重复
以列表的其余部分。

449
00:20:22,700 --> 00:20:25,740
>> 而且这里有一个直观的解释
如何将工作。

450
00:20:25,740 --> 00:20:30,460
因此，例如，如果我们开始
与五个元件的阵列，索引

451
00:20:30,460 --> 00:20:35,910
0至4，用3,5，2,6，和4个值
所以，现在摆在array--，

452
00:20:35,910 --> 00:20:38,530
我们只是假设
他们都是未分类

453
00:20:38,530 --> 00:20:41,130
因为我们还没有测试过，否则。

454
00:20:41,130 --> 00:20:44,130
>> 因此，如何选择排序会
工作是，那就先

455
00:20:44,130 --> 00:20:46,800
通过整体运行
未排序的数组。

456
00:20:46,800 --> 00:20:49,120
这将挑选出的最小值。

457
00:20:49,120 --> 00:20:51,750
在这种情况下，如图3所示，右
现在，是最小的。

458
00:20:51,750 --> 00:20:52,680
它得到5。

459
00:20:52,680 --> 00:20:55,620
不，5不大于than--
或不好意思，不低于than-- 3。

460
00:20:55,620 --> 00:20:57,779
所以最小值仍然3。

461
00:20:57,779 --> 00:20:58,695
然后你到2。

462
00:20:58,695 --> 00:21:00,990
电脑看，哦，2小于3。

463
00:21:00,990 --> 00:21:02,750
2现在必须的最小值。

464
00:21:02,750 --> 00:21:06,630
所以2掉期与第一个值。

465
00:21:06,630 --> 00:21:10,702
>> 因此，人们通过后，我们确实看到
该2和3被交换。

466
00:21:10,702 --> 00:21:13,910
而我们只是要继续做
这再次与阵列的其余部分。

467
00:21:13,910 --> 00:21:17,660
因此，我们将只运行通过
最后四个指标的数组。

468
00:21:17,660 --> 00:21:20,670
我们会看到，3
下一最小值。

469
00:21:20,670 --> 00:21:23,240
所以，我们要交换与4。

470
00:21:23,240 --> 00:21:26,900
然后，我们只是要继续
贯穿直到最后，你

471
00:21:26,900 --> 00:21:33,730
得到一个排序的数组中
2，3，4，5，和6被所有排序。

472
00:21:33,730 --> 00:21:37,530
大家是否明白逻辑
如何选择排序工作？

473
00:21:37,530 --> 00:21:39,669
>> 你只要有某种
的最小值。

474
00:21:39,669 --> 00:21:41,210
你跟踪的那是什么。

475
00:21:41,210 --> 00:21:45,170
每当你找到它，你将其交换
与在array--第一值

476
00:21:45,170 --> 00:21:48,740
或者，不是第一value--
阵列中的下一个值。

477
00:21:48,740 --> 00:21:50,150
酷。

478
00:21:50,150 --> 00:21:55,460
>> 所以当你们那种
从短暂的一瞥看到，

479
00:21:55,460 --> 00:21:58,450
我们要伪代码这一点。

480
00:21:58,450 --> 00:22:02,510
所以，如果你们在后面要
组成一个小组，每个人都在一张桌子

481
00:22:02,510 --> 00:22:06,170
可以形成一个小伙伴，我要去
给你们喜欢3分钟

482
00:22:06,170 --> 00:22:08,190
刚才讲通过
逻辑，英语，

483
00:22:08,190 --> 00:22:14,161
对我们如何能够实现
伪代码写一个选择排序。

484
00:22:14,161 --> 00:22:14,910
还有的糖果。

485
00:22:14,910 --> 00:22:16,118
请上来，并得到糖果。

486
00:22:16,118 --> 00:22:19,520
如果你在后面，你想
糖果，我会向你扔糖果。

487
00:22:19,520 --> 00:22:22,850
其实，做你 - 爽。

488
00:22:22,850 --> 00:22:23,552
噢对不起。

489
00:22:23,552 --> 00:22:26,751

490
00:22:26,751 --> 00:22:27,250
好。

491
00:22:27,250 --> 00:25:23,880

492
00:25:23,880 --> 00:25:27,140
>> 所以，如果我们想，作为
一类，写伪代码

493
00:25:27,140 --> 00:25:30,466
如何人们可能接近
这个问题，只是觉得自由。

494
00:25:30,466 --> 00:25:32,340
我就到处去和，
为了，问群体

495
00:25:32,340 --> 00:25:35,065
对于下一行
我们应该做的。

496
00:25:35,065 --> 00:25:37,840
所以，如果你们想开始
关，什么是第一件事情

497
00:25:37,840 --> 00:25:40,600
当你试图做
实现的方式来解决这个方案

498
00:25:40,600 --> 00:25:43,480
有选择地排序列表？

499
00:25:43,480 --> 00:25:46,349
让我们只是假设我们
有一个数组，没事吧？

500
00:25:46,349 --> 00:25:49,088
>> 听众：你想创造一些
排序[听不清]你是

501
00:25:49,088 --> 00:25:50,420
通过你的整个阵列的运行。

502
00:25:50,420 --> 00:25:51,128
>> ANDI彭：对。

503
00:25:51,128 --> 00:25:54,100
所以，你会想迭代
通过每一个空间，对不对？

504
00:25:54,100 --> 00:26:05,490
很好。

505
00:26:05,490 --> 00:26:08,600
如果你们想给我
接下来line--是啊，在后面。

506
00:26:08,600 --> 00:26:11,414

507
00:26:11,414 --> 00:26:13,290
>> 听众：检查他们
全部为最小。

508
00:26:13,290 --> 00:26:14,248
>> ANDI彭：我们去那里。

509
00:26:14,248 --> 00:26:17,438
因此，我们希望通过和检查
看到最小值是什么，对不对？

510
00:26:17,438 --> 00:26:22,110

511
00:26:22,110 --> 00:26:24,840
我要缩写，为“最小”。

512
00:26:24,840 --> 00:26:27,658
你们有什么想后做
你已经找到了最小值？

513
00:26:27,658 --> 00:26:28,533
>> 听众：[听不清]

514
00:26:28,533 --> 00:26:29,942

515
00:26:29,942 --> 00:26:33,150
ANDI彭：所以你会想
与第一个数组中打开它，

516
00:26:33,150 --> 00:26:33,650
对？

517
00:26:33,650 --> 00:26:45,120

518
00:26:45,120 --> 00:26:46,850
这是开始的时候，我会说。

519
00:26:46,850 --> 00:26:47,220
好吧。

520
00:26:47,220 --> 00:26:50,386
所以，现在你已经换第一
一，什么你想以后做什么？

521
00:26:50,386 --> 00:26:54,840
所以，现在我们知道，这一个在这里
必须是最小的值，对不对？

522
00:26:54,840 --> 00:26:58,310
然后，你有一个额外的休息
该阵列是无序的。

523
00:26:58,310 --> 00:27:01,569
所以，你想在这里做的，如果你有什么
人想给我的下一行？

524
00:27:01,569 --> 00:27:04,610
听众：那么接下来你要遍历
通过该阵列的剩余部分。

525
00:27:04,610 --> 00:27:05,276
ANDI彭：是的。

526
00:27:05,276 --> 00:27:09,857
还等什么，通过它遍历
那种暗示我们可能会需要什么？

527
00:27:09,857 --> 00:27:10,440
什么类型的of--

528
00:27:10,440 --> 00:27:12,057
>> 听众：哦，一个额外的变量？

529
00:27:12,057 --> 00:27:13,890
ANDI彭：可能
另一个循环，对不对？

530
00:27:13,890 --> 00:27:28,914
因此，我们可能会想
迭代through--很大。

531
00:27:28,914 --> 00:27:31,830
然后，你要回去
可能再次检查最低，

532
00:27:31,830 --> 00:27:32,100
对？

533
00:27:32,100 --> 00:27:34,975
而你要不断重复
这一点，因为环正要

534
00:27:34,975 --> 00:27:36,010
继续运行，对吧？

535
00:27:36,010 --> 00:27:39,190
>> 所以当你们可以看到，我们
只是有一个大致的伪代码

536
00:27:39,190 --> 00:27:41,480
我们如何希望这个节目的样子。

537
00:27:41,480 --> 00:27:46,646
这里这个迭代，我们怎么
通常需要在我们的代码编写

538
00:27:46,646 --> 00:27:49,270
如果我们要遍历一个
阵列，什么类型的结构？

539
00:27:49,270 --> 00:27:51,030
我想Christabel
之前已经说过这一点。

540
00:27:51,030 --> 00:27:51,500
>> 听众：for循环。

541
00:27:51,500 --> 00:27:52,160
>> ANDI彭：一种循环？

542
00:27:52,160 --> 00:27:52,770
没错。

543
00:27:52,770 --> 00:27:56,060
因此，这可能是
将是一个for循环。

544
00:27:56,060 --> 00:27:59,240
什么是这里的检查会意味着什么呢？

545
00:27:59,240 --> 00:28:02,536
通常情况下，如果你想查询
如果有什么东西else--

546
00:28:02,536 --> 00:28:03,270
>> 听众：如果。

547
00:28:03,270 --> 00:28:06,790
>> ANDI彭：如果一个，对不对？

548
00:28:06,790 --> 00:28:10,790
然后在这里交换，我们将
去了以后，因为大卫·

549
00:28:10,790 --> 00:28:12,770
通过讲座去为好。

550
00:28:12,770 --> 00:28:14,580
然后第二个迭代implies--

551
00:28:14,580 --> 00:28:15,120
>> 听众：另一个循环。

552
00:28:15,120 --> 00:28:16,745
>> ANDI彭：--another for循环，没错。

553
00:28:16,745 --> 00:28:19,870

554
00:28:19,870 --> 00:28:22,000
因此，如果我们正在寻找
在这个正确的，我们

555
00:28:22,000 --> 00:28:24,680
可以看到，我们可能
将需要一个嵌套的循环

556
00:28:24,680 --> 00:28:28,330
在有一个条件语句
然后代码的一个实际的一块是

557
00:28:28,330 --> 00:28:31,360
要交换值。

558
00:28:31,360 --> 00:28:35,980
所以，我只是一般写
这里一个伪代码。

559
00:28:35,980 --> 00:28:38,910
然后，我们实际上会
到身体上，作为一类，

560
00:28:38,910 --> 00:28:40,700
试试这个今天实现。

561
00:28:40,700 --> 00:28:42,486
让我们回到这个IDE。

562
00:28:42,486 --> 00:28:49,243

563
00:28:49,243 --> 00:28:50,230
>> 嗯，哦。

564
00:28:50,230 --> 00:28:51,754
这是为什么不是 - 它就在那里。

565
00:28:51,754 --> 00:28:52,253
好。

566
00:28:52,253 --> 00:28:55,834

567
00:28:55,834 --> 00:28:57,500
对不起，让我尽量放大一点。

568
00:28:57,500 --> 00:28:59,310
在那里，我们走了。

569
00:28:59,310 --> 00:29:05,060
我做的是在这里我创建
一个名为“选择/ sort.c。”

570
00:29:05,060 --> 00:29:10,860
我创建了九个数组
值，4，8 2，1，6,9，7,5，3。

571
00:29:10,860 --> 00:29:14,370
目前，你可以
看，他们是无序的。

572
00:29:14,370 --> 00:29:17,880
n为将成为数
告诉你值量

573
00:29:17,880 --> 00:29:18,920
你在你的阵列。

574
00:29:18,920 --> 00:29:20,670
在这种情况下，我们有九个值。

575
00:29:20,670 --> 00:29:23,760
我刚刚得到了一个for循环在这里
打印出的排序的数组。

576
00:29:23,760 --> 00:29:28,370
>> 而在最后，我也得到了一个为
循环，只是打印出来了。

577
00:29:28,370 --> 00:29:32,070
因此从理论上说，如果此程序
工作正常，到了最后，

578
00:29:32,070 --> 00:29:35,670
你应该看到一个打印的循环
其中，1，2，3，4，5，6，7，8，

579
00:29:35,670 --> 00:29:39,310
9都是正确的顺序。

580
00:29:39,310 --> 00:29:43,410
>> 所以，我们在这里得到了我们的伪代码。

581
00:29:43,410 --> 00:29:46,090
有谁想用于：我只是
要去问volunteers--

582
00:29:46,090 --> 00:29:49,540
确切地告诉我，如果什么类型
我们希望，第一，只是想迭代

583
00:29:49,540 --> 00:29:52,840
通过这个数组的开始？

584
00:29:52,840 --> 00:29:55,204
什么是代码行我
可能要在这里需要什么？

585
00:29:55,204 --> 00:29:56,990
>> 听众：[听不清]

586
00:29:56,990 --> 00:29:59,010
>> ANDI彭：是啊，感觉
免费用于：对不起，你

587
00:29:59,010 --> 00:30:02,318
不必忍受up--手感
自由地提高你的声音有点。

588
00:30:02,318 --> 00:30:08,190
>> 顾客：INT I等于0--

589
00:30:08,190 --> 00:30:10,690
>> ANDI彭：是的，不错。

590
00:30:10,690 --> 00:30:15,220
>> 观众：我是小于数组的长度。

591
00:30:15,220 --> 00:30:19,630
>> ANDI彭：因此，保持在
介意在这里，因为我们

592
00:30:19,630 --> 00:30:23,060
不具有功能
告诉我们的阵列的长度，

593
00:30:23,060 --> 00:30:25,790
我们已经有一个
值，其存储。

594
00:30:25,790 --> 00:30:27,920
对？

595
00:30:27,920 --> 00:30:31,010
另一件让
在mind--以阵列

596
00:30:31,010 --> 00:30:33,940
九价值观，有什么指标？

597
00:30:33,940 --> 00:30:38,720
远的不说这个数组是0至3。

598
00:30:38,720 --> 00:30:41,500
你看，最后
指数实际上是3。

599
00:30:41,500 --> 00:30:45,530
这不是4，即使有
阵列中的四个值。

600
00:30:45,530 --> 00:30:49,866
>> 所以在这里，我们必须非常小心，
什么我们条件的长度

601
00:30:49,866 --> 00:30:50,490
将是。

602
00:30:50,490 --> 00:30:51,948
>> 听众：那岂不是为n减去1？

603
00:30:51,948 --> 00:30:54,440
ANDI彭：这是怎么回事
Ñ​​减去1，正好。

604
00:30:54,440 --> 00:30:57,379
这是否有意义，为什么
它n值减1，每个人？

605
00:30:57,379 --> 00:30:58,920
这是因为数组是零索引。

606
00:30:58,920 --> 00:31:02,010
他们从0开始并运行最多n个减1。

607
00:31:02,010 --> 00:31:03,210
是的，这是一个有点棘手。

608
00:31:03,210 --> 00:31:03,730
好。

609
00:31:03,730 --> 00:31:05,929
接着 - 

610
00:31:05,929 --> 00:31:08,054
听众：Isnt'1那
已经采取的虽然照顾，

611
00:31:08,054 --> 00:31:11,400
通过刚才不是说“小于或
等于“，只是说：”不到？“

612
00:31:11,400 --> 00:31:13,108
>> ANDI彭：这是一个
非常好的问题。

613
00:31:13,108 --> 00:31:13,630
所以，是的。

614
00:31:13,630 --> 00:31:17,410
而且，我们的方式是说
实施检查权，

615
00:31:17,410 --> 00:31:19,120
你需要比较两个值。

616
00:31:19,120 --> 00:31:21,009
所以，你真的想
离开“到”空。

617
00:31:21,009 --> 00:31:23,050
因为如果你比较
这一次，你不会

618
00:31:23,050 --> 00:31:25,530
有后什么
要比较的，对不对？

619
00:31:25,530 --> 00:31:27,460
是啊。

620
00:31:27,460 --> 00:31:29,297
所以我++。

621
00:31:29,297 --> 00:31:30,380
让我们添加括号研究。

622
00:31:30,380 --> 00:31:30,880
哎呦。

623
00:31:30,880 --> 00:31:33,950

624
00:31:33,950 --> 00:31:34,710
太好了。

625
00:31:34,710 --> 00:31:39,117
因此，我们有初
我们的外环。

626
00:31:39,117 --> 00:31:41,450
所以，现在我们可能要
建立保持一个变量

627
00:31:41,450 --> 00:31:43,085
轨道的最小值，对不对？

628
00:31:43,085 --> 00:31:45,751
没有人想给我
行代码，将做到这一点？

629
00:31:45,751 --> 00:31:48,700

630
00:31:48,700 --> 00:31:53,570
我们需要什么，如果我们打算
想储存什么？

631
00:31:53,570 --> 00:31:55,047
>> 对。

632
00:31:55,047 --> 00:31:57,630
对于也许一个更好的名字
将be--“临时”完全works--

633
00:31:57,630 --> 00:32:00,655
也许更恰当地命名会是这样，
如果我们希望最小value--

634
00:32:00,655 --> 00:32:01,624
>> 听众：最小。

635
00:32:01,624 --> 00:32:02,790
ANDI彭：分钟，我们走吧。

636
00:32:02,790 --> 00:32:05,230
分将是一件好事。

637
00:32:05,230 --> 00:32:08,340
所以在这里，我们怎么
要初始化为？

638
00:32:08,340 --> 00:32:09,620
这是一个有点棘手。

639
00:32:09,620 --> 00:32:13,580
因为现在在
开始本阵，

640
00:32:13,580 --> 00:32:15,730
你有没有看什么，对不对？

641
00:32:15,730 --> 00:32:19,200
还等什么，自动，如果
我们只是i等于0，

642
00:32:19,200 --> 00:32:22,302
我们怎么想初始化
我们的第一个最小值？

643
00:32:22,302 --> 00:32:22,802
观众：我。

644
00:32:22,802 --> 00:32:24,790
ANDI彭：我，没错。

645
00:32:24,790 --> 00:32:27,040
Christabel，那我们为什么还要
它初始化到我？

646
00:32:27,040 --> 00:32:28,510
>> 听众：因为，
我们从0开始。

647
00:32:28,510 --> 00:32:31,660
所以，因为我们没有什么可比较
它，最小最终会被0。

648
00:32:31,660 --> 00:32:32,451
>> ANDI鹏：没错。

649
00:32:32,451 --> 00:32:34,400
所以她完全正确。

650
00:32:34,400 --> 00:32:36,780
因为我们还没有真正
看着任何东西，

651
00:32:36,780 --> 00:32:38,680
我们不知道我们的最低值。

652
00:32:38,680 --> 00:32:41,960
我们希望只是将其初始化为
我，这，目前，就在这里。

653
00:32:41,960 --> 00:32:44,750
而且，我们将继续
向下移动，这阵，

654
00:32:44,750 --> 00:32:48,122
我们将看到，每个
额外的传球，我递增。

655
00:32:48,122 --> 00:32:49,830
因此，在这一点上，
我很可能会

656
00:32:49,830 --> 00:32:52,329
想为最小，
因为这将是什么

657
00:32:52,329 --> 00:32:54,520
是未排序数组的开始。

658
00:32:54,520 --> 00:32:55,270
酷。

659
00:32:55,270 --> 00:32:58,720
>> 所以，现在我们要添加
一个for循环，这里的

660
00:32:58,720 --> 00:33:03,225
要遍历
未分类，或该阵列的其余部分。

661
00:33:03,225 --> 00:33:05,808
没有人想给我一个
行代码，将做到这一点？

662
00:33:05,808 --> 00:33:08,870

663
00:33:08,870 --> 00:33:11,330
Hint--我们需要什么到这里？

664
00:33:11,330 --> 00:33:17,320

665
00:33:17,320 --> 00:33:18,820
这是怎么回事往这个循环？

666
00:33:18,820 --> 00:33:19,465
是啊。

667
00:33:19,465 --> 00:33:21,590
听众：所以我们会想
有一个不同的整数，

668
00:33:21,590 --> 00:33:25,080
因为我们通过休息运行
数组，而不是我，所以也许对

669
00:33:25,080 --> 00:33:25,760
学家

670
00:33:25,760 --> 00:33:27,301
>> ANDI彭：是啊，J听起来不错。

671
00:33:27,301 --> 00:33:27,850
等于？

672
00:33:27,850 --> 00:33:33,930
>> 听众：那将是我加1，因为
你开始的下一个值。

673
00:33:33,930 --> 00:33:40,395
然后到end--如此反复，j为
小于n减去1，然后J ++以下。

674
00:33:40,395 --> 00:33:41,103
ANDI彭：太好了。

675
00:33:41,103 --> 00:33:48,510

676
00:33:48,510 --> 00:33:52,750
>> 然后在这里，我们将要
检查，看看是否符合我们的条件，

677
00:33:52,750 --> 00:33:53,250
对？

678
00:33:53,250 --> 00:33:55,740
因为你想
改变的最小值

679
00:33:55,740 --> 00:33:58,700
如果它实际上是小于什么
你对比的话，对不对？

680
00:33:58,700 --> 00:34:01,146
那么，我们将要在这里？

681
00:34:01,146 --> 00:34:04,160

682
00:34:04,160 --> 00:34:04,897
请检查。

683
00:34:04,897 --> 00:34:06,730
声明什么类型
我们有可能将

684
00:34:06,730 --> 00:34:08,389
TI想，如果用我们
要检查些什么呢？

685
00:34:08,389 --> 00:34:09,360
>> 听众：if语句。

686
00:34:09,360 --> 00:34:10,485
>> ANDI彭：if语句。

687
00:34:10,485 --> 00:34:13,155
所以if--，什么将是
我们希望里面的状况

688
00:34:13,155 --> 00:34:13,988
我们的if语句？

689
00:34:13,988 --> 00:34:18,255

690
00:34:18,255 --> 00:34:22,960
>> 听众：如果j值
小于I--值

691
00:34:22,960 --> 00:34:24,600
>> ANDI鹏：没错。

692
00:34:24,600 --> 00:34:27,480
所以if--所以这个数组被称为“数组”。

693
00:34:27,480 --> 00:34:27,980
太好了。

694
00:34:27,980 --> 00:34:30,465
因此，如果array--那是什么？

695
00:34:30,465 --> 00:34:31,090
再说一次。

696
00:34:31,090 --> 00:34:39,590
>> 听众：如果array-j是小于
数组我的话，就要改变最小。

697
00:34:39,590 --> 00:34:41,590
所以分钟就学家

698
00:34:41,590 --> 00:34:44,590

699
00:34:44,590 --> 00:34:47,249
>> ANDI彭：这是否有意义吗？

700
00:34:47,249 --> 00:34:48,670
好。

701
00:34:48,670 --> 00:34:52,929
而现在到这里，我们其实
要实现交换，对不对？

702
00:34:52,929 --> 00:34:58,285
所以记得，在演讲中，大卫，当
他是想换the--是什么

703
00:34:58,285 --> 00:34:59,996
它 - 橙汁和milk--

704
00:34:59,996 --> 00:35:01,150
>> 听众：这是毛。

705
00:35:01,150 --> 00:35:02,816
>> ANDI彭：是啊，这是种毛。

706
00:35:02,816 --> 00:35:05,310
但它是一个相当不错的
概念展示时间。

707
00:35:05,310 --> 00:35:08,430
因此，认为你的价值在这里。

708
00:35:08,430 --> 00:35:10,794
你有一个数组
的分，i的阵列，

709
00:35:10,794 --> 00:35:12,460
或不管我们想在这里交换。

710
00:35:12,460 --> 00:35:15,310
而且你可能无法将其倒入
对方在同一时间，对吧？

711
00:35:15,310 --> 00:35:17,180
那么究竟是为了什么
需要创建在这里

712
00:35:17,180 --> 00:35:19,126
为了正确交换价值？

713
00:35:19,126 --> 00:35:19,820
>> 听众：一个临时变量。

714
00:35:19,820 --> 00:35:21,370
>> ANDI彭：一个临时变量。

715
00:35:21,370 --> 00:35:22,570
因此，让我们做INT温度。

716
00:35:22,570 --> 00:35:25,681
你看，这将是一个更好的
时间用于：哇，那是什么？

717
00:35:25,681 --> 00:35:26,180
好。

718
00:35:26,180 --> 00:35:29,800
因此，这将是一个更好的
时间命名变量“温度”。

719
00:35:29,800 --> 00:35:30,730
因此，让我们做INT温度。

720
00:35:30,730 --> 00:35:32,563
什么是我们要
SET TEMP等于在这里？

721
00:35:32,563 --> 00:35:34,752

722
00:35:34,752 --> 00:35:35,335
听众：最小？

723
00:35:35,335 --> 00:35:38,508

724
00:35:38,508 --> 00:35:39,716
ANDI彭：这是一个有点棘手。

725
00:35:39,716 --> 00:35:43,110

726
00:35:43,110 --> 00:35:44,880
它实际上无所谓到底。

727
00:35:44,880 --> 00:35:47,690
它什么都无所谓
为了您选择交换

728
00:35:47,690 --> 00:35:50,862
只要你确保你
跟踪你交换什么。

729
00:35:50,862 --> 00:35:52,250
>> 听众：这可能是数组我。

730
00:35:52,250 --> 00:35:53,666
>> ANDI彭：是的，让我们做阵列我。

731
00:35:53,666 --> 00:35:55,950

732
00:35:55,950 --> 00:35:59,305
然后什么是下一行
的代码，我们要在这里？

733
00:35:59,305 --> 00:36:00,680
听众：阵列-i等于阵列-J。

734
00:36:00,680 --> 00:36:07,154

735
00:36:07,154 --> 00:36:08,070
ANDI彭：最后一点？

736
00:36:08,070 --> 00:36:12,070
听众：阵列-J等于阵列我。

737
00:36:12,070 --> 00:36:14,525
听众：或数组，j为
阵列temp--或温度。

738
00:36:14,525 --> 00:36:17,135

739
00:36:17,135 --> 00:36:19,430
>> ANDI彭：OK。

740
00:36:19,430 --> 00:36:21,510
因此，让我们运行这个，看看
如果它去上班。

741
00:36:21,510 --> 00:36:37,520

742
00:36:37,520 --> 00:36:39,335
哪里是怎么回事？

743
00:36:39,335 --> 00:36:40,210
哦，这是一个问题。

744
00:36:40,210 --> 00:36:44,320
见，第40行，我们
尝试使用数组-J？

745
00:36:44,320 --> 00:36:47,022
但是，在没有Ĵ只存在吗？

746
00:36:47,022 --> 00:36:48,402
>> 听众：在for循环。

747
00:36:48,402 --> 00:36:49,110
ANDI彭：对。

748
00:36:49,110 --> 00:36:51,730
那么，我们将需要做什么？

749
00:36:51,730 --> 00:36:53,170
>> 听众：外the--将其定义

750
00:36:53,170 --> 00:36:57,777

751
00:36:57,777 --> 00:37:00,610
听众：是的，我想你
if语句，使用权的另一个？

752
00:37:00,610 --> 00:37:05,230
所以像，如果minimum--
好吧，让我想想。

753
00:37:05,230 --> 00:37:08,170

754
00:37:08,170 --> 00:37:09,990
>> ANDI彭：伙计们，试试
看看咱们的

755
00:37:09,990 --> 00:37:11,270
看看，什么的东西，我们可以在这里做什么？

756
00:37:11,270 --> 00:37:11,811
>> 听众：OK。

757
00:37:11,811 --> 00:37:15,900
因此，如果最低不等于
j--所以如果最小仍然I--

758
00:37:15,900 --> 00:37:17,570
那么我们就不会掉。

759
00:37:17,570 --> 00:37:22,450

760
00:37:22,450 --> 00:37:24,712
>> ANDI彭：这是否等于我？

761
00:37:24,712 --> 00:37:25,920
你怎么在这里想说的？

762
00:37:25,920 --> 00:37:30,494
>> 听众：或者是啊，如果
最低不等于我，是的。

763
00:37:30,494 --> 00:37:39,627

764
00:37:39,627 --> 00:37:40,210
ANDI彭：OK。

765
00:37:40,210 --> 00:37:42,040
好了，解决了，那种，我们的问题。

766
00:37:42,040 --> 00:37:47,265
但是，这仍然没有解决
如果j--发生，因为Ĵ哪些问题

767
00:37:47,265 --> 00:37:49,890
外面它不存在，什么
你，我们想用它做？

768
00:37:49,890 --> 00:37:50,698
外部声明呢？

769
00:37:50,698 --> 00:37:59,410

770
00:37:59,410 --> 00:38:02,730
让我们尝试运行此。

771
00:38:02,730 --> 00:38:04,435
嗯，哦。

772
00:38:04,435 --> 00:38:06,200
我们的排序不工作。

773
00:38:06,200 --> 00:38:10,060
>> 正如你所看到的，我们最初的
数组有这些值。

774
00:38:10,060 --> 00:38:14,800
事后它应该有
一直在1，2，3，4，5，6，7，8，9。

775
00:38:14,800 --> 00:38:15,530
它不工作。

776
00:38:15,530 --> 00:38:16,030
啊。

777
00:38:16,030 --> 00:38:17,184
我们做什么？

778
00:38:17,184 --> 00:38:17,850
听众：调试。

779
00:38:17,850 --> 00:38:21,787

780
00:38:21,787 --> 00:38:23,370
ANDI鹏：好的，我们可以试试。

781
00:38:23,370 --> 00:38:25,030
我们可以调试。

782
00:38:25,030 --> 00:38:26,042
缩小了一点。

783
00:38:26,042 --> 00:38:31,177

784
00:38:31,177 --> 00:38:33,656
让我们设置的断点。

785
00:38:33,656 --> 00:38:37,280
让我们去like--确定。

786
00:38:37,280 --> 00:38:40,444
>> 所以，因为我们已经知道，
这些线路，15至22，

787
00:38:40,444 --> 00:38:43,610
在working--因为我做的是
通过与printing--只是迭代

788
00:38:43,610 --> 00:38:45,406
我可以继续跳过。

789
00:38:45,406 --> 00:38:47,280
让我们从第25行。

790
00:38:47,280 --> 00:38:48,712
空中接力，让我摆脱这一点。

791
00:38:48,712 --> 00:38:51,598

792
00:38:51,598 --> 00:38:54,057
>> 听众：所以断点的
其中，调试开始？

793
00:38:54,057 --> 00:38:54,890
ANDI彭：或停止。

794
00:38:54,890 --> 00:38:55,670
听众：或停止。

795
00:38:55,670 --> 00:38:55,930
ANDI彭：是的。

796
00:38:55,930 --> 00:38:58,640
您可以设置多个断点和
它可以只从一个到另一个跳。

797
00:38:58,640 --> 00:39:01,590
但是，在这种情况下，我们不知道
那里的错误发生。

798
00:39:01,590 --> 00:39:03,780
所以，我们只是想
从上向下展开。

799
00:39:03,780 --> 00:39:05,020
是的。

800
00:39:05,020 --> 00:39:05,550
好。

801
00:39:05,550 --> 00:39:08,460
>> 因此，这条线在这里，我们可以介入。

802
00:39:08,460 --> 00:39:11,499
你可以看到这儿，
我们已经有了一个数组。

803
00:39:11,499 --> 00:39:13,290
这些都是价值
是阵列中。

804
00:39:13,290 --> 00:39:16,360
你看到了，怎么指数为0，
对应于value--哦，

805
00:39:16,360 --> 00:39:17,526
我要去尝试进行放大。

806
00:39:17,526 --> 00:39:20,650
对不起，这真的很难
以see--数组索引0，

807
00:39:20,650 --> 00:39:24,090
我们有4的值，
然后依此类推等等。

808
00:39:24,090 --> 00:39:25,670
我们有自己的局部变量。

809
00:39:25,670 --> 00:39:28,570
现在我等于
0，这是我们希望它是。

810
00:39:28,570 --> 00:39:31,540

811
00:39:31,540 --> 00:39:33,690
>> 因此，让我们继续单步调试。

812
00:39:33,690 --> 00:39:36,850
我们的最低等于0，
我们也希望它是。

813
00:39:36,850 --> 00:39:39,470

814
00:39:39,470 --> 00:39:45,560
然后，我们进入我们的第二个用于
环，如果阵列-j是小于阵列-i的，

815
00:39:45,560 --> 00:39:46,380
它不是。

816
00:39:46,380 --> 00:39:48,130
所以，你怎么看
即跳过了吗？

817
00:39:48,130 --> 00:39:52,430
>> 听众：所以要把如果
最低，所有that--不应该的

818
00:39:52,430 --> 00:39:55,424
在里面的第一个for循环？

819
00:39:55,424 --> 00:39:57,340
ANDI彭：没有，因为
你还是想测试。

820
00:39:57,340 --> 00:40:00,329
你想要做一个比较每
时间，即使你通过它运行。

821
00:40:00,329 --> 00:40:02,620
你不只是想这样做
在第一通过。

822
00:40:02,620 --> 00:40:05,240
你想做到这一点的
再每增加一个通行证。

823
00:40:05,240 --> 00:40:07,198
所以，你要检查
你的病情里面。

824
00:40:07,198 --> 00:40:11,610

825
00:40:11,610 --> 00:40:13,746
所以，我们只是要
让经过这里运行。

826
00:40:13,746 --> 00:40:17,337

827
00:40:17,337 --> 00:40:18,420
我给你们一个提示。

828
00:40:18,420 --> 00:40:23,910
它必须做的事实是，当
你检查你的条件，

829
00:40:23,910 --> 00:40:26,600
你不检查
正确的索引。

830
00:40:26,600 --> 00:40:32,510
所以现在你检查
歼数组索引小于阵列

831
00:40:32,510 --> 00:40:33,970
我索引。

832
00:40:33,970 --> 00:40:36,580
但是，你在做什么了，在
for循环的开始？

833
00:40:36,580 --> 00:40:38,260
难道你不设置Ĵ等于我？

834
00:40:38,260 --> 00:40:41,260

835
00:40:41,260 --> 00:40:45,415
>> 是啊，所以我们实际上可以
退出调试器在这里。

836
00:40:45,415 --> 00:40:47,040
因此，让我们来看看我们的伪代码。

837
00:40:47,040 --> 00:40:50,070

838
00:40:50,070 --> 00:40:52,580
For--我们要
开始我等于0。

839
00:40:52,580 --> 00:40:54,760
我们要上浮到n减去1。

840
00:40:54,760 --> 00:40:58,040
让我们来看看，没我们有这个权利？

841
00:40:58,040 --> 00:40:59,580
是的，这是正确的。

842
00:40:59,580 --> 00:41:02,080
>> 因此，然后在里面在这里，我们
要创建一个最小值

843
00:41:02,080 --> 00:41:03,630
并设置等于i。

844
00:41:03,630 --> 00:41:04,950
难道我们这样做吗？

845
00:41:04,950 --> 00:41:06,270
是的，这样做。

846
00:41:06,270 --> 00:41:10,430
现在，在我们内心的for循环中，我们
要做到j为我到n减去1。

847
00:41:10,430 --> 00:41:11,950
难道我们这样做吗？

848
00:41:11,950 --> 00:41:15,540
事实上，我们做到了。

849
00:41:15,540 --> 00:41:19,922
>> 所以，不管，什么是我们比较吗？

850
00:41:19,922 --> 00:41:20,925
>> 听众：J-加1。

851
00:41:20,925 --> 00:41:21,716
ANDI鹏：没错。

852
00:41:21,716 --> 00:41:24,184

853
00:41:24,184 --> 00:41:27,350
然后你会想设置
您的最低等于到j加1为好。

854
00:41:27,350 --> 00:41:31,057

855
00:41:31,057 --> 00:41:32,640
所以，我通过真的很快去了。

856
00:41:32,640 --> 00:41:36,190
难道你们明白
为什么它的歼加1？

857
00:41:36,190 --> 00:41:36,890
好。

858
00:41:36,890 --> 00:41:40,700
>> 因此，在你的阵列，在
你的第一个闯关，

859
00:41:40,700 --> 00:41:44,850
你的for循环，对于int
i等于0，我们只

860
00:41:44,850 --> 00:41:46,740
假设这并没有改变呢。

861
00:41:46,740 --> 00:41:53,180

862
00:41:53,180 --> 00:41:56,760
我们的阵列，完全，
短短四年未排序的元素，对不对？

863
00:41:56,760 --> 00:42:00,760
因此，我们要初始化i等于0。

864
00:42:00,760 --> 00:42:03,650
而我是要只
通过这个循环运行。

865
00:42:03,650 --> 00:42:08,560
因此在第一轮，我们要
初始化一个名为“分”变

866
00:42:08,560 --> 00:42:11,245
这也等于我，因为
我们没有一个最小值。

867
00:42:11,245 --> 00:42:12,870
所以这是当前等于0为好。

868
00:42:12,870 --> 00:42:16,182

869
00:42:16,182 --> 00:42:17,640
然后，我们将经历。

870
00:42:17,640 --> 00:42:19,270
我们想再次重复。

871
00:42:19,270 --> 00:42:22,900
现在我们已经找到了我们的最低
是，我们要遍历

872
00:42:22,900 --> 00:42:25,190
再看看它的比较，对不对？

873
00:42:25,190 --> 00:42:40,440
所以Ĵ，在这里，是怎么回事
等于I，这是0。

874
00:42:40,440 --> 00:42:46,320
然后，如果阵列Ĵ再加上我，这
就是一个是下完了，一样都不能少

875
00:42:46,320 --> 00:42:49,270
比你目前的最低
值，要交换。

876
00:42:49,270 --> 00:42:56,850
>> 所以，让我们只说我们已经
有，像，2，5，1，8。

877
00:42:56,850 --> 00:43:01,610
现在，我等于
0和j是等于0。

878
00:43:01,610 --> 00:43:05,210
这就是我们的最低值。

879
00:43:05,210 --> 00:43:09,950
如果阵列-j的加I--因此如果所述一个
这就是我们正在寻找在一前一后

880
00:43:09,950 --> 00:43:13,450
大于前一，
这将成为最低。

881
00:43:13,450 --> 00:43:18,120
>> 所以在这里我们可以看到，5
是不逊色。

882
00:43:18,120 --> 00:43:19,730
因此，这将不会是5。

883
00:43:19,730 --> 00:43:23,580
我们看到，1小于2，对不对？

884
00:43:23,580 --> 00:43:32,970
所以，现在我们知道，我们的最低是
将是0，1，2的指数值。

885
00:43:32,970 --> 00:43:34,030
是吗？

886
00:43:34,030 --> 00:43:39,170
然后当你到这里，
你可以交换正确的价值观。

887
00:43:39,170 --> 00:43:42,610
>> 所以，当你们刚刚有第j
之前，你是不是在看一

888
00:43:42,610 --> 00:43:43,260
后。

889
00:43:43,260 --> 00:43:44,520
你在看
相同的值，这

890
00:43:44,520 --> 00:43:46,290
就是为什么它只是没有做任何事情。

891
00:43:46,290 --> 00:43:49,721
这是否有意义给大家，
为什么我们需要一个加1呢？

892
00:43:49,721 --> 00:43:50,220
好。

893
00:43:50,220 --> 00:43:53,345
现在，让我们只运行通过它来作
确认代码的其余部分是正确的。

894
00:43:53,345 --> 00:44:04,424

895
00:44:04,424 --> 00:44:05,340
这是为什么发生？

896
00:44:05,340 --> 00:44:14,780

897
00:44:14,780 --> 00:44:16,364
啊，这是分就在这里。

898
00:44:16,364 --> 00:44:17,780
我们比较了错误的值。

899
00:44:17,780 --> 00:44:24,944

900
00:44:24,944 --> 00:44:25,906
不好了。

901
00:44:25,906 --> 00:44:30,720

902
00:44:30,720 --> 00:44:33,482
>> 哦，是的，在这儿我们
交换了错误的值也是如此。

903
00:44:33,482 --> 00:44:34,940
因为我们在看i和j。

904
00:44:34,940 --> 00:44:36,440
这些都是那些我们被检查。

905
00:44:36,440 --> 00:44:39,160
事实上，我们希望交换的
至少，目前最低，

906
00:44:39,160 --> 00:44:40,550
与任何一个外面。

907
00:44:40,550 --> 00:44:59,510

908
00:44:59,510 --> 00:45:05,402
正如你们所看到下跌
在这里，我们有一个排序的数组。

909
00:45:05,402 --> 00:45:07,110
这只是不得不做
事实，当

910
00:45:07,110 --> 00:45:09,350
我们被检查
值的我们相比，

911
00:45:09,350 --> 00:45:11,226
我们不看正确的价值观。

912
00:45:11,226 --> 00:45:13,850
我们在看的同一个
在这里，没有实际交换它。

913
00:45:13,850 --> 00:45:17,135
你要看看一个接一个
它，然后你可以交换。

914
00:45:17,135 --> 00:45:19,260
所以，这是什么样的
前缠着我们的代码。

915
00:45:19,260 --> 00:45:22,460
而我在这里所做的一切
调试器可以为你做

916
00:45:22,460 --> 00:45:23,810
我只是做了它的
板，因为它更容易

917
00:45:23,810 --> 00:45:26,320
看而不是试图
可放大的调试器。

918
00:45:26,320 --> 00:45:29,391
这是否有意义给大家？

919
00:45:29,391 --> 00:45:29,890
酷。

920
00:45:29,890 --> 00:45:34,800

921
00:45:34,800 --> 00:45:35,410
>> 好吧。

922
00:45:35,410 --> 00:45:41,070
我们可以继续谈
渐近符号，这

923
00:45:41,070 --> 00:45:44,580
是说的只是一种奇特的方式
所有这些各种各样的运行时间。

924
00:45:44,580 --> 00:45:47,650
所以我知道大卫在演讲中，
在运行时感动。

925
00:45:47,650 --> 00:45:52,124
他走遍了整个公式
如何计算的运行时。

926
00:45:52,124 --> 00:45:53,040
关于无后顾之忧。

927
00:45:53,040 --> 00:45:54,660
如果你真的很好奇
其工作原理，

928
00:45:54,660 --> 00:45:55,810
随时节后跟我说话。

929
00:45:55,810 --> 00:45:57,560
我们可以穿行
公式在一起。

930
00:45:57,560 --> 00:46:00,689
但是，所有你们要真
知道是n的平方超过2

931
00:46:00,689 --> 00:46:01,980
是同样的事情为N的平方。

932
00:46:01,980 --> 00:46:04,710
因为最大数目，
该指数增长最。

933
00:46:04,710 --> 00:46:06,590
所以我们的目的，
我们关心的

934
00:46:06,590 --> 00:46:09,470
是巨大的数量也在不断增长。

935
00:46:09,470 --> 00:46:13,340
>> 那么，什么是最好的情况下，
选择排序的运行时间？

936
00:46:13,340 --> 00:46:15,830
如果你想有
遍历列表

937
00:46:15,830 --> 00:46:18,712
然后遍历
该列表的其余部分，

938
00:46:18,712 --> 00:46:20,420
多少次都
你要大概，

939
00:46:20,420 --> 00:46:24,612
在最坏的case--在
最好的情况下，sorry--跑过来吗？

940
00:46:24,612 --> 00:46:27,070
也许更好的问题是
要问，什么是最坏的情况下

941
00:46:27,070 --> 00:46:28,153
运行时选择排序的。

942
00:46:28,153 --> 00:46:29,366
听众：N的平方。

943
00:46:29,366 --> 00:46:30,740
ANDI彭：这n值的平方，正确的。

944
00:46:30,740 --> 00:46:36,986
因此，一个简单的方法来认为这是喜欢，
任何时候你有两个嵌套的for循环，

945
00:46:36,986 --> 00:46:38,110
它会为n的平方。

946
00:46:38,110 --> 00:46:40,386
因为不仅是你
通过再次运行，

947
00:46:40,386 --> 00:46:42,260
你要回去
周围，​​并通过它运行

948
00:46:42,260 --> 00:46:44,980
里面的每一个值一次。

949
00:46:44,980 --> 00:46:48,640
因此，在这种情况下，你在行驶中N
n次平方，这is--抱歉，

950
00:46:48,640 --> 00:46:50,505
n次N，这等于N的平方。

951
00:46:50,505 --> 00:46:53,230

952
00:46:53,230 --> 00:46:56,360
>> 和排序也有点
在这个意义上独特

953
00:46:56,360 --> 00:46:59,774
它不如果这些关系
值已经在秩序。

954
00:46:59,774 --> 00:47:01,440
它仍然会通过反正运行。

955
00:47:01,440 --> 00:47:03,872
远的不说，这是1，2，3，4。

956
00:47:03,872 --> 00:47:07,080
不管它是否是在
命令，它仍然会通过跑

957
00:47:07,080 --> 00:47:08,620
并且仍然检查的最小值。

958
00:47:08,620 --> 00:47:10,100
它会作出
检查相同数量的

959
00:47:10,100 --> 00:47:12,780
每一次，即使它
实际上并没有碰任何东西。

960
00:47:12,780 --> 00:47:16,940
>> 因此，在这样的情况下，最好和最差
运行时实际上是等价的。

961
00:47:16,940 --> 00:47:19,160
因此，预计运行时间
选择排序的，

962
00:47:19,160 --> 00:47:23,790
这是我们指定的符号
的θ，θ-，在这种情况下，

963
00:47:23,790 --> 00:47:24,790
还将为n的平方。

964
00:47:24,790 --> 00:47:26,480
所有这三个为N的平方。

965
00:47:26,480 --> 00:47:29,653
是为什么每个人都清楚
运行时间为n的平方？

966
00:47:29,653 --> 00:47:33,360

967
00:47:33,360 --> 00:47:33,980
>> 好吧。

968
00:47:33,980 --> 00:47:39,120
所以我只是要快速运行
通过对各种休息。

969
00:47:39,120 --> 00:47:41,137
该算法
泡泡类别 - 记住，

970
00:47:41,137 --> 00:47:43,220
这是第一个
大卫走过去的讲座。

971
00:47:43,220 --> 00:47:46,000
从本质上讲，你一步
整个列表

972
00:47:46,000 --> 00:47:48,950
你刚才swap--你
同时比较两个。

973
00:47:48,950 --> 00:47:51,350
而如果一个人的更大，
比你只是换他们。

974
00:47:51,350 --> 00:47:53,590
因此，如果这些是更大的，你就掉。

975
00:47:53,590 --> 00:47:56,180
我已经得到了官方的就在这里。

976
00:47:56,180 --> 00:47:59,100
>> 因此，让我们只说你有8个，6个，4个，2。

977
00:47:59,100 --> 00:48:00,571
你会比较8和6。

978
00:48:00,571 --> 00:48:01,570
你需要交换它们。

979
00:48:01,570 --> 00:48:02,610
您会比较8和4。

980
00:48:02,610 --> 00:48:03,609
你需要交换它们。

981
00:48:03,609 --> 00:48:07,000
如果您有交换8
2，改变他们。

982
00:48:07,000 --> 00:48:10,760
因此，在这样的意义上，你可以看到，
发挥出了相当长的时间周期，

983
00:48:10,760 --> 00:48:13,730
怎么样值泡沫来
两端，这就是为什么我们叫它

984
00:48:13,730 --> 00:48:15,320
冒泡排序。

985
00:48:15,320 --> 00:48:19,950
>> 我们只想上运行再次通过
我们的二传，而我们的第三关，

986
00:48:19,950 --> 00:48:21,150
而我们的第四个阶段。

987
00:48:21,150 --> 00:48:25,820
从本质上讲，冒泡排序只是运行
直到你不作任何更多的互换。

988
00:48:25,820 --> 00:48:31,109
因此，在这个意义上，这仅仅是
一般伪它。

989
00:48:31,109 --> 00:48:32,650
不用担心，这些都将在网上。

990
00:48:32,650 --> 00:48:34,990
我们没有真正去了这一点。

991
00:48:34,990 --> 00:48:38,134
>> 我们只是初始化一个计数器
从0开始的变量。

992
00:48:38,134 --> 00:48:39,800
而我们通过整个数组迭代。

993
00:48:39,800 --> 00:48:43,420
如果一个值is--如果这
值大于该值，

994
00:48:43,420 --> 00:48:44,610
你要交换它们。

995
00:48:44,610 --> 00:48:46,860
然后，你只是
要继续下去。

996
00:48:46,860 --> 00:48:47,970
而你要算。

997
00:48:47,970 --> 00:48:50,845
而你只是要继续做
这同时计数器的值大

998
00:48:50,845 --> 00:48:53,345
大于0，这意味着
每次你要交换，

999
00:48:53,345 --> 00:48:55,220
你知道你想要去
回去检查一次。

1000
00:48:55,220 --> 00:48:59,510
你要继续检查，直到你知道
你不必换了。

1001
00:48:59,510 --> 00:49:05,570
>> 那么，什么是最好的和最差
情况下的运行时间冒泡排序？

1002
00:49:05,570 --> 00:49:09,300
这hint--实际上是不同的
从某种意义上选择排序

1003
00:49:09,300 --> 00:49:11,810
这两个答案是不一样的。

1004
00:49:11,810 --> 00:49:14,709
想想会发生什么
的情况下，如果它已经被排序。

1005
00:49:14,709 --> 00:49:16,500
想想什么
如果它是会发生

1006
00:49:16,500 --> 00:49:18,372
在的情况下在它被排序。

1007
00:49:18,372 --> 00:49:20,580
你可以种运行
通过为什么会发生的事情。

1008
00:49:20,580 --> 00:49:22,954
我给你们一样，30
秒，想想。

1009
00:49:22,954 --> 00:49:52,330

1010
00:49:52,330 --> 00:49:53,540
>> 好。

1011
00:49:53,540 --> 00:49:57,462
是否有人在猜测什么
冒泡排序的最坏情况下的运行时间是？

1012
00:49:57,462 --> 00:49:57,962
是啊。

1013
00:49:57,962 --> 00:50:07,810
>> 听众：会是一样，n次
ñ减1或类似的东西？

1014
00:50:07,810 --> 00:50:10,650
像，每次运行时，
它只是一样，一个交换少

1015
00:50:10,650 --> 00:50:10,960
这不管是什么。

1016
00:50:10,960 --> 00:50:12,668
>> ANDI彭：是啊，所以
你是完全正确的。

1017
00:50:12,668 --> 00:50:15,940
这是在这种情况下你
答案竟是更复杂

1018
00:50:15,940 --> 00:50:17,240
比我们需要给。

1019
00:50:17,240 --> 00:50:19,772
因此，这将run--我
要删除这一切都在这里。

1020
00:50:19,772 --> 00:50:20,480
是每个人都好？

1021
00:50:20,480 --> 00:50:21,869
我能抹去吗？

1022
00:50:21,869 --> 00:50:22,368
好。

1023
00:50:22,368 --> 00:50:27,904

1024
00:50:27,904 --> 00:50:30,320
你会到n运行
第一次时间，对吧？

1025
00:50:30,320 --> 00:50:33,200
他们正在经历的运行
Ñ​​减去1秒的时间，对吧？

1026
00:50:33,200 --> 00:50:37,130
然后，你要保持
去，N矿2，等等。

1027
00:50:37,130 --> 00:50:40,210
大卫这样做的讲座，其中，
如果你加起来所有的值，

1028
00:50:40,210 --> 00:50:48,080
你得到的东西，是like-- yeah--
超过2，这本质上只是减少

1029
00:50:48,080 --> 00:50:49,784
下降到n的平方。

1030
00:50:49,784 --> 00:50:51,700
你会得到一个
怪异的部分在里面。

1031
00:50:51,700 --> 00:50:53,892
所以只要知道
第n总是平方

1032
00:50:53,892 --> 00:50:55,350
优先于分数。

1033
00:50:55,350 --> 00:50:58,450
因此在这种情况下，最坏的
运行时间为N的平方。

1034
00:50:58,450 --> 00:51:00,210
如果它是在降
顺序，想想，你

1035
00:51:00,210 --> 00:51:02,530
不得不做出交换每一次。

1036
00:51:02,530 --> 00:51:05,170
>> 什么是潜在的，
最好的情况下运行？

1037
00:51:05,170 --> 00:51:08,580
这么说吧，如果列表已经
为了，你会在运行时？

1038
00:51:08,580 --> 00:51:09,565
>> 听众：N。

1039
00:51:09,565 --> 00:51:10,690
ANDI彭：这是N，正好。

1040
00:51:10,690 --> 00:51:11,600
为什么是这N +

1041
00:51:11,600 --> 00:51:13,850
听众：因为你刚才
必须检查每一次。

1042
00:51:13,850 --> 00:51:14,770
ANDI鹏：没错。

1043
00:51:14,770 --> 00:51:17,150
因此，在可能的最佳运行时，
如果此列表中已经

1044
00:51:17,150 --> 00:51:20,270
sorted--比方说，1，2，3，4--您
只想去实现它，你会检查，

1045
00:51:20,270 --> 00:51:21,720
你会看到，哦，他们都做成。

1046
00:51:21,720 --> 00:51:22,636
我没得换。

1047
00:51:22,636 --> 00:51:23,370
我受够了。

1048
00:51:23,370 --> 00:51:26,500
因此，在这种情况下，它仅仅局限于N
或步数，你只是

1049
00:51:26,500 --> 00:51:29,870
不得不检查的第一个列表。

1050
00:51:29,870 --> 00:51:33,990
>> 及后，我们现在打
插入排序，其中，

1051
00:51:33,990 --> 00:51:39,260
该算法本质上是鸿沟
它变成一个排序和未排序的部分。

1052
00:51:39,260 --> 00:51:42,810
然后一个接一个，
未排序值

1053
00:51:42,810 --> 00:51:46,880
在其相应插
在列表的开头位置。

1054
00:51:46,880 --> 00:51:52,120
>> 因此，例如，我们有一个
的3名单，5,2，6,4试。

1055
00:51:52,120 --> 00:51:54,750
我们知道，这是目前
未分类的，因为我们刚刚

1056
00:51:54,750 --> 00:51:57,030
开始寻找它。

1057
00:51:57,030 --> 00:52:00,610
我们来看看，我们知道，
第一个值进行排序，对吧？

1058
00:52:00,610 --> 00:52:04,190
如果你只关注一个数组
尺寸之一，你知道它的排序。

1059
00:52:04,190 --> 00:52:08,230
>> 于是我们知道，
其他四个都是无序。

1060
00:52:08,230 --> 00:52:10,980
我们通过和我们看到的价值。

1061
00:52:10,980 --> 00:52:11,730
我们回去吧。

1062
00:52:11,730 --> 00:52:13,130
见5的价值？

1063
00:52:13,130 --> 00:52:14,110
我们来看看它。

1064
00:52:14,110 --> 00:52:15,204
我们把它比作3。

1065
00:52:15,204 --> 00:52:17,870
我们知道，它是大于
3，让我们知道，多数民​​众赞成排序。

1066
00:52:17,870 --> 00:52:22,940
所以，现在我们知道，前两个
进行排序和最后三个不是。

1067
00:52:22,940 --> 00:52:24,270
>> 我们来看看2。

1068
00:52:24,270 --> 00:52:25,720
我们首先检查一下与5。

1069
00:52:25,720 --> 00:52:26,700
是小于5？

1070
00:52:26,700 --> 00:52:27,240
它不是。

1071
00:52:27,240 --> 00:52:29,510
因此，我们必须继续找下去。

1072
00:52:29,510 --> 00:52:30,940
然后检查2关闭3。

1073
00:52:30,940 --> 00:52:31,850
是小于？

1074
00:52:31,850 --> 00:52:32,350
第

1075
00:52:32,350 --> 00:52:35,430
所以，你知道2必须插入
入前和3和5

1076
00:52:35,430 --> 00:52:38,200
都必须被推出。

1077
00:52:38,200 --> 00:52:42,190
6和4再次做到这一点。

1078
00:52:42,190 --> 00:52:48,962
我们只是保持检查从本质上讲，
在这里我们只是检查，检查，检查。

1079
00:52:48,962 --> 00:52:51,170
而直到它在正确的
样的位置，我们只是

1080
00:52:51,170 --> 00:52:54,890
将其插入合适的位置，
这就是它的名字是从哪里来的。

1081
00:52:54,890 --> 00:52:59,830
>> 所以，这仅仅是算法，
那种伪代码本身，

1082
00:52:59,830 --> 00:53:04,990
关于我们如何实现
插入排序。

1083
00:53:04,990 --> 00:53:05,954
伪代码是在这里。

1084
00:53:05,954 --> 00:53:06,620
这一切都在网上。

1085
00:53:06,620 --> 00:53:10,720
不，如果你们有隐忧
试图复制下来。

1086
00:53:10,720 --> 00:53:14,500
所以再次，相同的问题 - 是什么
将是最好的和最差的运行时间

1087
00:53:14,500 --> 00:53:16,120
插入排序？

1088
00:53:16,120 --> 00:53:17,750
这是非常相似的最后一个问题。

1089
00:53:17,750 --> 00:53:20,479
我给你们一样，30
秒想想这一点。

1090
00:53:20,479 --> 00:53:47,150

1091
00:53:47,150 --> 00:53:50,071
>> 确定有没有人要
给我最糟糕的运行？

1092
00:53:50,071 --> 00:53:50,570
是啊。

1093
00:53:50,570 --> 00:53:51,490
>> 听众：N的平方。

1094
00:53:51,490 --> 00:53:52,573
>> ANDI彭：这n值的平方。

1095
00:53:52,573 --> 00:53:53,730
为什么它Ñ平方？

1096
00:53:53,730 --> 00:53:57,562
>> 听众：因为在
相反的顺序，你有

1097
00:53:57,562 --> 00:54:02,619
要经过n次N，其中is--

1098
00:54:02,619 --> 00:54:03,660
ANDI彭：是的，没错。

1099
00:54:03,660 --> 00:54:06,610
所以，同样的事情在冒泡排序。

1100
00:54:06,610 --> 00:54:08,720
如果此列表中
降序排列，你

1101
00:54:08,720 --> 00:54:11,240
不得不先检查一次。

1102
00:54:11,240 --> 00:54:13,470
然后每
额外的价值，你

1103
00:54:13,470 --> 00:54:16,390
将不得不对检查
每一个值，对不对？

1104
00:54:16,390 --> 00:54:20,290
所以干脆，你会做
正通时代另外N通，这

1105
00:54:20,290 --> 00:54:21,750
为n的平方。

1106
00:54:21,750 --> 00:54:22,860
那么最好的情况？

1107
00:54:22,860 --> 00:54:24,360
是啊。

1108
00:54:24,360 --> 00:54:28,840
>> 听众：N减1，因为
第一个是已经平方。

1109
00:54:28,840 --> 00:54:30,270
>> ANDI彭：那么，关闭。

1110
00:54:30,270 --> 00:54:31,850
其实答案ñ。

1111
00:54:31,850 --> 00:54:37,189
因为当第一个是
排序，也可以不actually--它

1112
00:54:37,189 --> 00:54:38,980
我们只是走运了，在
即例如，2

1113
00:54:38,980 --> 00:54:40,930
正好是最小的数目。

1114
00:54:40,930 --> 00:54:43,680
但是，这不会总是这种情况。

1115
00:54:43,680 --> 00:54:48,040
如果2已经排序的开始
但是你看，有一个1在这里，

1116
00:54:48,040 --> 00:54:49,144
1将要碰撞。

1117
00:54:49,144 --> 00:54:51,060
而这将结束
最多被撞毁反正。

1118
00:54:51,060 --> 00:54:56,250
>> 因此，在最好的情况下，
它实际上只是要为n。

1119
00:54:56,250 --> 00:54:59,090
如果有1个，2个，3个，
4，5，6，7，8，你

1120
00:54:59,090 --> 00:55:00,940
经过运行
这整个列表一次

1121
00:55:00,940 --> 00:55:03,430
检查，如果一切都很好看。

1122
00:55:03,430 --> 00:55:07,390
在其上运行大家清楚
选择的时候呢？

1123
00:55:07,390 --> 00:55:09,960
我知道我经历
这些真快。

1124
00:55:09,960 --> 00:55:13,330
但是，仅仅知道，如果你知道
一般概念，您应该不错。

1125
00:55:13,330 --> 00:55:16,070
好。

1126
00:55:16,070 --> 00:55:19,790
所以，我只是给你们也许一样，
一分钟谈谈你的邻居

1127
00:55:19,790 --> 00:55:21,890
什么都只是一些
的主要区别

1128
00:55:21,890 --> 00:55:23,540
与这些类型的排序。

1129
00:55:23,540 --> 00:56:24,571

1130
00:56:24,571 --> 00:56:25,570
我们一起去了很快。

1131
00:56:25,570 --> 00:56:26,444
听众：哦，好。

1132
00:56:26,444 --> 00:56:27,320
ANDI彭：是的。

1133
00:56:27,320 --> 00:56:28,380
好。

1134
00:56:28,380 --> 00:56:33,420
酷，让我们重新召集的一类。

1135
00:56:33,420 --> 00:56:34,330
好。

1136
00:56:34,330 --> 00:56:37,579
所以，这是一种一
在这个意义上开放式的问题

1137
00:56:37,579 --> 00:56:39,120
这有很多他们的答案的。

1138
00:56:39,120 --> 00:56:40,746
我们将介绍一些他们的简要介绍。

1139
00:56:40,746 --> 00:56:43,411
我只想让你们
思考什么区别

1140
00:56:43,411 --> 00:56:44,530
这三种类型的排序。

1141
00:56:44,530 --> 00:56:47,440
而且我听说，也有很大
的问题 - 是什么归并排序呢？

1142
00:56:47,440 --> 00:56:50,110
大的问题，因为这是
我们正在覆盖下一个。

1143
00:56:50,110 --> 00:56:52,850
>> 所以，归并排序是
一个分类的功能

1144
00:56:52,850 --> 00:56:56,100
非常不同于其他种类。

1145
00:56:56,100 --> 00:56:58,180
正如你们可以see--
David是不是做演示

1146
00:56:58,180 --> 00:57:01,130
在那里，他把所有的酷
看到如何合并的声音

1147
00:57:01,130 --> 00:57:04,010
排序跑了一样，无限
比其他两种类型的快？

1148
00:57:04,010 --> 00:57:04,510
好。

1149
00:57:04,510 --> 00:57:07,580
所以，这是因为合并
排序实现了鸿沟

1150
00:57:07,580 --> 00:57:11,020
而治之的概念，我们已经
谈到了很多在课堂上。

1151
00:57:11,020 --> 00:57:14,550
在这个意义上，我们喜欢的工作
更聪明，而不是更辛苦，当你把

1152
00:57:14,550 --> 00:57:18,120
而治之的问题，并打破他们
下来，然后把它们放在一起，

1153
00:57:18,120 --> 00:57:19,930
美好的事物总是发生。

1154
00:57:19,930 --> 00:57:21,960
>> 这样合并的方式
排序基本工作原理

1155
00:57:21,960 --> 00:57:24,660
是，它把一个
无序阵列中的一半。

1156
00:57:24,660 --> 00:57:26,500
然后它有阵列的两半。

1157
00:57:26,500 --> 00:57:28,220
它只是排序那些两半。

1158
00:57:28,220 --> 00:57:31,750
它只是保持在半分，在
一半，一半，直到万事俱备

1159
00:57:31,750 --> 00:57:33,680
然后递归
把他们放在一起。

1160
00:57:33,680 --> 00:57:36,550
>> 这就是真正的抽象。

1161
00:57:36,550 --> 00:57:38,750
所以，这只是一个有点伪的。

1162
00:57:38,750 --> 00:57:41,040
这是否有意义的
它的运行方式？

1163
00:57:41,040 --> 00:57:43,870
因此，让我们只说你有一个
n个元素的数组，对不对？

1164
00:57:43,870 --> 00:57:45,450
如果n小于2，可以退货。

1165
00:57:45,450 --> 00:57:49,040
因为你知道，如果有
只有一件事，它必须被排序。

1166
00:57:49,040 --> 00:57:52,600
否则，你排序左前卫，
然后排序的右半​​部分，

1167
00:57:52,600 --> 00:57:54,140
然后合并。

1168
00:57:54,140 --> 00:57:56,979
>> 因此，虽然看起来很容易，
在现实中，思考它的

1169
00:57:56,979 --> 00:58:00,270
样的困难。因为你喜欢，
嗯，这是运行的一种自身。

1170
00:58:00,270 --> 00:58:00,769
对？

1171
00:58:00,769 --> 00:58:02,430
它本身运行。

1172
00:58:02,430 --> 00:58:05,479
因此，在这个意义上，大卫·感动
在递归类。

1173
00:58:05,479 --> 00:58:07,270
这是一个概念
我们将谈论更多。

1174
00:58:07,270 --> 00:58:11,430
那就是这一点，这两条线
在这里，其实只是节目

1175
00:58:11,430 --> 00:58:13,860
告诉它运行本身
与不同的输入。

1176
00:58:13,860 --> 00:58:17,230
因此，而不是与运行本身
n个元素的全部，

1177
00:58:17,230 --> 00:58:20,530
你可以把它分解成的
左半部和右半

1178
00:58:20,530 --> 00:58:22,680
然后再运行它。

1179
00:58:22,680 --> 00:58:26,050
>> 然后我们来看看它在视觉上，
因为我是一个视觉学习者。

1180
00:58:26,050 --> 00:58:27,270
它为我好。

1181
00:58:27,270 --> 00:58:29,890
所以，我们来看看一个可视化的例子在这里。

1182
00:58:29,890 --> 00:58:36,237
>> 比方说，我们有一个数组，六
元素，3，5，2,6，4,1，不进行排序。

1183
00:58:36,237 --> 00:58:37,820
好吧，有很多这个页面上。

1184
00:58:37,820 --> 00:58:43,179
所以，如果你们可以看看
这里第一步骤中，3，5，2,6，4,1，

1185
00:58:43,179 --> 00:58:44,220
您可以在一半分裂它。

1186
00:58:44,220 --> 00:58:45,976
您有3个，5个，2，6,4，1。

1187
00:58:45,976 --> 00:58:48,850
你知道这些aren't--您
不知道他们正在排序或没有，

1188
00:58:48,850 --> 00:58:52,517
所以你把它们分解，在上半年，
成两半，一半，直至最后，

1189
00:58:52,517 --> 00:58:53,600
你只有一个元素。

1190
00:58:53,600 --> 00:58:56,790
而一个元素总是排序，对吧？

1191
00:58:56,790 --> 00:59:01,560
>> 因此，我们知道，3，5，2，4，6，
1，由本身，进行排序。

1192
00:59:01,560 --> 00:59:05,870
现在，我们可以把他们重新走到一起。

1193
00:59:05,870 --> 00:59:07,510
因此，我们知道的3,5。

1194
00:59:07,510 --> 00:59:08,510
我们把这些在一起。

1195
00:59:08,510 --> 00:59:09,617
我们知道这是排序。

1196
00:59:09,617 --> 00:59:10,450
2.仍然存在。

1197
00:59:10,450 --> 00:59:11,830
我们可以把4和6一起。

1198
00:59:11,830 --> 00:59:13,996
我们知道，多数民​​众赞成排序，
所以我们这身打扮。

1199
00:59:13,996 --> 00:59:14,940
而1是存在的。

1200
00:59:14,940 --> 00:59:18,720
>> 然后你只要看看
这两个半就在这里。

1201
00:59:18,720 --> 00:59:21,300
你有3,5，2，2，3，5。

1202
00:59:21,300 --> 00:59:23,465
你可以只比较
开始的一切。

1203
00:59:23,465 --> 00:59:26,340
因为你知道，这是排序
你知道，多数民​​众赞成排序。

1204
00:59:26,340 --> 00:59:29,360
所以，那么你甚至没有给
对比5，你只要比较一下3。

1205
00:59:29,360 --> 00:59:32,070
和2小于3，所以
你知道2必须走到底。

1206
00:59:32,070 --> 00:59:33,120
>> 同样的事情在那边。

1207
00:59:33,120 --> 00:59:34,740
1.必须在这里。

1208
00:59:34,740 --> 00:59:37,330
然后，当你去把
这两个值加在一起，

1209
00:59:37,330 --> 00:59:39,950
你知道，这是分类和
你知道这是排序。

1210
00:59:39,950 --> 00:59:43,240
于是在1和
图2中，1是小于2。

1211
00:59:43,240 --> 00:59:45,570
这告诉你，1
应该在本月底

1212
00:59:45,570 --> 00:59:47,480
看也不看3或5。

1213
00:59:47,480 --> 00:59:50,100
然后是4，你可以
检查，它会就在这里。

1214
00:59:50,100 --> 00:59:51,480
你不必看5。

1215
00:59:51,480 --> 00:59:52,570
同样的事情在6。

1216
00:59:52,570 --> 00:59:55,860
你知道6--它只是
并不需要研究。

1217
00:59:55,860 --> 00:59:57,870
>> 所以这样一来，你是
只是拯救自己

1218
00:59:57,870 --> 00:59:59,526
很多步骤，当你比较。

1219
00:59:59,526 --> 01:00:02,150
你不必比较每
元素与其他元素。

1220
01:00:02,150 --> 01:00:05,230
你只是比较反对的人
你需要将它与比较。

1221
01:00:05,230 --> 01:00:06,870
所以这是一种抽象的概念。

1222
01:00:06,870 --> 01:00:10,540
不用担心，如果它不是
相当击中你的权利呢。

1223
01:00:10,540 --> 01:00:14,740
但是总体来说，这是
如何合并排序工作。

1224
01:00:14,740 --> 01:00:17,750
问题，简单的问题，
之前，我继续前进？

1225
01:00:17,750 --> 01:00:18,550
是啊。

1226
01:00:18,550 --> 01:00:22,230
>> 听众：所以你说，你拿
1，然后在4和6

1227
01:00:22,230 --> 01:00:23,860
并把他们进来。

1228
01:00:23,860 --> 01:00:26,800
所以不those--不
你看他们

1229
01:00:26,800 --> 01:00:28,544
作为单独的元素，而不是整？

1230
01:00:28,544 --> 01:00:29,210
ANDI彭：是的。

1231
01:00:29,210 --> 01:00:32,020
所以发生了什么
是，你基本上

1232
01:00:32,020 --> 01:00:33,650
正在创造一个全新的阵列。

1233
01:00:33,650 --> 01:00:36,690
所以，你知道，在这里，我有
尺寸3的两个数组，对不对？

1234
01:00:36,690 --> 01:00:39,600
所以，你知道，我的排序的数组
需要有六个要素。

1235
01:00:39,600 --> 01:00:42,270
所以，你只要创建一个
新的内存量。

1236
01:00:42,270 --> 01:00:44,270
所以，你是那种喜欢
被浪费的存储器，

1237
01:00:44,270 --> 01:00:46,186
但是，这并不重要
因为它是如此之小。

1238
01:00:46,186 --> 01:00:48,590
所以，你看1
你看2。

1239
01:00:48,590 --> 01:00:50,770
而你知道，1小于2。

1240
01:00:50,770 --> 01:00:53,840
所以，你知道，1应该在
所有这些的开始。

1241
01:00:53,840 --> 01:00:55,850
>> 你甚至都不需要
看3和5。

1242
01:00:55,850 --> 01:00:57,400
所以，你知道1去那里。

1243
01:00:57,400 --> 01:00:59,300
然后，你基本上砍掉1。

1244
01:00:59,300 --> 01:01:00,370
这是一样，死了我们。

1245
01:01:00,370 --> 01:01:03,690
然后，我们只是有2个，
3，5，然后4和6。

1246
01:01:03,690 --> 01:01:06,270
然后你知道，你
比较4和2，

1247
01:01:06,270 --> 01:01:07,560
呵呵，2应该在那里。

1248
01:01:07,560 --> 01:01:09,685
所以，你扑通2下来，你砍了下来。

1249
01:01:09,685 --> 01:01:12,060
所以，那么你只需要3
和5中的4个和6个。

1250
01:01:12,060 --> 01:01:14,650
而你只是不断砍它关闭
直到你把他们到数组中。

1251
01:01:14,650 --> 01:01:17,110
>> 听众：所以，你只是总是
比较[听不清]？

1252
01:01:17,110 --> 01:01:17,710
>> ANDI鹏：没错。

1253
01:01:17,710 --> 01:01:19,590
因此，在这个意义上说，你是
只是相比较，从本质上讲，

1254
01:01:19,590 --> 01:01:21,240
一个号码对另一个号码。

1255
01:01:21,240 --> 01:01:22,990
而且因为你知道
，它的排序，

1256
01:01:22,990 --> 01:01:24,350
不必翻阅
所有的数值。

1257
01:01:24,350 --> 01:01:25,870
你只需要看看第一个。

1258
01:01:25,870 --> 01:01:27,582
然后你可以扑通
下来，因为你知道

1259
01:01:27,582 --> 01:01:29,640
他们属于他们需要属于。

1260
01:01:29,640 --> 01:01:31,030
是啊。

1261
01:01:31,030 --> 01:01:32,920
好问题。

1262
01:01:32,920 --> 01:01:35,290
>> 然后，如果哪
有点雄心勃勃，

1263
01:01:35,290 --> 01:01:38,660
随意看看这段代码。

1264
01:01:38,660 --> 01:01:40,680
这实际上是
物理实现

1265
01:01:40,680 --> 01:01:42,150
我们如何会写归并排序。

1266
01:01:42,150 --> 01:01:44,070
你可以看到，这是非常短的。

1267
01:01:44,070 --> 01:01:46,310
但背后的想法
这是相当复杂的。

1268
01:01:46,310 --> 01:01:50,865
所以，如果你觉得自己画了这一点
在你的功课今晚，随意。

1269
01:01:50,865 --> 01:01:54,050

1270
01:01:54,050 --> 01:01:54,740
>> 好。

1271
01:01:54,740 --> 01:01:58,070
大卫也去了这个讲座。

1272
01:01:58,070 --> 01:02:00,660
什么是最好的情况下，
运行时，最坏的情况下运行时，

1273
01:02:00,660 --> 01:02:05,680
和合并排序的预计运行时间？

1274
01:02:05,680 --> 01:02:07,260
几秒钟思考。

1275
01:02:07,260 --> 01:02:11,198
这是相当困难的，但那种
直观的，如果你仔细想想。

1276
01:02:11,198 --> 01:02:20,090

1277
01:02:20,090 --> 01:02:23,054
好吧。

1278
01:02:23,054 --> 01:02:25,269
>> 听众：是最坏的情况的n log N +

1279
01:02:25,269 --> 01:02:26,060
ANDI鹏：没错。

1280
01:02:26,060 --> 01:02:29,380
为什么说它是N日志ñ。

1281
01:02:29,380 --> 01:02:32,230
>> 听众：是不是因为它
成为指数更快，

1282
01:02:32,230 --> 01:02:35,390
因此它就像一个函数
而不只是单纯的为N

1283
01:02:35,390 --> 01:02:37,529
平方什么？

1284
01:02:37,529 --> 01:02:38,320
ANDI鹏：没错。

1285
01:02:38,320 --> 01:02:40,750
这样之所以
运行时在此为n日志

1286
01:02:40,750 --> 01:02:44,310
n是因为 - 你是什么人
在做所有这些步骤？

1287
01:02:44,310 --> 01:02:46,190
你只是砍了一半，对不对？

1288
01:02:46,190 --> 01:02:48,750
所以，当我们正在做的
日志，所有它做

1289
01:02:48,750 --> 01:02:53,150
被分割的问题在一半，
成两半，一半，在更半部。

1290
01:02:53,150 --> 01:02:56,430
而在这个意义上，可以种
对消除线性模型

1291
01:02:56,430 --> 01:02:57,510
我们一直在使用。

1292
01:02:57,510 --> 01:03:00,254
因为当你砍
事情的一半，这是一个记录。

1293
01:03:00,254 --> 01:03:02,420
这只是数学
代表它的方式。

1294
01:03:02,420 --> 01:03:06,310
>> 然后终于，到了最后，你
只是让通过一个最后一关

1295
01:03:06,310 --> 01:03:07,930
把所有的人都在秩序，对不对？

1296
01:03:07,930 --> 01:03:10,330
所以，如果你只需要
查一件事，那n值。

1297
01:03:10,330 --> 01:03:13,420
所以你是那种
乘两者结合起来。

1298
01:03:13,420 --> 01:03:17,660
因此，这就像你已经得到了最终的
检验N-下来日志的n这里

1299
01:03:17,660 --> 01:03:18,390
上面这儿。

1300
01:03:18,390 --> 01:03:21,060
如果你乘
他们，那是N日志ñ。

1301
01:03:21,060 --> 01:03:26,100
>> 所以，最好的和最坏
情况和预期是所有N日志N。

1302
01:03:26,100 --> 01:03:27,943
它也像另一个排序。

1303
01:03:27,943 --> 01:03:30,090
这就像选择排序
在某种意义上说，它

1304
01:03:30,090 --> 01:03:32,131
不要紧，你的
列表，它只是会

1305
01:03:32,131 --> 01:03:34,801
做同样的事情，每一次。

1306
01:03:34,801 --> 01:03:35,300
好。

1307
01:03:35,300 --> 01:03:39,950
所以当你们可以看到，即使
我们已经走了through-- n中的种种

1308
01:03:39,950 --> 01:03:41,660
平方，这不是很有效。

1309
01:03:41,660 --> 01:03:47,060
而即使是这样的n log n是
不是最有效的。

1310
01:03:47,060 --> 01:03:49,720
如果你们是好奇，
有某种机制

1311
01:03:49,720 --> 01:03:54,310
这是如此有效，以至于他们
几乎是基本持平的运行时间。

1312
01:03:54,310 --> 01:03:55,420
>> 你有一些日志ñ的。

1313
01:03:55,420 --> 01:03:58,190
你有一些loglogN个的。

1314
01:03:58,190 --> 01:04:00,330
我们不触及他们
在这个类现在。

1315
01:04:00,330 --> 01:04:02,663
但是，如果你们是好奇，
随意谷歌，什么是

1316
01:04:02,663 --> 01:04:04,392
最有效的分类机制。

1317
01:04:04,392 --> 01:04:06,350
我不知道，有
一些很搞笑的人，

1318
01:04:06,350 --> 01:04:09,860
like--有一些真的
有趣的那些人做。

1319
01:04:09,860 --> 01:04:12,210
你想知道他们是如何
没有想过这一点。

1320
01:04:12,210 --> 01:04:15,730
因此谷歌，如果你有一些空闲
时间上，都有些什么有趣的方式

1321
01:04:15,730 --> 01:04:17,730
该people--以及
高效ways--人

1322
01:04:17,730 --> 01:04:20,371
之所以能够实现排序。

1323
01:04:20,371 --> 01:04:20,870
好。

1324
01:04:20,870 --> 01:04:22,880
而这里只是一个方便的小图。

1325
01:04:22,880 --> 01:04:26,850
我知道在座的各位，是竞猜0之前，
会在你的房间可能是试图

1326
01:04:26,850 --> 01:04:27,960
记住这一点。

1327
01:04:27,960 --> 01:04:30,940
所以这是很好的在那里为你们。

1328
01:04:30,940 --> 01:04:37,120
但不要忘记，made--逻辑
为什么这些数字正在发生。

1329
01:04:37,120 --> 01:04:39,870
如果你总是输了，只是让
确保你知道什么是排序是。

1330
01:04:39,870 --> 01:04:40,820
你可以贯穿
它们在你的心中

1331
01:04:40,820 --> 01:04:42,903
弄清楚为什么那些
答案是这些问题的答案。

1332
01:04:42,903 --> 01:04:46,250

1333
01:04:46,250 --> 01:04:47,600
>> 好吧。

1334
01:04:47,600 --> 01:04:49,680
所以，我们要动
在最后，在搜索。

1335
01:04:49,680 --> 01:04:51,638
因为那些对你
谁看过处理器集，

1336
01:04:51,638 --> 01:04:55,175
搜索也是部分
这个星期的习题集。

1337
01:04:55,175 --> 01:04:57,300
你会被要求执行
两种类型的搜索。

1338
01:04:57,300 --> 01:05:00,070
一个是线性搜索和
一个是一个二进制搜索。

1339
01:05:00,070 --> 01:05:01,760
>> 所以线性搜索是相当容易的。

1340
01:05:01,760 --> 01:05:04,070
你只是想搜索的元素
列表，看看你得到它。

1341
01:05:04,070 --> 01:05:05,444
你只需要遍历。

1342
01:05:05,444 --> 01:05:08,170
如果它等于什么，
你可以返回它，对吗？

1343
01:05:08,170 --> 01:05:10,890
但是，一个我们最
兴趣谈论

1344
01:05:10,890 --> 01:05:14,550
是二进制搜索，右，这是
分而治之的机制，

1345
01:05:14,550 --> 01:05:18,190
大卫被证明在讲座。

1346
01:05:18,190 --> 01:05:20,810
>> 还记得电话簿的例子
他不断拉扯大，

1347
01:05:20,810 --> 01:05:23,960
一个那种他挣扎
有点过去的一年，

1348
01:05:23,960 --> 01:05:27,530
在那里你把这个问题了一半，
一半，一半，一遍又一遍，

1349
01:05:27,530 --> 01:05:30,730
直到你找到你想要的？

1350
01:05:30,730 --> 01:05:33,727
而你已经得到了
那运行时也是如此。

1351
01:05:33,727 --> 01:05:35,810
你可以看到，它的
显著更高效

1352
01:05:35,810 --> 01:05:39,080
比任何其他类型的搜索。

1353
01:05:39,080 --> 01:05:41,880
>> 所以我们会去的方式
实现的二进制搜索

1354
01:05:41,880 --> 01:05:46,510
是，如果我们有一个数组，
索引为0到6，7的元素，

1355
01:05:46,510 --> 01:05:49,790
我们可以看看在中间，right--
很抱歉，如果我们的问题first--

1356
01:05:49,790 --> 01:05:53,840
如果我们要问的问题，请问
该阵列含有的7的元件，

1357
01:05:53,840 --> 01:05:56,840
显然，是人类，并且具有
这样一小阵，很容易让我们

1358
01:05:56,840 --> 01:05:58,210
说是。

1359
01:05:58,210 --> 01:06:05,750
但方式来实现二进制
搜索将是寻找在中间。

1360
01:06:05,750 --> 01:06:08,020
>> 我们知道，指数3
中间，因为我们

1361
01:06:08,020 --> 01:06:09,270
知道有七个要素。

1362
01:06:09,270 --> 01:06:10,670
什么7除以2？

1363
01:06:10,670 --> 01:06:12,850
你可以额外1砍掉。

1364
01:06:12,850 --> 01:06:14,850
你在中间得到了3。

1365
01:06:14,850 --> 01:06:17,590
所以为3数组等于7？

1366
01:06:17,590 --> 01:06:18,900
它是不是，对不对？

1367
01:06:18,900 --> 01:06:21,050
但是，我们可以做一对夫妇的检查。

1368
01:06:21,050 --> 01:06:25,380
是3小于7或阵列
是3阵列大于7？

1369
01:06:25,380 --> 01:06:27,240
>> 我们知道，这是不到7。

1370
01:06:27,240 --> 01:06:30,259
因此，我们知道，哦，就必须
不会在左半部。

1371
01:06:30,259 --> 01:06:32,300
我们知道，它必须是
在右前卫，对不对？

1372
01:06:32,300 --> 01:06:34,662
因此，我们可以只砍掉一半的阵列。

1373
01:06:34,662 --> 01:06:36,370
我们甚至不有
看它了。

1374
01:06:36,370 --> 01:06:38,711
因为我们知道，
一半的problem--的

1375
01:06:38,711 --> 01:06:41,210
我们知道答案是
我们的问题的右半部分。

1376
01:06:41,210 --> 01:06:42,580
因此，我们只看现在。

1377
01:06:42,580 --> 01:06:44,860
>> 所以，现在我们来看看
中间还剩下些什么。

1378
01:06:44,860 --> 01:06:46,880
该指数5。

1379
01:06:46,880 --> 01:06:50,200
我们再次做同样的检查
而且我们看到，它的体积更小。

1380
01:06:50,200 --> 01:06:52,050
因此，我们期待的是左边。

1381
01:06:52,050 --> 01:06:53,430
然后我们看到检查。

1382
01:06:53,430 --> 01:06:57,600
是在阵列值
索引4等于7？

1383
01:06:57,600 --> 01:06:58,260
它是。

1384
01:06:58,260 --> 01:07:03,580
因此，我们可以返回true，因为
我们发现在我们的列表中选择值。

1385
01:07:03,580 --> 01:07:06,738
我是否通过去的方式
是否有意义给大家？

1386
01:07:06,738 --> 01:07:08,760
好。

1387
01:07:08,760 --> 01:07:11,670
我给你们也许一样，
三，四分钟，以搞清楚

1388
01:07:11,670 --> 01:07:13,270
如何在伪代码本。

1389
01:07:13,270 --> 01:07:18,070
>> 所以，想象一下，我问你写
函数调用搜索（）的返回

1390
01:07:18,070 --> 01:07:20,640
一个值，布尔值，
这是真的还是false--类似，

1391
01:07:20,640 --> 01:07:22,970
如果你找到了真正的
值，如果你没有假的。

1392
01:07:22,970 --> 01:07:25,230
然后你
在值传递你

1393
01:07:25,230 --> 01:07:28,410
在寻找到值，
是array--哦，我一定会把

1394
01:07:28,410 --> 01:07:29,410
在错误的地方。

1395
01:07:29,410 --> 01:07:29,580
好。

1396
01:07:29,580 --> 01:07:31,829
不管怎样，应该有
到过的值的右侧。

1397
01:07:31,829 --> 01:07:36,280
然后INT n是数
在该数组元素。

1398
01:07:36,280 --> 01:07:39,430
你会如何​​去努力
伪代码在这个问题？

1399
01:07:39,430 --> 01:07:41,630
我给你们喜欢
三分钟的时间做到这一点。

1400
01:07:41,630 --> 01:08:00,137

1401
01:08:00,137 --> 01:08:02,595
不，我认为有only--
是啊，有一个正确的在这里。

1402
01:08:02,595 --> 01:08:03,261
听众：可以吗？

1403
01:08:03,261 --> 01:08:04,388
ANDI彭：是啊，我给你。

1404
01:08:04,388 --> 01:08:09,410

1405
01:08:09,410 --> 01:08:11,050
是不是工作？

1406
01:08:11,050 --> 01:08:12,290
嗯不错。

1407
01:08:12,290 --> 01:10:43,590

1408
01:10:43,590 --> 01:10:44,720
>> 好。

1409
01:10:44,720 --> 01:10:47,630
好球员，我们
要收服入。

1410
01:10:47,630 --> 01:10:49,730
好。

1411
01:10:49,730 --> 01:10:54,020
因此，假设我们已经有了这个可爱的
小数组在它的n值。

1412
01:10:54,020 --> 01:10:55,170
我没有画线。

1413
01:10:55,170 --> 01:10:58,649
但是我们怎么能去
尝试写这个？

1414
01:10:58,649 --> 01:11:00,440
有没有人要
给我的第一行？

1415
01:11:00,440 --> 01:11:02,814
如果你想给我
第一行该伪代码。

1416
01:11:02,814 --> 01:11:06,563

1417
01:11:06,563 --> 01:11:08,430
>> 听众：[听不清]

1418
01:11:08,430 --> 01:11:10,138
听众：你想要
遍历through--

1419
01:11:10,138 --> 01:11:11,094
听众：只为循环的另一个？

1420
01:11:11,094 --> 01:11:11,760
听众：──。

1421
01:11:11,760 --> 01:11:15,880

1422
01:11:15,880 --> 01:11:17,780
>> ANDI彭：所以这一块是有点棘手。

1423
01:11:17,780 --> 01:11:23,130
想想about--你想
要继续运行这个循环

1424
01:11:23,130 --> 01:11:27,950
一遍又一遍，直到什么时候呢？

1425
01:11:27,950 --> 01:11:30,819
>> 听众：直到[听不清]
值等于该值。

1426
01:11:30,819 --> 01:11:31,610
ANDI鹏：没错。

1427
01:11:31,610 --> 01:11:33,900
所以，你可以真正地写 - 
我们甚至可以把它简化了。

1428
01:11:33,900 --> 01:11:35,630
我们可以写一个while循环，对不对？

1429
01:11:35,630 --> 01:11:39,380
所以，你可以有loop--
我们知道，这是一段时间。

1430
01:11:39,380 --> 01:11:42,850
但现在，我要去
说“循环” - 通过什么？

1431
01:11:42,850 --> 01:11:46,640
环until--是什么
我们结束条件？

1432
01:11:46,640 --> 01:11:47,510
我想我听到了。

1433
01:11:47,510 --> 01:11:48,530
我听到有人说了吧。

1434
01:11:48,530 --> 01:11:51,255
>> 听众：值等于中间。

1435
01:11:51,255 --> 01:11:52,255
ANDI彭：再说一遍。

1436
01:11:52,255 --> 01:11:54,470
听众：或者，直到
值要搜索

1437
01:11:54,470 --> 01:11:58,470
为等于中间值。

1438
01:11:58,470 --> 01:12:00,280
>> ANDI彭：如果有什么是不是在那里？

1439
01:12:00,280 --> 01:12:03,113
如果你正在寻找的价值
对于实际上不是在这阵？

1440
01:12:03,113 --> 01:12:05,890
听众：你返回1。

1441
01:12:05,890 --> 01:12:08,850
>> ANDI鹏：但是我们要
循环，直到如果我们有一个条件？

1442
01:12:08,850 --> 01:12:09,350
是啊。

1443
01:12:09,350 --> 01:12:11,239
>> 听众：直到有只有一个值？

1444
01:12:11,239 --> 01:12:13,530
ANDI彭：你可以循环
until--让你知道，你是

1445
01:12:13,530 --> 01:12:15,714
将有一个最大值，对不对？

1446
01:12:15,714 --> 01:12:18,130
而你知道，你会
有一个最小值，对不对？

1447
01:12:18,130 --> 01:12:20,379
也因为，这东西
我忘了之前的说法，

1448
01:12:20,379 --> 01:12:22,640
这东西是
约二分查找关键

1449
01:12:22,640 --> 01:12:24,182
是你的数组已经排序。

1450
01:12:24,182 --> 01:12:26,973
因为没有办法做
这一点，如果他们只是随机值。

1451
01:12:26,973 --> 01:12:29,190
你不知道，如果一个人的
比另一个大，对吧？

1452
01:12:29,190 --> 01:12:32,720
>> 所以，你知道你的最大和
您分钟都在这里，对不对？

1453
01:12:32,720 --> 01:12:35,590
如果你将要调整
你最大的您分钟和mid--

1454
01:12:35,590 --> 01:12:38,470
就让我们假设你的
中间值右这里 - 

1455
01:12:38,470 --> 01:12:43,910
你要基本
循环，直到你的最小值是

1456
01:12:43,910 --> 01:12:47,510
大致相同的最大，右，或
如果你的max是不一样的分。

1457
01:12:47,510 --> 01:12:48,040
对？

1458
01:12:48,040 --> 01:12:51,340
因为当发生这种情况，你知道，
你最终击中了相同的值。

1459
01:12:51,340 --> 01:12:59,135
所以，你要循环，直到你分钟
小于或等于用于：哎呀，

1460
01:12:59,135 --> 01:13:01,510
不小于或等于
around--最大的另一种方法是。

1461
01:13:01,510 --> 01:13:15,110

1462
01:13:15,110 --> 01:13:16,160
>> 这是否有意义？

1463
01:13:16,160 --> 01:13:18,810
我花了一些尝试，以获得这一权利。

1464
01:13:18,810 --> 01:13:21,869
但循环，直到你的最大值
基本上是差不多少

1465
01:13:21,869 --> 01:13:23,410
大于或等于您的最低，对不对？

1466
01:13:23,410 --> 01:13:25,201
当你知道这是
你已经收敛。

1467
01:13:25,201 --> 01:13:29,290
听众：当你将最大
值是小于最小？

1468
01:13:29,290 --> 01:13:31,040
ANDI彭：如果你保持
调整它，这

1469
01:13:31,040 --> 01:13:32,380
就是我们要
在做这个。

1470
01:13:32,380 --> 01:13:33,460
那有意义吗？

1471
01:13:33,460 --> 01:13:35,750
最小和最大只是
整数，我们可能

1472
01:13:35,750 --> 01:13:39,260
将要创建的保留
赛道上，我们正在寻找的。

1473
01:13:39,260 --> 01:13:41,790
因为数组存在
无论我们在做什么的。

1474
01:13:41,790 --> 01:13:45,030
就像，我们没有实际的物理
斩去阵列，对不对？

1475
01:13:45,030 --> 01:13:47,261
我们只是调整
我们正在寻找。

1476
01:13:47,261 --> 01:13:48,136
那有意义吗？

1477
01:13:48,136 --> 01:13:48,472
>> 听众：是的。

1478
01:13:48,472 --> 01:13:49,110
>> ANDI彭：OK。

1479
01:13:49,110 --> 01:13:57,090
所以，如果这对我们的循环中的条件，
我们需要什么这个循环里面？

1480
01:13:57,090 --> 01:13:58,700
什么是我们将要想要做什么？

1481
01:13:58,700 --> 01:14:02,390
所以，现在，我们已经有了
一个最大和最小，权，

1482
01:14:02,390 --> 01:14:04,962
可能产生在这里的某个地方。

1483
01:14:04,962 --> 01:14:07,170
我们将可能希望
找一个中间的，对不对？

1484
01:14:07,170 --> 01:14:08,450
我们该如​​何为
能找到中间？

1485
01:14:08,450 --> 01:14:09,491
什么是mathematical--

1486
01:14:09,491 --> 01:14:11,079
听众：最大加分除以2。

1487
01:14:11,079 --> 01:14:11,870
ANDI鹏：没错。

1488
01:14:11,870 --> 01:14:20,300

1489
01:14:20,300 --> 01:14:21,620
那有意义吗？

1490
01:14:21,620 --> 01:14:25,780
做你们明白为什么我们
不只是use--为什么我们这样做

1491
01:14:25,780 --> 01:14:27,850
而不是做了2只除以n？

1492
01:14:27,850 --> 01:14:30,310
这是因为n是一个值
那将保持不变。

1493
01:14:30,310 --> 01:14:30,979
对？

1494
01:14:30,979 --> 01:14:34,020
但是，当我们调整我们的最低和
最大值，他们将改变。

1495
01:14:34,020 --> 01:14:36,040
其结果，我们的中间
都不会改变太多。

1496
01:14:36,040 --> 01:14:37,873
所以这就是为什么我们要
在这里做的权利。

1497
01:14:37,873 --> 01:14:38,510
好。

1498
01:14:38,510 --> 01:14:41,600
>> 然后，现在
我们发现our--耶。

1499
01:14:41,600 --> 01:14:44,270
>> 听众：只是一个快速的问题 - 
当你说最大和最小，

1500
01:14:44,270 --> 01:14:46,410
在我们假设
它已经排序？

1501
01:14:46,410 --> 01:14:48,400
>> ANDI彭：是啊，这实际上是一个
先决条件二进制搜索，

1502
01:14:48,400 --> 01:14:49,816
你必须知道它的排序。

1503
01:14:49,816 --> 01:14:53,660
这就是为什么排序，你写你的
您的二进制搜索之前，习题集。

1504
01:14:53,660 --> 01:14:55,910
好。

1505
01:14:55,910 --> 01:14:58,876
所以，现在我们知道我们的中点
是，你要什么做的吗？

1506
01:14:58,876 --> 01:15:01,789

1507
01:15:01,789 --> 01:15:04,319
>> 听众：我们想比较
即到另一个。

1508
01:15:04,319 --> 01:15:05,110
ANDI鹏：没错。

1509
01:15:05,110 --> 01:15:12,280
所以，你要比较
月中的价值，对不对？

1510
01:15:12,280 --> 01:15:14,900

1511
01:15:14,900 --> 01:15:18,670
而这是什么告诉
我们，当我们比较？

1512
01:15:18,670 --> 01:15:22,226
什么是我们想要做的之后？

1513
01:15:22,226 --> 01:15:25,389
>> 听众：如果该值越大
比中期，我们希望把它割下来。

1514
01:15:25,389 --> 01:15:26,180
ANDI鹏：没错。

1515
01:15:26,180 --> 01:15:33,940
因此，如果该值大
比中旬，我们

1516
01:15:33,940 --> 01:15:36,550
会想改变这些
最小和马克塞斯，对不对？

1517
01:15:36,550 --> 01:15:38,980
我们需要什么改变？

1518
01:15:38,980 --> 01:15:42,145
因此，如果我们知道价值的地方
在这里，你有什么，我们要改变？

1519
01:15:42,145 --> 01:15:44,758
我们要改变我们的
最小的是中端，对不对？

1520
01:15:44,758 --> 01:15:49,420

1521
01:15:49,420 --> 01:15:54,292
然后否则，如果它在这个
上半年，有什么事我们要改变？

1522
01:15:54,292 --> 01:15:55,306
>> 听众：你最大的。

1523
01:15:55,306 --> 01:15:55,972
ANDI彭：是的。

1524
01:15:55,972 --> 01:16:02,597

1525
01:16:02,597 --> 01:16:04,680
然后，你只是去
保持循环，对不对？

1526
01:16:04,680 --> 01:16:08,920
因为现在，一次迭代后，
通过，你已经有了一个最大这里。

1527
01:16:08,920 --> 01:16:10,760
然后你就可以重新计算中间。

1528
01:16:10,760 --> 01:16:11,990
然后你就可以比较。

1529
01:16:11,990 --> 01:16:14,766
而你要坚持下去
直到分钟和马克塞斯

1530
01:16:14,766 --> 01:16:15,890
已经基本收敛。

1531
01:16:15,890 --> 01:16:17,890
而且，当你知道这是
你打它的结束。

1532
01:16:17,890 --> 01:16:20,280
而无论你已经找到了
或者你有没有在这一点上。

1533
01:16:20,280 --> 01:16:23,170
>> 这是否有意义给大家？

1534
01:16:23,170 --> 01:16:26,020

1535
01:16:26,020 --> 01:16:26,770
好。

1536
01:16:26,770 --> 01:16:27,900
这是非常重要的，
因为你有

1537
01:16:27,900 --> 01:16:29,760
在您的代码今晚这样写。

1538
01:16:29,760 --> 01:16:32,660
但是你们有一个相当不错的
什么，你应该做的意义，

1539
01:16:32,660 --> 01:16:34,051
这是很好的。

1540
01:16:34,051 --> 01:16:34,550
好。

1541
01:16:34,550 --> 01:16:38,840
所以，我们已经得到了大约七
离开分钟一节。

1542
01:16:38,840 --> 01:16:43,170
所以，我们要谈谈
这pset的，我们会做。

1543
01:16:43,170 --> 01:16:46,410
因此的pset分为两半。

1544
01:16:46,410 --> 01:16:50,230
上半年涉及
实施发现

1545
01:16:50,230 --> 01:16:54,210
在你写一个线性搜索，一
二进制搜索，和一个排序算法。

1546
01:16:54,210 --> 01:16:56,690
>> 因此，这是第一个
一次在PSET哪里

1547
01:16:56,690 --> 01:17:00,050
我们会给予你们什么所谓
分配代码，这是代码

1548
01:17:00,050 --> 01:17:02,740
我们已经预先写好，
只是留下了一些棋子落

1549
01:17:02,740 --> 01:17:04,635
为你完成写作。

1550
01:17:04,635 --> 01:17:07,510
所以你们这些家伙，当你看这个
代码中，你可能会真是吓坏了。

1551
01:17:07,510 --> 01:17:08,630
如果你只是想，啊，我
不知道这是什么在做，

1552
01:17:08,630 --> 01:17:11,670
我不知道一样，这似乎
这么复杂，啊，放松。

1553
01:17:11,670 --> 01:17:12,170
好的。

1554
01:17:12,170 --> 01:17:12,930
阅读规格。

1555
01:17:12,930 --> 01:17:16,920
该规范将解释你到底
什么所有这些方案都在做。

1556
01:17:16,920 --> 01:17:20,560
>> 例如，generate.c是一个程序
这会是你的pset中。

1557
01:17:20,560 --> 01:17:24,060
你实际上并没有去触摸它，但
你应该明白它在做什么。

1558
01:17:24,060 --> 01:17:28,550
而generate.c，所有它做的是
或者产生随机数

1559
01:17:28,550 --> 01:17:32,400
或者你可以给它一个种子，像
预先安排的号码，它需要，

1560
01:17:32,400 --> 01:17:34,140
它产生更多的数字。

1561
01:17:34,140 --> 01:17:37,170
因此，有一种特定的方式来
实施generate.c其中

1562
01:17:37,170 --> 01:17:42,760
你可以做一串数字
为您测试您的其他方法上。

1563
01:17:42,760 --> 01:17:45,900
>> 所以，如果你想为
例如，测试你的发现，

1564
01:17:45,900 --> 01:17:48,970
你想运行generate.c，
生成一串数字，

1565
01:17:48,970 --> 01:17:50,880
然后运行你的助手功能。

1566
01:17:50,880 --> 01:17:53,930
你的助手功能就是你
实际的物理写代码。

1567
01:17:53,930 --> 01:17:59,330
并认为佣工作为库文件
你写的那些发现正在呼叫。

1568
01:17:59,330 --> 01:18:02,950
所以在helpers.c，你会
做搜索和排序。

1569
01:18:02,950 --> 01:18:06,500
>> 然后，你要基本上
只是把它们放在一起。

1570
01:18:06,500 --> 01:18:10,350
该规范将告诉你如何
把在命令行上。

1571
01:18:10,350 --> 01:18:14,880
你就可以测试是否
不是你的排序和搜索工作。

1572
01:18:14,880 --> 01:18:15,870
酷。

1573
01:18:15,870 --> 01:18:18,720
有没有人已经开始，
遇到问题或疑问

1574
01:18:18,720 --> 01:18:20,520
他们现在所拥有的这个吗？

1575
01:18:20,520 --> 01:18:21,020
好。

1576
01:18:21,020 --> 01:18:21,476
>> 听众：等待。

1577
01:18:21,476 --> 01:18:21,932
我有一个问题。

1578
01:18:21,932 --> 01:18:22,844
>> ANDI彭：是的。

1579
01:18:22,844 --> 01:18:28,390
>> 听众：所以我就开始做
在helpers.c线性搜索

1580
01:18:28,390 --> 01:18:29,670
它并没有真正的工作。

1581
01:18:29,670 --> 01:18:34,590
但后来，我发现我们只是
要删除它，做二进制搜索。

1582
01:18:34,590 --> 01:18:36,991
因此，它的问题，如果它不能正常工作？

1583
01:18:36,991 --> 01:18:39,700

1584
01:18:39,700 --> 01:18:41,510
>> ANDI彭：简短的答案是否定的。

1585
01:18:41,510 --> 01:18:42,642
但由于我们是不是 - 

1586
01:18:42,642 --> 01:18:44,350
听众：但是，没有一个人的
其实检查。

1587
01:18:44,350 --> 01:18:46,058
ANDI彭：我们从来没有
要看到这一点。

1588
01:18:46,058 --> 01:18:49,590
但是，你可能想使
确保你的搜索工作。

1589
01:18:49,590 --> 01:18:51,700
因为如果你的线性
搜索无法正常工作，

1590
01:18:51,700 --> 01:18:54,410
那么机会是你的二进制
搜索是不会正常工作。

1591
01:18:54,410 --> 01:18:56,646
因为你也有类似的
逻辑在两人面前。

1592
01:18:56,646 --> 01:18:58,020
不，这其实并不重要。

1593
01:18:58,020 --> 01:19:01,300
所以唯一的，你转
在有排序和二进制搜索。

1594
01:19:01,300 --> 01:19:02,490
是啊。

1595
01:19:02,490 --> 01:19:06,610
>> 而且，很多孩子们
尝试编译helpers.c。

1596
01:19:06,610 --> 01:19:09,550
你没有真正允许
要做到这一点，因为helpers.c

1597
01:19:09,550 --> 01:19:11,200
不具有的主要功能。

1598
01:19:11,200 --> 01:19:13,550
所以，你只应该
是实际编制

1599
01:19:13,550 --> 01:19:18,670
产生和发现，因为找不到电话
helpers.c并在它的职能。

1600
01:19:18,670 --> 01:19:20,790
这样就使得调试
一个痛苦的对接。

1601
01:19:20,790 --> 01:19:22,422
但是，这就是我们要做的。

1602
01:19:22,422 --> 01:19:23,880
听众：你刚才做的所有，对不对？

1603
01:19:23,880 --> 01:19:27,290
ANDI彭：你可以
让所有的嗯，是的。

1604
01:19:27,290 --> 01:19:28,060
好。

1605
01:19:28,060 --> 01:19:32,570
所以这是它在什么条件
pset的要求你都做。

1606
01:19:32,570 --> 01:19:35,160
如果您有任何问题，请随时
免费区之后问我。

1607
01:19:35,160 --> 01:19:37,580
我会在这里一样，20分钟。

1608
01:19:37,580 --> 01:19:40,500
>> 和是的，处理器集的
真的没有那么糟糕。

1609
01:19:40,500 --> 01:19:41,680
你们应该没问题。

1610
01:19:41,680 --> 01:19:43,250
这些，只是遵循的指导方针。

1611
01:19:43,250 --> 01:19:47,840
一种有意识，从逻辑上讲，是什么
应该发生，你会没事的。

1612
01:19:47,840 --> 01:19:48,690
不要太害怕。

1613
01:19:48,690 --> 01:19:50,220
有很多的代码
已经写在那里。

1614
01:19:50,220 --> 01:19:53,011
不要太害怕，如果你不
明白了这一切手段。

1615
01:19:53,011 --> 01:19:54,749
如果这是一个很大，这是完全罚款。

1616
01:19:54,749 --> 01:19:55,790
而来到办公时间。

1617
01:19:55,790 --> 01:19:57,520
我们会帮你看看。

1618
01:19:57,520 --> 01:20:00,810
>> 听众：用多余的
功能，我们看这些吗？

1619
01:20:00,810 --> 01:20:03,417
>> ANDI彭：是的，这些都是在代码中。

1620
01:20:03,417 --> 01:20:05,750
在游戏中的15，一半的
它已经为你写的。

1621
01:20:05,750 --> 01:20:09,310
因此，这些功能
已经在代码中。

1622
01:20:09,310 --> 01:20:12,020
是的。

1623
01:20:12,020 --> 01:20:12,520
好吧。

1624
01:20:12,520 --> 01:20:14,000
那么，最好的运气。

1625
01:20:14,000 --> 01:20:15,180
这是一个恶心的一天。

1626
01:20:15,180 --> 01:20:19,370
所以希望你们不要觉得太
不好呆在里面和编码。

1627
01:20:19,370 --> 01:20:22,133