扬声器1：嗨大家好！ 欢迎回到一节。 很高兴见到你们这么多人都在这里， 大家谁的在线观看。 所以，像往常一样，欢迎回来。 我希望大家都度过了一个可爱 周末，得到充分的休息，放松。 这是美丽的昨天。 所以，我希望你喜欢户外活动。 因此，首先一对夫妇公告。 分级。 所以，你最应该得到的 从我的电子邮件你刮的Pset， 以及分级的Pset中1。 所以，只是一对夫妇的事情。 请务必使用check50在style50。 这些都意味着是 资源为你们， 确保你得到 尽可能多的点，你可以 没有不必要的失去他们。 所以像风格 是非常重要的。 我们要起飞了。 你们有些人可能已经 注意到，从你的pset中。 和check50仅仅是一个 非常简单的方法，以确保 那我们实际上回归了什么 需要被返回给用户， 而这一切的正常工作。 在第二个音符时，请确保您的 上传东西到正确的文件夹中。 它使我的生活只是一个 更困难一点 如果你上传的Pset 2成1的Pset 因为当我下载的东西， 他们不能正确下载。 我知道这是一个有点靠不住 在一个系统中使用的获得， 但只是超 小心，如果只是对我来说， 所以，当你得到的邮件 在像上午02点我就是分级。 如果没有引起我要看看 各地为您的Pset。 凉爽。 我知道这是早期的，但我 完全得到起飞​​后卫 通过一篇短文这是本周五到期，该 我的教授只是喜欢，哦耶。 请记住，你有一个 文章将于周五公布。 所以，我知道没有人喜欢 想想期中考试， 但你的第一次测验是10月15日， 其中10月份这个星期开始。 因此，它可能是迟早 比你预期的是一切。 让你不扔猝不及防的时候 我提到下周一节哦， 您的测验接下来的一周，我想 我愿意给你一点点 的抬起头来了。 所以，你的问题集，排名第三。 人如何阅读 规范的好奇心了呢？ 行。 我们有一对夫妇。 那种从上向下 本周不过没关系。 我知道这是美丽的。 因此爆发。 一定时间后就会完成 今天看了你的天赋，至少 尝试像下载 发行代码并运行 像第一初始 他们问你要的东西。 因为我们使用 分配代码和一个图书馆 我们只是一直在using-- --IT只是 第二次我们已经做到了这一点的Pset， 疯狂的事情都可能发生 与您的设备， 你想找到 从现在与以后。 因为如果是周四晚上或它的 周三晚上，由于某种原因 您的设备少了点 要与库运行 或用分配 代码，这意味着 你甚至不能开始做编码。 因为你不能检查 来看看它的工作原理。 你不会是能够 看它是否编译。 你想在早期照顾那些 本周，当你仍然可以给我发电子邮件 或其他转录因子中的一个， 我们可以得到这些固定的。 因为这些都是问题 这会阻止你 做任何实际进展。 它不象1的bug，那 有种你就跳过。 如果您遇到问题，您 设备或分发代码， 你真的想要得到所采取的 呵护宜早不宜迟。 所以，即使你不会真正 开始编码，下载发行 码，读取规格，确保 一切都在那里工作。 行？ 如果你可以做到这一点，我 答应你的生活会更容易。 所以你很可能会 要做到这一点，现在好吗？ 行。 那么，有什么问题吗？ 任何逻辑的东西呢？ 大家的好？ 行。 免责声明对于那些 你在房间里上网。 我将要尝试切换 PowerPoint中的装置之间 因为我们要 是做一些编码 今天流行的匿名需求 调查建议我送出去的最后一周。 所以，我们会做一些编码。 所以，如果你们也想 火了你的设备， 你应该已经得到了一封电子邮件， 从我来说，有一个示例文件。 请随时做。 所以，我们要谈 GDB，这是一个调试程序。 这将帮助你 种揣摩出 事情会出错的代码。 这真的只是一个方法可以让你一步 通过你的代码，它的发生， 并能够打印出变量 或者看看有什么实际发生 引擎盖下的诗句程序 刚运行时，它就像断层， 和你一样，不知道 这里刚刚发生了什么。 我不知道它没有在哪一行。 我不知道哪里出了问题。 因此，GDB会帮助你的。 另外，如果你决定 继续没错，走61， 它真的，真的是你 最好的朋友，因为我可以告诉你 因为我要通过这个类。 我们要看看二进制 搜索，这如果你们还记得 伟大的电话簿例子 眼镜从类。 我们将实现这一点， 通过多一点点走， 然后我们要通过四个 不同种类的，这是泡沫， 选择，插入和合并。 凉爽。 所以，GDB正如我所说，是一个调试器。 而这些都是一种大的 的东西，大的功能或命令 您在使用GDB，我会走 你通过它在第二演示。 所以，这不仅是 要留抽象。 我会试着让它混凝土 尽可能为你们。 因此，突破。 它会要么是突破 象，一些数量，这 代表你的程序行， 或者，你可以命名的功能。 所以，如果你说分手主力， 它会停在主， 并且让你通过该功能走路。 同样，如果你有一些外部 功能类似于交换或多维数据集， 我们看最后一周。 如果你说破其中的一个， 只要你的程序打了， 就等你来 告诉它要做什么。 之前，它只会执行，所以你 可以在函数内部实际步骤 看看是怎么回事。 所以，接下来，就跳过了 下一行，越过功能。 步骤。 这些都是有点抽象。 所以，我只是通过他们的运行， 但你会看到他们在第二次使用。 步入函数。 因此，正如我所说， 像交换，它会 让你真正的，如果你 就像身体里面的加强， 你可以乱用这些变量，打印 它们是什么，看看发生了什么事情。 名单将字面上只是打印 从周围的代码。 所以，如果你种忘了 你在哪里在你的程序中， 或者你想知道 这是怎么回事周围， 这将只打印出一个段 都喜欢它周围的五六行。 所以，你可以得到导向 关于你在哪里。 打印一些变量。 所以，如果你有这样的关键 在恺撒，那我们来看看。 你可以说在任何时候打印键。 它会告诉你的价值就是如此 这，也许某个地方一路走来， 你重写你的关键。 实际上，你可以告诉大家，因为 你其实可以观察到的价值。 在当地人，只是版画 你的局部变量。 所以，任何时候，你是在一个循环中， 而你只是想看看像哦。 什么是我的吗？ 这是什么键值 我在这里初始化？ 这是在这一点上的信息？ 它只是将打印所有 那些的，这样就 不必单独地 说，打印一打印信息。 打印键。 然后显示。 这是什么做的是为你 单步执行程序， 它会只是确保它的 显示一定的变数 在每一点上。 所以，你also-- --IT是 一种快捷方式，其中的 你没有坚持下去似的，呵呵。 打印键或打印一，这只是 将自动为您代劳。 因此，在这一点，我们要去 怎么看这样下去。 我要去尝试和开关 在我的设备。 看看我能做到这一点。 全部。 我们只是要镜像。 没有什么疯狂 我的笔记本电脑反正。 行。 这需要这个。 它是如此的渺小。 让我们来看看，如果我们能做到这一点。 行。 爱丽丝显然是挣扎 这里只是一点点， 但我们会让它在你几分钟。 行。 我们只是要增加这一点。 行。 种可大家看到了吗？ 也许一点点？ 我知道这是小了点。 你不能完全弄清楚 如何使这个更大。 如果有人知道。 有谁知道如何使它更大？ 行。 我们将推出它。 不要紧，反正，因为它只是 这是代码，你们应该 有。 什么是更重要的 是这里的端子。 而我们在这里为什么会这么少呢？ 设置。 呵呵。 真正的艾克。 这个怎么样？ 离开那里。 是为大家好？ 行，。 凉爽。 你知道，当你在CS 一流的技术困难 是善良的the--一部分 所以，让我们澄清这一点。 行。 所以，这里的部分​​， 我们不得不在这里。 凯撒是一个可执行文件。 所以，我做到了。 所以，有一点要实现与GDB是 它仅适用于可执行文件。 所以，你不能在dotsy运行它。 你要真正使 确保你的代码编译， 并且，它可以实际运行。 因此，请相信，如果它不 编译，得到它的编译， 这样就可以通过它种上运行。 因此，要启动GDB，你所要做的， 凯莱型GDB，然后就在 文件，你想要的。 我总是拼错撒。 但是你要确保 因为它是一个可执行文件， TI的圆点闪烁，使 意味着你要 运行CSI你要执行 此文件或者与调试。 行。 所以，你这样做，你会得到 这种乱码。 这只是所有关于调试的东西。 你不会真的要 担心现在。 正如你看到的，我们有这个 开括号，国内生产总值，接近括号， 而那种只是看起来像 我们的命令行，对不对？ 所以，我们要do-- - 因此，第一件事 就是我们要选 一个地方打破它。 所以，有一个错误 在这个程序凯撒 我介绍一下，这 我们要了解一下。 它是做什么是需要输入 Barfoo全部大写，并由于某种原因 它只是离开它不会改变A. 孤军奋战，是一切正确， 但第二个字母 A保持不变。 所以，我们要尝试 弄清楚这是为什么。 所以，第一件事情，你通常 想要每次启动GDB上做 是从哪里打破它。 因此，凯撒是一个很短的程序。 我们只是有一个功能，对不对？ 什么是我们的凯撒功能？ 这里只有一个功能，主要对不对？ 主要是功能 您的所有程序。 如果没有主，我可能会 是有点担心，现在， 但我希望你们都在那里有主。 所以，我们可以做的是，我们可以 刚刚突破主，就这样。 因此，它说，OK。 我们设置了断点，一个人也没有。 所以，现在要记住的是凯撒 需要一个命令行参数的权利 我们还没有做到这一点还没有任何地方。 所以，你要做的就是当 你居然去跑 该程序，你是任何程序 在GDB运行需要的命令行 参数，你要输入 当你第一次启动运行它。 所以，在这种情况下，我们做 与三支一键运行。 它会真正开始。 所以，如果你看到这里，我们有 如果RC不等于2。 所以，如果你们都 我送出了该文件 你会看到，就像 第一行我们的主要功能，对不对？ 它的检查，看看是否有 正确数目的参数。 所以，如果你想知道 如果RC是正确的， 你可以做一些事情，就像打印RC。 RC为2，这是 我们所预期的，对不对？ 因此，我们可以去下， 并继续通过。 因此，我们有一些关键的有。 我们可以打印出我们的关键 以确保是正确的。 有意思的。 并不完全符合我们的预期。 所以，有一点认识 用GDB也，是 它不是，直到你竟然打 接下来，你刚才看到的行 实际执行。 所以，在这种情况下关键 尚未分配爱好。 所以，关键是一些垃圾的价值 您在底部有看到。 负$ 120-- --IT坚持一个十亿 和一些奇怪的事情吧？ 这不是我们所期望的关键。 但是，如果我们点击Next，然后我们 尝试打印键，它是三种。 大家看到了吗？ 所以，如果你得到的东西 那你喜欢，请等待。 这是完全 错了，我不知道 怎么会发生这种事，因为我想要的 做的是分配一个编号，变量 试着打接下来，尝试印刷 一遍，看看是否可行。 因为它只会执行和 之后，你实际上分配的东西 点击Next。 道理大家？ 嗯？ 扬声器2：当你随意 数字是什么意思呢？ 扬声器1：这只是随机的。 这只是垃圾。 这只是一些你 电脑会随机分配。 凉爽。 所以，现在我们可以通过移动，等等 现在我们有这个纯文本的GetString。 所以，让我介绍什么 会发生什么，当我们点击Next这里。 种了GDB消失了，对不对？ 这是因为GetString的 现在执行的，对不对？ 所以，当我们看到纯文本等于 GetString的，开放的括号和括号， 和我们打接下来，有 实际执行了。 因此，它在等待 我们输入一些东西。 所以，我们要输入我们的食物， 就是它的失败，因为我告诉过你 那只是说，这是 完成执行，该封闭 支架是指它的 退出了该循环。 因此，我们可以接着打，而现在，因为我 确保你所有的从凯撒熟悉， 这，这是什么行会的事情。 这对INT I等于0，N等于 strlen的，纯文本，然后 我是小于n，I，加，加。 什么是这个循环怎么办呢？ 打开你的邮件。 凉爽。 那么，让我们开始这样做。 因此，应此条件 匹配，我们的第一个？ 如果它是一个B，这是纯文本格式一，我们 可以了解我们当地人的信息。 所以，我是零​​，而如果6，其 我们希望，我们的重点是三。 所有这一切是有意义的，对吗？ 这些数字都 正是他们应该的。 因此，哼？ 扬声器3：我有 随机数我的。 扬声器1：嗯，我们可以check-- - 我们 可以聊，在第二。 但是，你应该得到这个。 所以，如果我们有一个资本 B我们的第一个， 这种情况下应该抓住它，对不对？ 所以，如果我们打接下来，我们看到 这如果实际执行。 因为如果你是以下 沿着你的代码， 这条线在这里，在纯文本我 替换为算术， 仅当如果执行 条件是正确的吗？ GDB只是要告诉你 这是实际执行的东西。 所以，如果没有达到这个如果条件下，它的 只是要跳到下一行。 行？ 因此，我们有。 这架意味着它 现在关闭了该循环。 因此，它会重新开始。 就这样。 因此，我们可以得到的信息 关于我们当地人在这里， 我们看到，我们的第一个 信改变了，对不对？ 它现在是E，因为它应该是。 因此，我们可以继续。 我们有这个检查。 而这种检查应该工作了吧？ 这是A.应该改变 三个字母前进。 但是，如果你注意到，我们 得到不同的东西。 所以在这种情况下在这里，它抓 它，因此这条线执行， 它修改了我们的B. 但是，在这里这种情况下， 我们认为它只是跳过它， 并到[？ L SIFF。 ？] 因此，一些对那里发生。 什么是告诉你的是， 我们知道，它应该在这里赶， 但事实并非如此。 任何人都可以看到我们的 问题是在该行？ 这是一个非常微小的事情。 你也可以看看你的代码。 它也line--忘了这是什么线 在那里 - 但它在[听不清]。 是吗？ 扬声器4：这是在比大 页面，如果你在书中读到它。 扬声器1：没错。 所以，调试分不清楚 你说，但是调试器 可以让你下到一条线 你知道不正常。 有时候，特别是当 后来在学期中，当 你处​​理了一百，一 百几行代码，你 不知道它的失败， 这是一个伟大的方式来做到这一点。 所以，我们发现我们的错误。 您可以修复它​​在你的文件， 然后，你可以再次运行它， 一切都将正常工作。 而最重要的事情是 这似乎是，OK。 是啊。 凉爽。 你知道你在寻找什么。 所以，你知道该怎么做。 GDB可能是因为你超级有帮助 可以打印出所有这些东西，你 不会。 它比的printf有用得多。 你们有多少人使用 如printf语句 找出其中的错误是，对不对？ 所以，这一点，你不 必须保持回去， 和喜欢的评论 printf的，或者注释掉， 并找出哪些 你应该打印。 这实际上只是让你 步，打印出来的东西 当你正在经历，所以，你可以 观察他们在现实时间的变化， 因为你的程序正在运行。 它确实需要一点点 对习惯一下。 我会强烈建议正中下怀 的是一个有点沮丧吧 对于现在。 如果你在花一个小时 下周学习如何使用GDB， 你能救自己 如此多的时间以后。 和字面上。告诉我们 这人年年有， 我记得，当我把 类，我很喜欢，我会没事的。 号 PSET 6来了，我是 喜欢，我要学习 如何使用GDB，因为我不 知道是怎么回事。 如果你花时间，所以， 使用它的小程序 那你会是 工作，喜欢工作 通过类似 Visionare，是这样的。 或者，如果你想要额外的练习，我敢肯定， 我可以用bug的程序上来， 为您调试，如果你愿意的话。 但如果你只是需要一些时间来获得 习惯了，只是玩它， 它真的会满足你的需要。 而且它是真正的一个 那些东西，你只是 必须尝试，并得到你的手脏 用，在你真正了解它。 我真的只听懂了一次 我调试的东西吧， 和它的更漂亮有一个想法 如何调试宜早不宜迟。 行。 凉爽。 我知道这有点像 速成班GDB， 我一定会努力的让 这些看起来更大下一次。 凉爽。 所以，如果我们回到我们的PowerPoint。 这是去上班？ AWH。 是的。 行。 所以，如果你需要任何 这些再次，还有的列表。 所以二进制搜索，人人 记得大卫的伟大奇观 撕成两半电话簿。 我真的不明白了 电话簿了， 因为喜欢你在哪里 获取电话簿可好？ 我真的不知道。 二进制搜索。 有谁还记得 如何二进制搜索作品？ 人呢？ 是吗？ 扬声器5：你知道什么时候 你看看是哪一半 这将是在，在此基础上， 和摆脱的另一半。 扬声器1没错。 因此，二进制搜索，它是一种A-- - 我们喜欢叫它分而治之。 所以，你要做的是 你将看到在中间， 你会看它是否符合 您要查找的内容。 如果没有，那么你尝试 搞清楚，它是将要离开 一半或右半部。 所以，这可能是如果你正在寻找 在东西是按字母顺序排列， 你看，哦。 难道佳佳来到先于M？ 是的。 所以，我们要 看看上半场。 或者它可能是像数字。 什么，你可以 比较，就可以进行排序。 您可以使用二进制搜索。 因此，任何人都记住了这个 图表或这是什么？ 这是渐近复杂性。 因此，此图只 介绍了多长时间 你需要解决一个问题， 你增加多少东西 您正在使用。 因此，我们有N个，其是直链的时间。 如果N超过2，略 好，还是成长超快。 然后我们登录，这是 我们认为二分查找。 如果我们注意到，作为您的问题 变多，大得多， 它把你的时间来解决它 并没有真正增加那么多。 这就像媲美 在这里开始。 你就像，OK。 任何事情在这里并没有真正 无论哪一种我们使用， 但你得到了一百万，一十亿。 你想找到some-- --you're 试图找到大海捞针。 我想你想这个问题。 你想这种复杂性，不 线性的，因为所有你 知道你会通过搜索来 每个单独的针，干草的事情， 试图寻找你的针。 而这还不是在我看来，太好玩了。 我喜欢快。 我喜欢有效率。 而作为勤奋的学生，你 家伙，你知道的更聪明地工作， 而不是更辛苦类型的事情，你怎么 可以弥补这些算法。 所以，我们要走路 仅仅通过一个简单的例子。 我想你们应该有 在二进制搜索手， 但在任何情况下，一点点 模糊，要加强它， 我们打​​算才行 通过这里的例子。 所以，我们要寻找的，如果 该数组包含七个。 所以，我们首先要做的就是 看在中间，对不对？ 而且你要被编码 在短短的二二分查找。 因此，这将很有趣。 因此，我们期待在 中间的小数组3。 3是否等于7？ 没有。 这是6。 那么，是不是小于 或大于7？ 少于。 是的。 干得漂亮家伙。 我觉得我我应该 有糖果，因为我 想要把它伸到码。 这就是我将在下周的事。 这将让你们锋利。 所以，我们扔掉了 上半年，对不对？ 这是小于。 我们知道，一切 在该左侧 将是小于什么 我们实际上是在寻找。 所以，没有必要 注意它。 忘掉它。 所以，现在我们看一下我们的右手边， 我们期待在中间那边， 现在它是9。 因此，9 is-- --Everyone？ 比我们大 找了吧？ 因此，我们要扔掉 客场的一切权利。 这样。 现在，我们只剩下一个。 所以我们检查，是这个东西 我们正在寻找什么？它是。 我们发现我们想要的。 所以，我们就大功告成了。 双线性搜索。 如果你注意到，我们 有七个输入存在。 只花了我们喜欢的三倍， 但如果你正在做的像一个十亿， 你们知道要走多少步会 走，如果我们有四十亿的事情呢？ 任何猜测？ 这是32。 32步找到的东西 在四十亿 因为两个大国的元素数组。 所以，二是32个，是四十亿。 所以很疯狂怎么你还在内 像一个相当小的数目的步骤 找东西 four十亿元素。 所以，关于这一点，我们 将这个代码 所以你们其实可以 样的了解其工作原理。 好吧，让你们可以代码。 我将让你们 聊了一点点。 了解你周围的人，这是 从最后一节什么人想要的。 所以，了解你周围的人。 聊了一点点。 和所有我想从你 你们现在只是 尝试创建伪代码的轮廓。 行？ 哇。 所有我想从你们这些家伙是你 只是要填补这一情况时。 所以我已经设置了这些上 界和下界哪 代表开始 我们的阵列和末端。 而你要真正 遍历并找出 我们正在做的这个while循环中。 所以，如果你自己看着办out--我 暗示那里 - 是什么情况 我们有吗？ 所以，如果你想弄清楚的 的情况下，我们将这些伪 然后我们就可以真的实现它们。 而这将是我 想想，希望它会 比预期的更容易一些。 因为它没有那么多的代码， 其实，这是真的很酷。 嗯？ 学生：[听不清]？ 指导老师：是的。 有一件事 发现在中间。 学生：所以我们可以使用它。 行。 讲师：完美。 所以这是我们需要做的第一件事。 所以，找到中间。 太好了。 所以，你有一个想法，我们怎么可能 实际上找到的代码中间？ 学生：是啊。 ñ超过2？ 讲师：因此n超过2。 所以，有一点要记住的是， 你的上界和下界改变。 我们不断收缩的部分 数组的，我们正在寻找。 因此n超过2只会工作 对于第一件事，我们做的。 因此服用上下兼顾， 怎么可能，我们得到了中量元素？ 因为我们想要中间 之间的上，下，右？ 嗯？ 学生：[听不清]。 讲师：所以我们有一些中间。 而这将是上加下超过2。 真棒。 在那里，我们走了。 一号线下来。 你们是在用自己的方式。 所以，现在，我们有我们 中间，有什么事我们想干什么？ 只是一般。 您不必编写它。 是的。 学生：[听不清]？ 讲师：所以这是加，因为你 发现两者之间的平均 对他们。 所以，如果你认为它们是一种 在从侧面增加， 想想看，当你接近 中间，你想这样的。 所以，如果你是对的两边 中间，我们有像5和7。 当你把它们加起来，你 得到12，你除以2，就是6。 有时候很难 解释为什么这样的作品， 但如果你的工作，通过 一个例子有时候， 它会帮你计算出，如果 它应该是正或负。 是的。 学生：[听不清] 恰好在中间 如果他们的情况 还有很多小的数字 而像一个大的数量？ 讲师：所以你需要 是阵列的中间。 所以，如果你有一堆小数字 再一个真正大量 在末端，也没关系。 所有的事情是， 他们排序，你只要 想看看中间 数组是因为你还 一半切片您的问题。 凉爽。 所以，现在，我们有 中间，我们接下来做什么？ 学生：比较。 讲师：当比较。 所以比较中间value_wanted。 凉爽。 所以你看在这里，我们有 我们要在这里这个值。 请记住，这是一个数组。 所以中间是指索引。 所以，我们要做的中间值。 如果你想不要忘记 比较，双等号。 你做单等于你 只是要重新分配它， 然后，当然，它们也 会是你想要的值。 所以，不要那样做。 所以，我们要如果看 在中间的值 等于我们想要的值。 不要忘了你的牙套。 Dropbox的应该消失。 那么，我们在这种情况下怎么办？ 如果它是什么，我们要回去呢？ 我们想说的。 学生：打印关闭。 讲师：嗯，我们 不想打印出来。 因此，这是这里的布尔值，因此我们 要返回true或false。 我们要说的，就是这个号码 一个[？ RRA？ ？]因此，如果它是， 我们只是回到它真实的。 如果我能拼写正确。 学生：你为什么不回零？ 讲师：所以，你可以 返回零，如果你想要的。 但在这种情况下，因为 我们的函数返回一个布尔值， 我们需要返回true或false。 学生：当你 话说布尔表达式， 你可以将其设置为假？ 就像如果我想说，如果这种情况 没有得到满足时，象是上等于false。 如果你只是将它理解 把假的另一边？ 指导老师：是啊。 因此，实际上，如果你 曾经做的事情 象是上还是下， 返回true或false 它实际上是不好的风格 比方说等于等于true或等于 等于false。 要使用该结果 因为本身你的支票。 不是我想要的。 这就是我想要的。 所以，在你的情况你问 关于像保存在C。 所以，如果我们有INT主要（无效） 而这样的事情。 你有，如果是上 一些输入你的 问如果你能做到 这样的事情？ 对不对？ 学生：我是想 要做到这一点[听不清]。 因为如果it's-- 指导老师：对。 所以，你希望这是假的，对不对？ 学生：是啊。 讲师：所以在这种情况下，你 希望它执行的，如果它是不正确的。 所以，你在那里做的很酷的事情是这样的。 所以请记住惊叹号 点否定的东西呢？ 它说[听不清]表示不。 因此，如果我们看一下刚刚 这部分在这里，你会 说，计算结果为 只要你想为false。 不是假的是真的， 这意味着将执行。 这是否有道理？ 学生：是啊。 讲师：真棒。 行。 因此，我们可以只返回 真在这种情况下。 所以，现在我们有两个 例在这种情况下。 什么是我们的另外两个情况？ 让我们只是做这种方式。 所以，让我们开始其他 如果在中间值 不到我们想要的值。 所以我们在中间的值小于 不是我们要寻找的价值。 那么，哪绑定你 我们认为要更新？ 上或下？ 上？ 因此，该阵列的一侧 我们将要在看什么？ 学生：下部。 教师：我们岂不是 可以看左边。 所以，如果别人没有什么价值较少。 所以，你的中间值在这里 不到我们想要的。 因此，我们要采取 右侧我们的阵列。 所以，我们要 更新我们的下界。 因此，我们将重新分配我们的低。 那你觉得下应该是什么？ 学生：中间值？ 讲师：所以中间value-- 学生：加1。 讲师：--plus 1。 谁能告诉我为什么 我们有一个加1？ 学生：[？没有价值？] 更等于它。 指导老师：对。 因为我们已经知道， 我们的中间值不等于 它和我们要排除 所有后续搜索。 如果你忘了加1，这 会喜欢无限循环。 而你只是陷入了 无限循环，然后你​​就会出现段错误 而事情变坏。 因此，始终确保你不 其中包括价值，你只是 看了看。 因此，我们照顾与加1。 所以，现在我们有我们的最后一个条件 我总是为了安全着想 您可以点击这里，否则，如果在值 中间的是大于该值 我们想要的。 这意味着，我们要 左手一半。 那么，哪一个我们要更新？ 上。 什么是这个打算一样的吗？ 中间减1，因为， 当然，我们要 以确保我们不 再看那中间值。 然后，我们有它。 就是这样。 这是所有的二进制搜索。 这并不是说不好，对不对？ 这就像10行 用空格代码。 所以很强大，很实用，你会 在你以后的pset中的一个使用它。 也许不是这一个，但后来。 所以，学习它。 爱它。 它会善待你。 因此，没有人有任何 在二进制搜索的问题？ 是的。 学生：它的问题 您是否n为偶数或奇数？ 导师：第 因为我们投它中间的 一个int，它只会截断。 所以它会留一个整数，它会 通过一切最终排序。 所以，你不必担心。 大家好？ 真棒。 凉爽。 所以，你们得到这个。 幻灯片。 因此，当我们在谈论，我知道 大卫提到的复杂的运行时间。 因此，在最好的情况下，它只是 1，我们称之为恒定时间。 谁能告诉我为什么，可能是？ 什么类型的场景会是意味着什么？ 嗯。 学生：[听不清] first-- 讲师：所以中间作为 我们来到了第一个元素，对不对？ 这样的一个数组或 无论我们正在寻找的只是 正好是在中间嫌民建联。 所以这是我们最好的情况。 你进入真正的问题，恐怕不是 要达到[听不清]经常。 那么我们最坏的情况？ 我们最糟的情况是日志ñ。 并且，是因为有全 两件事，我谈到的权力。 所以在最坏的情况下这将意味着 我们不得不砍了下来阵列 直到它是1的一个元素。 因此，我们不得不砍了下去一半 因为很多时候，我们可能会。 这就是为什么它的日志N，因为 你只是保持除以二。 所以假设，你的东西 要知道，如果你曾经 要使用二进制搜索。 你必须元素进行排序。 他们进行排序，因为 这是你唯一的出路 可以知道，如果你能 扔了出来一半。 如果你有这个混乱的包包 号码和你说， 好了，我要去检查中间 号码和我正在寻找数 小于说，我只是去 随意扔掉一半。 你不会知道你的 在另一半的数字。 列表中的排序。 同样，这可能是 要提前一点点， 但你需要有随机访问。 你需要能够公正 去那个中间的元素。 如果你必须遍历 通过什么 或者你花额外的步骤 去了中间的元素， 它没有日志N了，因为 您要添加更多的工作了进去。 这将使一点 在两周更有意义， 但我就是那种想要前言， 给你们一个什么样的想法 来。 但就是这两种 重要的假设 你需要一个二进制名单。 请确保它的排序。 这是大个的 你们现在。 和我们能进入 我们各种各样的休息。 所以4选择产品类别泡沫， 插入，选择和合并。 他们都很酷。 如果你们决定采取CS 124， 您将了解各种不爽。 如果你是一个XKCD风扇，有 是一个非常酷的漫画有关 就像真的无效的种种，我 强烈建议你去看看。 其中之一是喜欢那种恐慌，这 就像是，哦，不，返回随机数组。 关闭系统。 离开。 所以古怪的幽默总是好的。 因此，没有人记得那种 像只是一个总体思路 如何冒泡排序工作。 你还记得吗？ 学生：是啊。 讲师：大胆试试吧。 学生：所以你要通过和 如果是做大，那么你交换两个。 指导老师：嗯。 没错。 所以你只要遍历。 您检查两个数字。 如果前一个比较大 比一算账， 你只要将它们使得在 这样一来所有的高数 气泡向着列表的末尾向上 和所有的数字低泡下来。 他有没有告诉你家伙很酷 音效分拣的视频？ 这是一种很酷的。 所以罗伯特刚才说的，该算法 您在列表中只是一步， 交换相邻的值 如果他们不正常。 然后自顾自地重复 直到你不作任何交换。 所以，还不错吧？ 所以我们只需要一个简单的例子在这里。 所以，这是怎么回事排序 他们按升序排列。 所以，当我们经过第一 时间，我们期待通过八个 六显然不 为了我们交换它们。 所以，看看下一个。 八，以4没有。 交换它们。 然后8两，交换它们。 在那里，我们走了。 所以，你第一遍之后，你 知道你最多 将是一路 在顶部，因为它只是 要不断地 比一切更大 它只是将泡沫 向上一路到底那里。 这是否有道理给大家？ 凉爽。 所以，接下来我们来看看我们的第二次。 6个和4，开关。 六两，开关。 现在我们有为了几件事情。 因此，对于每一个传球，我们 让我们的整个列表， 我们知道，像许多号码 在年底将被排序。 所以我们做了第三次， 这是一个交换。 然后在我们的第四个 过去，我们是零插槽。 因此，我们知道，我们的 数组已排序。 那就是大 与冒泡排序的事情。 我们知道，当我们 具有零掉期，即 意味着一切 是完整的订单。 这是一种怎样检查。 因此，我们也要去泡代码 排序也并不坏。 这些都不是那么糟糕。 我知道他们看起来有点吓人。 我知道，当我把 类，甚至当我 教的班 第一次，去年， 我当时想，我该怎么办呢？ 是有意义的理论，但 我们如何真正做到这一点？ 这就是为什么我还不想走 通过与你们这里的代码。 所以，我有一个伪 对你们这段时间。 因此，只要记住这一点作为 我们要转型了。 因此，我们有一些反了 让我们的掉期交易的轨道， 因为我们需要确保 我们正在检查。 我们遍历整个数组 因为我们只是做了这个例子。 如果元素之前大于 之后，我们是在元素， 我们交换他们，我们增加我们的 计数器，因为只要我们交换， 我们要让我们的柜台都知道。 有什么问题吗？ 有些事情似乎好笑在这里。 学生：你设置计数器为零 每次经过循环？ 难道你不坚持下去 回零每次？ 讲师：不一定。 那么，什么情况是我们经过这里。 所以，做一段时间，记住，这 将执行一次没有失败。 因此，它会设置 计数器等于零， 然后，它会遍历。 由于它遍历， 它会更新计数器。 由于它更新计数器，当它完成， 当它到达数组的末尾， 如果我们的名单还没有被排序， 计数器将被更新。 那样的话就检查情况，并 说，OK，就是柜台大于零。 如果是，再这样做。 要重置，这样，当你 经过，计数器等于零。 如果你通过一个排序 阵，没有什么变化， 失败了，你 返回的排序列表。 这是否有道理？ 学生：它可能在一点点。 讲师：OK。 如果有任何其他 问题的出现。 是的。 学生：你会的功能 对于交换的元素呢？ 讲师：所以我们其实可以写 如果我们现在要的权利。 凉爽。 所以，关于这一点，艾莉森是怎么回事 切换回设备。 这将很有趣。 我们有我们的好 在这里冒泡排序的事情。 所以，我已经做了骑自行车 通过该阵列。 我们有我们互换了 都等于零。 因此，我们要交换相邻 元素，如果他们太过份了。 所以，第一件事，我们需要 做的是通过我们的数组遍历。 那么，你如何认为我们也许 通过我们遍历数组？ 我们有和我等于0。 我们希望我要少 大于n减1负ķ。 我会解释说，在第二。 所以这是一个最优化在这些地方， 记得我每次传球后是怎么说的 通过数组我们 知道什么是on-- 打完一遍我们 知道这是排序。 经过两道我们知道 这一切进行排序。 经过三关我们 知道的排序。 所以，我现在的迭代 通过阵列这里， 是它确保只有走 通过我们所知道的是未排序的。 行？ 这只是一个优化。 你可以写它只是天真 通过迭代的一切， 它只是需要更长的时间。 与此四环路是 一个不错的优化 因为我们知道，以后每满 通过数组迭代这里， 喜欢这里的每一个完整的循环，我们知道 一个多这些元素 在最后进行排序。 所以我们不必担心这些。 这是否有道理给大家？ 很酷的小把戏？ 因此，在这种情况下，如果 我们通过迭代， 我们知道，我们要检查 数组n和n加1是为了。 行。 因此，这里的伪代码。 我们要检查数组ñ 和N加1是为了。 那么，什么可能我们有吗？ 这将是一些条件。 这将是如果一个。 学生：如果array n是 比数组n与1少。 指导老师：嗯。 那么，小于或大于。 学生：大于。 然后，我们要交换他们。 没错。 所以，现在我们进入有什么 机制交换呢？ 因此，我们通过这个简短去了， 一种交换功能的最后一周。 有谁还记得它是如何工作的？ 因此，我们不能只是重新分配，对不对？ 因为其中一人将得到丢失。 如果我们说，A等于B，然后B 等于A，突然两个人 只是等于B. 所以，我们要做的是我们 有一个临时变量，是 将要举办的我们，而一个 我们在交换的过程中。 所以，我们所拥有的是我们​​有一些INT 温度等于to--你可以指定它 到任何一个你想要的，只是 请确保你跟踪它 - 的 所以在这种情况下，我要去 它分配给数组n与1。 所以这是将要举办什么 值是在该第二块 我们正在寻找。 然后我们可以做的是，我们可以去 提前并重新分配数组n与1， 因为我们知道，我们 有存储该值。 这也是大的一个 things--我不知道你们中的任何 曾：如果你切换的两个问题 代码行突然事情的来龙去脉。 为了在CS非常重要的。 所以一定要确保你关系图 事情是否可能 至于什么是实际发生的事情。 所以，现在我们要 重新分配数组n与1， 因为我们知道，我们 有存储该值。 我们可以将它赋值给数组 在这种情况下，阵列I n或。 太多的变数。 行。 所以，现在我们已经重新分配数组我 加1等于什么阵我。 现在我们可以回去 分配数组我的是什么？ 任何人吗？ 学生：10。 讲师：10。 没错。 而最后一件事。 如果我们现在已经换了， 什么，我们需要做什么？ 什么是一件事 这是怎么回事告诉我们 如果我们终止这项计划？ 什么告诉我们 有一个排序的列表？ 如果我们不进行任何交换，对不对？ 如果互换等于 在此结束零。 所以每当你完成一个交换，因为我们 只是在这里做，我们要更新掉。 我知道有一个 刚才的问题能左右你 用零次或一次，而不是 true或false。 而这正是这并不在这里。 因此，这如果不是掉期说。 所以，如果掉期为零，这is--我总是 让我的真理，我falses混淆。 我们希望我们能够评估 以真实，事实并非如此。 所以，如果是零，那么它是假的。 如果你有一个否定它 [？一声？]成为事实。 那么接下来这条线执行。 真理与虚假， 零和一弄疯了。 只是，如果你慢慢走 通过它它才有意义。 但是，这就是这个小 代码位在这里呢。 因此，这将检查 我们做任何交换。 所以，如果它的任何东西，除了 零，这将是错误的 而整个事情是 要再次执行。 酷？ 学生：什么突破呢？ 讲师：刚刚突破 打破你跳出循环。 所以在这种情况下，它会 只是想结束程序 而你只想 有你的排序列表。 学生：惊人的。 讲师：对不起？ 学生：因为以前我们 用过写1比写零 提出，如果 将工作或没有。 指导老师：是啊。 所以，你可以返回零个或1。 在这种情况下，因为我们没有真正 做什么用的功能， 我们只是希望它打破。 我们真的不关心它。 刹车也不错，如果 它是用于突破 四个环或条件的那 你不希望继续执行。 它只是需要你了出来。 这是一个有点细微的事情。 我觉得有 很多摆手的， 就像你将了解这一声。 但是，你将了解这一声。 我保证。 行。 因此，每个人都得到冒泡排序？ 差不太多。 遍历，使用交换的东西 临时变量，我们都设在那里？ 凉爽。 真棒。 行。 回到PowerPoint文件。 一般来说任何问题 这些这么远吗？ 凉爽。 嗯。 学生：[听不清]诠释主通常。 你必须有这个？ 讲师：所以我们只是在寻找 只是在实际的排序算法。 如果你在有它 像一个更大的程序， 你将有一个int的主要地方。 这取决于你在哪里 使用这种算法， 这将决定什么 由它返回。 但对于我们而言，我们是严格 着眼于如何真正做这个 遍历数组。 所以，我们并不担心。 因此，我们在谈论最好的情况和 最坏的情况下为二进制搜索。 因此，这也是非常重要的做 对于每一个我们的排序。 所以你认为是什么做的是最差的 冒泡排序的情况下运行？ 你们还记得吗？ 学生：N减1。 讲师：N减1。 因此，这意味着有 ñ减1的比较。 所以，有一点认识是 即在第一次迭代中， 我们经历，我们比较 这些two--所以这是1。 这两个，三个，四个。 所以一次迭代后，我们 已经有四个比较。 当我说的是运行和n。 N表示比较的数量 有多少元素的函数 我们有。 行？ 因此，我们过不去，我们有四个。 下一次当你知道我们不 要利用这一服务。 我们比较这两个， 这两个，这两个， 如果我们没有这个优化 与四循环，我写的， 你会比较这里反正。 所以，你必须 通过阵列上运行 而从N比较ñ 次，因为每次我们 运行通过它我们排序的一件事。 每次我们通过运行时间 数组，我们从N比较。 因此，我们运行的是 实际上Ñ平方，其中 是更糟糕了 日志末尾，因为这 也就是说，如果我们有四个 十亿元素，它的 我们要花费four十亿 平方，而不是32。 所以不是最好的运行时间， 但对于某些事情， 你知道，如果你是内 在一定范围内的元素 冒泡排序可能会比较好用。 行。 所以，现在什么是最好的情况下运行？ 学生：零？ 还是1？ 教师：那么1人 是一次比较。 右。 学生：N减1？ 讲师：所以，是的。 因此n减1。 当你有一个像N A概念 减去1，我们往往只是把它关闭 我们只说N，因为你有 比较每个these--每对。 所以它会为n减去1，这是我们 我们刚刚说的是大约ñ。 当你正在处理的运行时间， 一切都在接近。 只要指数是 正确的，你很不错。 这就是我们如何处理它。 所以，最好的情况下是n，这 意味着该列表已经排序， 而我们要做的就是通过运行 并检查它的排序。 凉爽。 行。 所以，当你看到这里，我们 只是有一些更多的图形。 因此n的平方。 好玩的。 远小于n更糟，因为我们看到了， 多，比数2n个糟糕得多。 然后你也进入日志记录。 你拿124，你进入 像日志的明星，这是像疯了似的。 所以，如果你有兴趣， 查询日志的明星。 这是一种乐趣。 因此，我们有这个伟大的图表。 只是抬起头，这是一个 精彩图有 为您的中期，因为我们 长问你这些变薄。 所以才抬起头来，这个对你 对你的好小抄中期 那里。 所以，我们只是看着冒泡排序。 最坏的情况下，N的平方，最好的情况下，N。 而且我们要看看其他人。 正如你所看到的，唯一的 一个真正做得好 是归并排序，我们将进入的原因。 所以我们要去的 下一个这里 - 选择排序。 有谁还记得 选择排序工作？ 去了。 学生：基本上经历 一种秩序，创造一个新的列表。 而且，正如你把元素 中，把他们在正确的地方 在新的清单。 讲师：这样的声音 更像是插入排序。 但是你真的很近。 他们是非常相似的。 就算我让他们混在一起的时候。 这部分我像以前一样，等待。 行。 所以，你要 做的是选择排序， 你能想到的方式 它和方式 我要确保我尽量不要让 它们混合起来，是它通过 的情况下选择 最小数目和它 提出，在列表的开头。 它交换它与第一点。 他们居然对我有一个例子。 真棒。 所以，只是一个方式去思考它 - 选择 排序，选择最小的值。 而我们要 通过一个实例运行 我认为这将有助于因 我觉得视觉效果总是帮助。 因此，我们的东西开始了 这是完全无序。 红会未排序的， 绿色进行排序。 它将所有的意义在第二。 所以，我们通过我们遍历 从开始到结束。 我们说好，2 我们最小的号码。 因此，我们要采取2，我们要 将它移动到我们的数组的前面 因为它是 最小数，我们有。 所以，这就是这是在这里做。 它只是要交换这两个。 所以，现在我们有一个排序 部分和未分类的一部分。 什么是好记 关于选择排序 是我们唯一的选择 从无序的一部分。 排序的一部分，你只是独自离开。 嗯？ 学生：它是如何知道什么是 最小无它比较 到阵列中的每一个其它值。 讲师：它确实进行比较。 我们喜欢跳过它。 这只是一般的整体。 是啊。 当我们编写我的代码 相信你会更加满意。 但是，你保存这第一 元件为最小。 你比较，你 说好，是不是更小？ 是的。 保留它。 这里是小？ 不是吗？ 这是你最小， 它重新分配给你的价值。 你会感到非常的快乐 当我们通过代码。 因此，我们过不去，我们交换了，所以再 我们看一下这个排序的部分。 所以，我们要选择三个出来。 我们打​​算把它在 我们的排序的部分的端部。 而我们只是要继续做 这，做那，而这样做。 因此，这是我们的一种伪这里。 我们将在这里编写它在一秒钟。 但只是一些走 通过在一个高的水平。 你会从去 i等于0到n减去2。 这是另一种优化。 不要太担心了。 所以，当你在说什么。 正如雅各说，我们怎么 跟踪我们什么是最小的？ 我们怎么知道？ 我们来比较 一切都在我们的名单。 因此，最小等于我。 它只是说，在这种情况下， 我们的最低值的索引。 这样的话它会遍历 而它从j为我加1。 因此，我们已经知道， 这是我们的第一个元素。 我们不必把它比作自己。 所以，我们开始把它比作下一个 1这就是为什么它是我加1到n 减1，这是 阵列那里的端部。 我们说，如果数组 j是小于阵列分钟， 那么，我们在那里重新分配 我们的最低指标是。 而如果分不等于i，如 在这里我们又回到了这里。 所以像我们当初做这个。 在这种情况下，它会开始 零，这将最终被两人。 所以分也不会等于我到底。 让我们知道， 我们需要交换它们。 我觉得自己像一个具体的例子 将帮助远不止此。 因此，我将这个代码与你们 现在，我认为这将是更好的。 排序往往工作方式在 它往往只是为了更好地看到它们。 所以我们想要做的是 我们首先需要的最小 元件在它的阵列中的位置。 正是雅各说的话。 你需要存储，不知怎的。 因此，我们要在这里开始 遍历数组。 我们会说这是我们的 第一次只是开始。 因此，我们将不得不INT 最小等于阵列在岛 所以，有一点要注意，每 这个时间循环执行， 我们开始一起又进了一步。 当我们开始我们看这一个。 接下来的时间，我们遍历， 我们已经开始在这一个 而分配给它我们的最小值。 所以这是非常相似的冒泡排序 我们知道，一个传球后， 这最后一个元素进行排序。 与选择排序， 它正好相反。 在每一个传球，我们知道， 第一个是排序。 第二次通过后，将 第二个将被排序。 正如你看到的幻灯片的例子， 我们来分类的部分只是不断增长。 因此，通过设置我们最小的一个 到数组我，所有它做 收缩是什么 我们正在寻找这样 最小化的数量 比较我们做。 这是否有意义大家？ 你需要我通过运行 再慢，或者在不同的话吗？ 我很高兴。 行。 因此，我们的存储 在这点上的值， 但是我们也希望来存储索引。 所以我们要保存 最小的位置 1，这是只是要我。 所以，现在雅各是满意的。 我们所储存的东西。 现在我们需要看看通过 阵列的未分类的一部分。 所以在这种情况下，这 将是我们未排序的。 这就是我。 行。 所以，我们要做些什么 将是一个循环。 每当你需要 遍历数组， 你的头脑会去为一个循环。 因此，对于一些INTķ equals--什么，我们认为 k被要等于开始？ 这是我们设置了最小 价值，我们要进行比较。 我们究竟要比较它？ 这将是该下一个，对不对？ 所以我们要k，进而进行初始化 要我加1开始。 我们希望K的这种情况下，我们 已经存储的大小在这里， 所以我们可以只使用尺寸。 大小作为数组的大小。 我们只是想 一，每次更新ķ。 凉爽。 所以，现在我们需要找到 这里的最小元素。 因此，如果我们遍历，我们 想说，如果数组日K 小于我们最小value-- 这就是我们实际上 跟踪是什么 最小这里 - 那么我们要重新分配 就是我们最小的值是。 这意味着，哦，我们是 迭代经过这里。 无论值是这里 不是我们最小的事情。 我们不希望它。 我们要重新分配它。 所以，如果我们要重新分配它，做什么 你觉得可能是这里的代码？ 我们要重新分配 最小的位置。 还等什么，现在是最小的？ 学生：列K。 讲师：列K。 是什么位置呢？ 什么的指数 我们最小的价值？ 它只是ķ。 所以列K中，k，它们相匹配。 因此，我们要重新分配。 再之后，我们发现我们最小的， 因此在今年年底for循环 在这里我们找到了我们的最小 值，所以我们只是换了。 在这种情况下，像说我们的 最小值是出在这里。 这是我们的最小值。 我们只是想在这里交换，这是 是什么在底部的交换功能 的确，这是我们刚刚写了 同时几分钟前。 所以它应该很熟悉。 然后它只会重复 通过直到它到达一路 到结束，这意味着你 具有零个元素是无序 和其他一切已排序。 有意义吗？ 有一点更具体？ 该代码的帮助？ 学生：对于一个规模，你永远不 真正定义它或改变它， 它是怎么知道的？ 教师：那么一回事， 注意在这里为int的大小。 所以我们说在这个类别 - 排序 是在这样的函数case--它 选择排序，它通过 同的功能。 所以，如果它没有通过 中，你会做什么 像与所述阵列的长度 或者你会遍历 找到的长度。 但由于它的传递 中，我们可以只使用它。 你刚才假设用户 给你一个有效的尺寸 实际上代表 一个大小的数组。 酷？ 如果你们有这些任何麻烦 还是要多练编码排序 在你自己的，你应该 去study.cs50。 这是一个工具。 他们有一个检查器 你其实可以写。 他们这样做伪。 他们有更多的视频和幻灯片 包括那些我在这里使用。 所以，如果你仍然感觉 有点模糊，尝试了这一点。 与往常一样，来和我说话了。 问题？ 学生：你说的 大小是预先定义的？ 指导老师：是的。 大小是预先定义了 这里的函数声明。 所以，你认为它已经通过了 由用户，并且为简单起见， 我们将假设 用户给了我们正确的大小。 凉爽。 所以这是选择排序。 伙计们，我知道我们今天学习了很多。 这是一个密集的数据部分。 于是就这样，我们将 去插入排序。 行。 所以，在这之前，我们需要做的 我们这里的运行时分析。 所以，在最好的情况下， 理所当然，因为我给你 表我已经 种就将它丢弃。 但是，最好的情况下运行时，我们会怎么想？ 一切都来分类的。 Ñ​​平方。 任何人都有一个解释 为什么你觉得呢？ 学生：你比较through-- 指导老师：对。 你比较过。 在每一次迭代中，即使 我们正在递减这一个， 你还在寻找通过 一切都找到了最小的一个。 所以，即使你的最小值 就是在这里开始， 你还在比较其 反对一切 以确保它是最小的事情。 所以，你最终会通过运行 大约ñ平方倍。 行。 什么是最糟糕的情况？ 也可为N的平方，因为你会 在做了同样的过程。 所以在这种情况下，选择 排序有什么 我们也呼吁预期运行。 因此，在别人，我们只知道 的上限和下限。 这取决于如何疯狂我们 列表或者如何排序的是， 它们n或n的平方之间变化。 我们不知道。 但由于选择排序有相同的 最坏和最好的情况下，这告诉我们， 无论输入什么类型的，我们 有，无论是完全 排序或完全 反向排序，这是 要采取的相同的时间量。 因此，在这种情况下，如果 从表中我们还记得， 它实际上有一个值，该值 这两类没有， 这是预期运行。 所以我们知道，每当 我们运行选择排序， 它保证 运行一个n的平方时间。 没有可变性存在。 这只是预期。 并再次，如果你想学习 更多的，拿CS 124的春天。 行。 我们已经看到了这一点。 凉爽。 所以插入排序。 而且我可能会 走出一条通过此。 我不会有你们编写它。 我们将步行穿过它。 所以插入排序是怎么样 类似于选择排序 在我们有两个未排序 和排序的阵列的一部分。 但不同的是， 因为我们通过一个接一个， 我们只取什么数 接下来是我们未排序的， 并正确排序 到我们的排序的数组。 它会更有意义，用一个例子。 所以一切开始作为未分类， 只是想用选择排序。 而我们要在此排序 升序因为我们一直。 因此，我们第一遍 我们采取的第一个值 我们说好，你是 现在在列表中自己。 因为你是在一个列表 由自己，你的排序。 恭喜您成为了 此数组第一个元素。 你已经排序的所有靠自己了。 所以，现在我们有一个排序 和一个未排序的数组。 所以，现在我们采取的第一个。 在此之间会发生什么 这里就是我们说的， OK，我们要去看看 我们排序的数组的第一个值 而且我们要投入在其 正确的位置排序数组中。 所以，我们要做的是，我们采取5 我们说好，5大于3， 所以我们只是将它的权利 到的，该权利。 我们是很好的。 那么接下来，我们继续我们的下一个。 我们采取2。 我们说好，2少 比3，所以我们知道它 需要是在 我们的名单前面了。 所以，我们做的是我们推3和5下 我们提出2成第一个插槽。 所以，我们只是将其插入 正确的位置是应该的。 然后我们来看看我们的 下一个，我们说6。 行，6大于 一切都在我们的排序的数组， 所以我们只是将其标记到结束。 然后我们来看看4。 图4是小于6，就少 比5，但它是大于3。 所以我们只是把它插入到正确的 3和5之间的中间。 因此，为了使这一点 多一点具体的， 这里是怎么样的 想法发生了什么事。 因此，对于每一个未排序的元素，我们 确定在排序部分 它是。 所以，牢记 分类和未分类， 我们已经遍历和数字 出它的排序的数组能容纳。 我们通过移动插入 元素，它的降权。 然后，我们只是不停 通过迭代，直到我们 有一个完全排序的列表 其中，无序现在是零 和排序占用 我们的全部名单。 所以，再一次，为了让事情 更具体的，我们有伪代码。 所以基本上对我是 等于0到n减1， 这是我们阵中仅有的长度。 我们有一些元件，它等于 第一阵列或第一索引。 我们集合的J相等。 因此，虽然j大于 零和阵列，J减去1 大于 元素，让所有的做 为确保 您Ĵ真正代表 阵列的未分类的部分。 因此，尽管还有事 排序和j减一is--什么 是她的元素？ J以从来没有在这里定义。 这是一种烦人。 行。 反正。 所以Ĵ减1，你检查 之前的元素。 你说，OK，是元素 之前，无论我am--我们 实际绘制了这一点。 所以我们可以说，这是 就像我们的第二次。 所以我将是相等 为1，这是在这里。 所以我将是等于1。 这将是2，4，5，6，7。 行。 因此，我们在这种情况下，元素 将是等于4。 我们有一些Ĵ这 将等于1。 哦，j被递减。 那它是什么。 所以j等于我，所以这个是什么 说的是，我们向前迈进， 我们只是要确保 我们不是在 索引这样，当我们试图 插入的东西到我们的排序列表。 因此，当j等于1在这种情况下，与 阵列Ĵ减埃德蒙顿所以数组Ĵ减1 2本case--如果这就是 大于所述元件， 那么这一切是做 被转移下来。 所以在这种情况下，阵列Ĵ减一 将阵列为零，这是2。 图2为不大于4， 所以这不会执行。 这样的移位，并不会向下移动。 这里做的事情在这里只是 移动你的排序的数组下来。 在这种情况下，实际上，我们 可以do--让我们做这3。 所以，如果我们穿行与 这个例子，我们现在在这里。 这是排序。 这是未排序的。 酷？ 所以i等于2，所以 我们的元素等于3。 与我们的j等于2。 因此，我们期待通过我们 说好，是数组Ĵ减一 大于所述元件 那我们看什么？ 答案是肯定的，对不对？ 图4是大于3和j 是2，那么该代码执行。 所以，现在我们做的一个数组 2，所以在这里，我们交换它们。 所以，我们只是说，OK，阵列 2，现在将是3。 和j是要等于 Ĵ减1，为1。 这是可怕的，但 你们的想法。 J是现在等于1。 和阵列j的只是要 等于我们的元件，为4。 我删除的东西我不应该 有或miswrote东西， 但是你们的想法。 它移动以n。 然后，如果这是，它会循环 再次，它会说，OK，j是1了。 和阵列Ĵ减1现在是2。 2小于我们的元素？ 不是吗？ 这意味着，我们已经 插入这个元素 在我们排序的数组中的正确位置。 然后，我们就可以利用这个和我们说， OK，我们的排序的数组是在这里。 它会采取这个数字6，并 就像，OK，比这个数少6？ 不是吗？ 凉爽。 我们很好。 再次这样做。 我们说7。 比所述端部7少 我们的排序的数组？ 号 所以，我们很好。 所以这将被排序。 基本上，这一切确实 它是在说拿 的第一个元素 您排序的数组， 找出通向哪里 在排序的数组。 而这只是照顾 掉期来做到这一点。 你基本上只是交换 直到它在正确的位置。 视觉形象是你 移动都记录下来做的。 所以，这就像半冒泡排序式的。 退房研究50。 我强烈建议尝试 编写这个你自己。 如果您有任何问题，或者您想 参见示例代码插入排序， 请告诉我。 我总是四处。 因此，最坏的情况下运行 和最好的情况下运行。 当你的家伙从表中看到，我已经 表现出你，这既是ñ平方和n。 种这么打算过什么，我们聊 关于我们以前的种种，最糟糕的 情况下运行时，如果 它是完全不排序， 我们必须比较所有这些n次。 我们做了一大堆的比较 因为如果它以相反的顺序， 我们会说，OK，这 是相同的，这是很好的， 而这一次将要被比较 相对于第一个要被移动回。 而且随着我们走向 尾部，我们有 比较，比较和 与之比较的一切。 因此它最终被 大约Ñ平方。 如果它是正确的，那么你 说好，2，你是​​好。 3，你比2。 你很厉害。 4，你只是比较的尾巴。 你很厉害。 6，比较的尾巴，你的罚款。 因此，对于每一个点，如果它已经 排序，你正在做一次比较。 所以它只是ñ。 因为我们有最好的情况下运行 n及n的最坏情况的运行时的 方，我们也没有预期的运行。 这只是取决于 乱我们的名单中出现。 又一次，另一 图形和另一个表。 所以各种各样的差异。 我只是微风过，我 感觉我们已经谈过了广泛 有关他们都怎么样 的变化，并且连接到一起。 所以合并排序是最后一个 我要你承担家伙。 我们也有一个漂亮的多彩画卷。 所以，归并排序是递归算法。 所以，不要你们知道是什么 递归函数是？ 任何想说的？ 你想试试吗？ 因此，一个递归函数就是 一个函数调用自身。 所以，如果你们熟悉 与斐波那契序列， 该公司认为，因为递归 你把前面的两个 并把它们相加 让你的下一个。 这样循环，我一直认为 递归如像一个螺旋形的 所以你像螺旋式下降了进去。 但它只是一个功能 调用自身。 而且，实际上，真的很快我 可以告诉你那是什么样子。 所以递归这里，如果我们看，这是 递归的方式来总结一个数组。 因此，所有我们要做的就是 我们有求和函数 总之，需要一个大小和数组。 如果你注意到，大小 减一各一次。 和所有它的作用是，如果x等于 zero--因此，如果该数组的大小 等于zero--返回零。 否则，这个总结 所述阵列的最后一个元素， 然后采取的总和 该阵列的其余部分。 所以它只是将它分解 成越来越小的问题。 长话短说，递归， 函数调用自身。 如果这是你离开了这一点， 这就是一个递归函数。 如果你51，你会得到非常， 很舒服的递归。 这真的很酷。 它以有意义像 上午03点一晚了。 我当时想，为什么 我也从来没有用这个？ 因此，对于归并排序，基本上 什么是要做的是它的 要打破它，打破它 直到它只是单一的元素。 单个元件很容易就可以进行排序。 我们看到这一点。 如果你有一个元素，它的 已经考虑排序。 等n个元素的一个输入端， 如果n小于2， 刚回来，因为那意味着 它是0或1，因为我们已经看到了。 那些被认为是排序的元素。 否则，打破它的一半。 排序上半年，排序第二 一半，然后将它们合并在一起。 为什么它被称为归并排序。 所以，我们在这里，我们将整理这些。 因此，我们继续让他们 直到数组大小为1。 所以，当它的1，我们只返回 因为这是一个排序后的数组， 这是一个排序的数组，而这 一个排序的数组，我们都来分类的。 那么接下来我们要做的是我们 启动它们合并在一起。 所以，这样就可以 想想合并是 你只是删除小 各子阵列中的数 而只是将其追加到数组中出现。 所以，如果你看看这里，当我们有 这些集我们有4,6和1。 当我们要合并这些， 我们看一下前两个 我们说好，1越小， 它会向前方。 4和6，有没有什么比较 它，只是将其标记上到结束。 当我们结合这两个，我们只是 取这两个中较小的一个， 所以它的1。 现在我们采取的 这两个，所以2的小。 这两个，3个较小的。 这两个，4，5，6以下。 所以，你刚才拉过这些。 而且由于他们把 以前被排序， 你只有一个 比较有各一次。 因此，更多的代码在这里，只是表示。 所以你在开始，中间和 您排序左右 然后你只要这些合并。 我们没有代码 对于合并就在这里。 但是，再说一次，如果你去上 研究50，它会在那里。 否则，来跟我说话 如果你还在迷茫。 因此，这里很酷的事情是最好的情况下， 最坏的情况下，与预期的运行时 都在日志中N，其中 远不如我们已经 看到了我们各种各样的休息。 我们已经看到ñ平方 而其实我们 拿到这里的n log N，这是伟大的。 看看这是多么要好的多。 这样一个漂亮的曲线。 因此，更有效。 如果你可以，使用归并排序。 这将节省您的时间。 话又说回来，正如我们所说的，如果 你倒在这个较低的地区， 它不会作出这样的 多大的差别。 你得到多达数千 和数以千计的投入， 你一定要一个 更有效的算法。 并再次，我们可爱的表 各种各样，你们今天学到。 所以，我知道这是一个密集的一天。 这不一定要去 帮助您与您的PSET。 但我只想做一个免责声明 该节不只是pset中。 所有这些材料是公平的 游戏中为你的期中考试。 而且如果你继续用CS， 这些都是非常重要的基础 你需要知道的。 所以，有些日子将是一个 多一点PSET的帮助， 但几个星期会 更多的实际内容 这似乎并不超 现在对你有用， 但如果你继续我答应 上会非常，非常有用。 所以这是它的一节。 下来的电线。 我做了一分钟之内。 但你去那里。 我也有甜甜圈或糖果。 有没有人过敏 任何事情，顺便？ 鸡蛋和牛奶。 因此，甜甜圈是一个没有？ 行。 行。 巧克力不？ 星爆。 星形图案都不错。 行。 我们将有 下周爆吧。 这就是我去拿。 你们有一个伟大的一周。 看了你的天赋。 让我知道，如果你有任何问题。 PSET两个档次应该是 出来给你周四。 如果您有任何问题 我是如何分级的事情 为什么我的东西渐变的方式，我 没有，请给我发电子邮件，来和我说话。 我有点疯了这 一周，但我保证 我仍然会在24小时内回复。 所以，有一个伟大的一周，每一个人。 祝你PSET。