大卫马兰：好吧。 所以这是CS50，这是 现在3周的开始。 所以到现在为止，我们已经 在写程序用C 这看起来有点 这样的事情在这里。 所以，我们有几个 尖锐包括在顶部。 我们已经得到了诠释，主要的，无效的，并 然后事情做在中间， 一些代码位内 的该功能。 但重点一直事实 我们一直在说空在这里。 因此作废，这一切的时候，指定 这个程序在运行时， 只能通过其名称来运行。 你不能输入其他文字或 该程序的名称时数后， 运行它。 因此，例如，如果节目是 编译成一个名为hello的文件， 你可以做./hello，但就是这样。 唯一的办法，你可以 提供输入到该程序 是通过调用一个函数。 例如，什么功能 使用迄今还我们一直 以获得来自用户的输入？ 听众：获取字符串。 大卫马兰：要获得字符串，或 得到int或你见过其他人， 即使你没有使用它们， 喜欢弄长，长，等等。 但是，假如我们 其实要开始 编写程序是多一点 多才多艺，而且，坦率地说，多一点 就像你已经命令 已经越来越有希望， 有点习惯了。 如CD空间的Dropbox。 此，当然，改变 您的目录，假设 你在约翰·哈佛的家 目录到你的Dropbox文件夹。 同时，这样的命令 创建一个名为pset2新目录， 正如你可能已经或 很快就会在问题设置两个。 当然，做出喂，是一个命令 即建立了一项名为招呼 从一个叫你好点C文件。 和在每个这些 的情况下，现在，我们已经有 在所谓的提供参数 命令行中，闪烁提示， 让化妆知道要建什么，等等 这MKDIR知道文件夹的创建， 和使坎德拉知道 您想去的地方。 但是到现在为止，我们一直在说 在主，您的默认功能， 有一个空洞的表达 这些括号内， 这意味着它 不带任何参数。 所以，从今天起， 我们要做些什么 是，我们要开始 支持这样的事情，甚至。 事实上，在这种情况下，你 通常不手动输入， 让一直在做这 对我们来说，有没有 之一，但一个，两个，三个附加 之后，该程序的命名字符串 铛。 那么，如何才能做到这一点？ 好了，从今天开始， 在这里我们要案件 通过提供输入 所谓的命令行 我们要开始添加 这里什么在yellow-- 与诠释的argc逗号代替无效 字符串argv的左括号右括号。 现在，这是有趣的 一对夫妇的原因。 一，这将让我们写 程序是多了几分动感。 不过，更令人信服， 这将打开 现在的对话，以 什么阵列可真 可以使用，什么串 真的是引擎盖下方， 等到下星期我们开始跳水 在更深层次，以机器是如何 让所有这些东西的工作。 但现在，让我们来画， 也许，一个图片。 当你写一个程序 与主声明 以这种方式，使得主 有两个参数，一个int 还有 - 什么样的数据类型 是第二个参数？ 听众：阵列。 大卫马兰：阵列。 所以，第一眼看上去就像是一个 字符串，但要注意的方括号。 还记得我们去年推出的时间 阵列的概念。 和数组使用方括号 在几个场合。 您可以使用方 括号去到一个数组 并获得一个特定的元素，如 支架0或1架或支架2。 但是我们看到，如果简单地说， 上周，你也 使用这些方括号 声明数组的大小， 如果你事先知道有多少个整数 或者有多少字符串或任何你 其实想。 因此，原来有 这里三分之一的上下文 这里面有没有一些 方括号。 当你指定，因为我这里有， 的类似的argv名称， 这只是一种奇特的方式 话说参数向量，这 是另一种奇特的方式 说的参数数组， 开放式托架右方括号只是 意味着你不一定 预先知道有多大 该阵列将是， 但你知道这将是一个数组。 所以，如果你不知道的 一些不把它放在那里， 开放式托架右方括号 也就是说argv是不是一个字符串， 但一个字符串数组。 所以，语法，如果你 回想上周， 这是非常相似的说法 像整型年龄开支架， 再以后的东西。 那么，这是什么样子的呢？ 让我们来实际绘制的图片。 所以，当你运行这个程序有主 有两个参数中定义 这些括号的，你 本质上具有至少两个组块 内存就交给你了 引擎盖下方。 一，我会为绘制这个矩形， 将要被调用的argc。 而只是作为一个快速回顾一下， 什么是ARGC的数据类型？ 所以这是一个int。 因此，一些会 走在argc--圈 出代表参数计数。 同时，我画的argv为数组。 我真的不知道 多久将是， 所以对于今天的目的，点点点。 它可能会得到一些长度。 但我在这里想象 至少四个矩形。 所以的argv内存存储块 串串串点点点， 和ARGC只是一大块 的存储器为一个整数。 所以，现在，让我们可以更确切的一点。 如果，当我有串 在这个数组，称为 ARGV，我想向他们 单独的，就像上​​周， 我们将要使用的符号 像argv的支架0 拿到的第一件事数组。 ARGV支架1得到 第二件事情，等等。 这里的关键是，我们还在0 indexed--我们仍然从0开始计数。 所以，现在让我们来实际 装上去的。 如果我要编译一个调用程序 你好，从一个叫你好点C文件， 然后我运行的程序 用点斜线您好， 什么我的电脑，我的笔记本电脑， 像机罩下方 那一刻我跑点 湿地打招呼，敲回车？ 那么，这也许是 我们可以描述 为您的计算机的内容 存储器，或RAM--随机存取存储器。 换句话说，计算机 不知怎么给你神奇， 放入的argc数字1，AKA argcount， 它把字面上的字符串 ./hello argv中支架0。 我不知道，坦白地说，有什么 argv中托架1或2或3， 因为如果用户具有不 什么类型除了./hello， 我们将假定这些 最有可能的垃圾值 可以这么说。 内存块的那些 存在的，但它不是我们 看着他们，因为 该argcount是唯一的一个。 现在，同时，如果我 编写运行另一个程序， CD，这是更适当的命令时， 在你眨眼prompt-- CD的空间 当我运行，有效地Dropbox--， 光盘程序运行时，argc个， 我的计算机的内存里面，是 最简短的第二数字2。 然后argv的支架O具有 CD，argv的支架1有Dropbox的， 然后当然命令 完成，所以这一切的记忆 基本消失， 用于别的东西。 这就是为什么我说 只是一个瞬间。 同时，如果我们做的mkdir pset2， 画面看起来几乎一样， 但里面的argv不同的字符串。 如果我做铛冲刺打招呼 你好点C，同样的想法。 更多的东西填充的 的argv和argc个，当然，是4。 因此，换句话说， 尽管这阵 可能会点一些点点， 可变长度的，可以这么说， 你总是知道它在哪里结束 是的，因为的argc是要告诉你 在什么时候你必须停止 看着argv中的元素。 你只能看4 在总在这种情况下。 现在让我们来看看， 也许，一个简单的程序。 一个刚刚打招呼 到有人喜欢Zamyla。 所以，我要求我要编写一个程序 在短短的一瞬间，通过它我可以做 ./hello空间Zamyla，然后我想 我的程序打印出来的东西 超级简单的像“你好，Zamyla。” 现在，在过去，我们使用的GetString。 因此，在过去，即使 你是新来编程， 可能你会掀起 使用GetString的程序 然后使用printf的 说喜Zamyla。 但是，我们不要用GetString的这个时候。 让我来代替进入Appliant 做包括标准输入输出点小时。 让我也有CS50网点小时。 现在主要的诠释，而现在我 不会今天做无效。 相反，我该怎么办INT ARGC 字符串的argv开括号右括号， 不指定一个数字。 喏，这就是我所谓的做。 我什么都现在要做的就是，我 打算做一点信仰的飞跃， 我将假设用户的 要正确地使用这个程序， 而我只是去 这样做的printf你好，％锡。 所以，没有什么新的存在。 但我想现在把什么字 该程序的名称后，用户类型。 所以，如果我这样做./hello空间Zamyla，我 要以某种方式编程方式访问 报价引文结束“Zamyla。”所以我 可以进入我的参数向量， 我的字符串数组，并且如果该命令 再次，是./hello空间Zamyla， 什么数字做我想要 argv中放这里？ 听众：1。 大卫马兰：1，因为 支架0证明 将是该 节目的名字，正如我们所看到。 所以托架1是第一个字 我的用户，键入。 我要继续前进，保存这个。 我要进入​​我的文件夹 在那里我已经放在这个文件。 我该怎么办让你好3。 比较IO的确定。 ./hello Zamyla输入。 我做了什么错？ 我措手不及 我自己只是一瞬间出现。 我做了什么错？ 听众：名称。 大卫马兰：该文件的 其实所谓的hello3.c。 我这样做只是为了 一致性，因为我们已经 有hello.c中的中 过去在联机代码。 因此，让我们解决这个问题./hello 支架冲刺3 Zamyla。 输入。 现在我们有打招呼，Zamyla。 同时，我可以改变这 是抢，还是真的任何其他文字。 但是，让我们考虑一个角落的情况下。 什么，你可能会想到，如果会发生 我不输入任何人的名字呢？ 听众：错误。 大卫马兰：错误 的一些，也许。 让我们来看看。 输入。 NULL。 所以printf的实际上是被 一点点保护我们 在这里，和字面移印开括号 空，但更糟糕的事情都可能发生。 而只是为了展示 东西你绝对 不该做的事，让我们在 在这里，并开始闲逛。 对不对？ 如果我知道，在画面 内存基本上是这样， argv的支架1具有Zamyla，ARGV 托架0具有./hello，或./hello-3。 什么是支架2？ 这样我就可以回答这个问题 怀疑自己，对不对？ 我只能改变1到2。 我现在可以重新编译您好3， ./hello3让我们放大并按下回车键。 哎呦。 没有引号。 有意思的。 所以这是一种很酷 看到的是在这里还有什么。 那么，我的笔记本电脑里还有什么？ 让我们将它保存与支架3。 请hello3，./hello-3。 好奇的。 现在，让我们真正bold-- 50。 所以，这真的跳水深 进入我的电脑的内存中。 50指数研究。 所以要喂3 ./hello-3。 好奇的。 好吧，现在我只是 要得到鲁莽。 让我们去到5000。 好吧。 因此，让我重新编译。 请hello3，./hello-3。 行。 现在，你们中的一些，可能 一个灯泡去了。 你们有多少人有 之前看过这个消息？ 行。 那么，为什么呢？ 赔率are--并有不同 事情可能会导致此， 并明确你的好 company--我们必须清楚 造成了所谓 分段故障。 而长话短说今天，我 已经触及记忆的片段 我不应该有。 其中段仅仅意味着一大块 记忆，我不应该有。 现在的电脑可以保证，如果我 运行./helloZamyla我能触摸的argv 是支架0和argv支架1。 但ARGC是值2，这意味着我 只有allowed--这有点荣誉 系统 - 触摸 0支架及支架1。 如果我再往前走，有 绝对将是存储器那里。 我的内存物理上存在 在计算机中。 但谁知道那里有什么？ 事实上，我在运行多个 程序在同一时间。 我可能有seen--如果我不 在Appliant这样做 但在我的Mac或PC--我可能有 观察的电子邮件的内容。 我可能会看到瞬间 消息我最近发。 任何可能 在内存周围徘徊 可以通过的方式被访问 这个任意方括号。 或者，更糟糕的是，你可能有 发现了我的密码1 我想最近输入的，一个 方案已存储在内存中，从而 验证了我， 然后种刚刚离开它 在内存中，直到我退出该程序。 事实上，这是一 的危险，一个权力 使用类似C的语言 您可以自由访问 到的全部内容 程序的内存， 什么坏人能 即使在做这些cases-- 特别是当我们 得到Web编程 朝学期结束，我们将 重温这topic--是闲逛， 可能有人是电脑的 记忆，找到这样的事情感到好奇 因为我们看到了那里。 甚至更糟糕的是，口令，他 或者她可以用它来干坏事。 所以，显然我不应该这样做， 因为奇怪的事情开始发生。 的确，这是一个程序崩溃。 这将是等效 的Mac OS的Windows或 程序窗口刚刚消失。 已发生未预期的错误。 在命令行环境 我们看到这样的事情。 但是，这是为什么，是我只是碰 不属于我的记忆。 因此，让我们对这样的防守 以不同的方式点点 通过看这个节目在这里。 因此，再次，骨架 我们看到先前已经 我已经强调了这一次诠释。 而这一切的时候主要有 实际上返回的值。 即使在我们大部分的演讲 我们从来没有使用一次例子 返回主任何东西。 我们只是写的printf关闭 大括号，就是这样。 但对于自由，什么 编译器已经做了你， 有效，则返回0给你。 打开out--，它是一个小 counterintuitive-- 0是好。 这并不意味着错误本身。 0是好，任何非0 值时，世界已经决定， 可以表示一个错误。 所以，如果你曾经搞砸 什么您的计算机上， 或计划刚刚去世，你和 你已经得到了一些错误窗口 在屏幕上，说错误 负49或错误23-- 一些看似随意的value--这 因为程序员已经硬编码 像49负或正的值 23代表任意数字，敢说， 四十亿可能的事情 可能出错的程序。 所以，我怎么可能拿 利用这一点我自己？ 好吧，让我打开一个程序 我提前写了， 和闲逛在线名为hello 4。 这几乎是相同的，不同之处在于 它得到了错误检查的一点点。 在这种情况下，我再次声明 主要是考虑两个参数， 但是这一次，在第17行，通知 我做了一下仔细的检查了。 我要确保 的argc等于等于2。 因为如果是，那 意味着我可以安全地 触摸不仅托架0，但是支架1。 我继续前进，打印出来， 在这种情况下，Zamyla或抢劫 或什么字我打出来。 而现在只是为了让 多一点正确的， 我要明确地返回 0来表示一切都很好。 没什么不好的事情发生了。 不过，按照惯例，我要 返回1，或者坦白任何非0值， 如果出事了。 现在，用户不会 真正注意到发生了什么事情。 事实上，如果我进入这个目录， 我们放大，做让你好4， ./hello-4 Zamyla表现如我所料。 但是，如果我不是不键入 什么，似乎什么都没有发生， 但它不会崩溃。 如果我不是做一些事情 像罗布是一个监考人 在Thayer--共享 任意信息。 但通知，argv的1，2，3，4，和 5现在应该存在于内存中。 这也并不是什么 我的程序需要， 因为我已经检查是否 的argc等于等于2或没有。 所以，我现在防御这一点。 现在，顺便说一句，我们的 programmer--或者说我们的users-- 从来没有看到一个0或1，但使用 工具，称为调试器或其它工具， 和以前一样，我们会看到 长，你的程序员 其实可以看看可能是什么 你的程序里面去错了。 因此，在ARGC什么问题吗？ 是啊。 听众：我见过他们 还没有的字符，[听不清] 刚才说的串星D，如 字符星号逗号。 他们是等价吗？ 大卫马兰：他们是。 所以，问题是，你有 偶尔可见的程序 像这样不 说字符串argv的支架 而是说些什么 像炭明星argv的支架。 甚至还有其他 变体，你可能会看到。 他们确实是等价的。 现在，我们有这些 这类训练车轮 在字符串中的CS50的形式 库，但在短短一个多星期 还是让我们将删除 完全梗阻，实际上 看看炭和星 有，以及这些涉及到内存 代表更普遍。 因此，我们会回来的。 在我们的argv和argc个其他的问题吗？ 是啊。 听众：为什么会回来 错误[听不清]？ 大卫马兰：为什么会 返回一个错误only--哦！ 在前面的情况下，当我们 带记忆功能均围绕把玩， 为什么只返回一个错误 当我真正输入一个大数目？ 简短的回答是，我们只是很幸运。 一般来说，一台计算机 在块分配内存， 它给了我一个足够大的存储块，它 我得到了，而不被发觉， 感人的支架2，支架3， 支架50，但只要我推 我的运气，我去超越 的存储器中的数据块的边界 操作系统给了我。 这就是当 取缔并说，没有。 分割错误。 是啊。 听众：如何在电脑 知道的argc的值？ 大卫马兰：请问该如何 计算机知道的argc的值？ 当你运行一个程序，该程序， 通过闪烁提示性质， 被传递的数组 被输入的字 在提示符下，这是 键入的。 因此，这是你的工作 系统的本质 填充主要的论点为您服务。 所以这是一个服务 之类的，你得到的，偷偷的 的机罩下方 一个操作系统。 其他问题吗？ 是啊。 听众：什么是核心转储是什么意思？ 大卫马兰：这是什么核心转储是什么意思？ 所以这是一个很好的问题。 让我重新回到 该目录在这里。 而且你会发现， 我有一个新的文件存在。 它确实是叫核心，它的 其实通常一个体面的大小的文件。 这是本质上的快照 我的程序的内存内容 或RAM时坠毁。 并且这将是有用的， 可能，诊断， 当我们谈论在未来的演讲 而有关调试部分， 因为你实际上可以做的 数字尸检相当于 在该文件中，以帮助找出 你做错了什么在你的程序。 是啊。 听众：是的argc的命令 本身，或者你的名字什么？ 大卫马兰：好问题。 是的argc命令本身， 或者你能想到的东西吗？ 这绝对不是一个命令。 这是一个简单的变量 命名或参数的名称， 所以，我们绝 可以称之为富， 我们可以把这个吧，这往往 是去到的话，一个计算机 科学家去。 但按照惯例，我们用argc和argv。 但是，这只是一个人 按惯例，仅此而已。 好吧。 所以，事实证明，我已经 讲述一个有点白lie--的 坦率地说，在未来，你会看到 我们已经告诉其他善意的谎言。 但现在，我们要 剥离背部的其中之一。 在这种情况下这里的时候，我在前面 跑起来像./hello或./hello-3方案 Zamyla，我们有内容我 计算机的内存期待大致如下 这个。 但是记得什么是字符串。 咱们怎么说的一个星期前有什么 字符串实际上是引擎盖底下？ 听众：字符数组。 大卫马兰：这是一个 字符数组的，对不对？ 因此，我们可能有一个数组 字符串，但是，反过来，一个字符串 是字符数组。 所以，如果我真的想成为 当我画这幅画的肛门， 我真的画 它有点像这样， 由此在每个这些 我argv数组的索引， 存在本身就是一个整串 这本身是一个数组。 现在的善意的谎言 我们今天讲 就是图片不 看上去很喜欢这个。 事实上，小广场都是 一般外面的大矩形 那里。 但我们会回来用不了多久。 但是，这是./hello反斜线0， 这是特殊字符 划定一个字符串的结尾， 我们已经得到了一个又一个后 Zamyla的名字。 所以，这是什么意思？ 好了，让我继续前进， 打开另外两个例子 这是在网上提供。 一个被称为argv1.c 另一种是argv2。 这是一个超级简单的程序， 与过去​​不同的方案 在现在，我使用 argc和argv在这里。 现在我有一个for循环积分 在长达argc那样线18，从i = 0。 而且我怎么办 与这行代码在这里？ 用英语。 这显然​​表明使用的argc的。 但在英语有哪些呢 它这样做，如果我运行这个程序？ 是吗？ 听众：这将打印 只要你想筛选多次。 马兰大卫：没错。 所以，无论话我 在提示符处键入，它的 要吐出 他们看着我，每行一个。 因此，让我们继续前进，做到这一点。 让我进入我的目录 做让argv1 ./argv1。 现在，让我们保持简单。 让我们什么也不做第一。 它没有打印出一件事， 这是确实的程序的名称， 因为这是在支架0。 如果我现在说富，它会做 这两个，如果我说富吧， 它会说，这三样东西。 现在，这是有点有趣，也许。 但记得的argv 是一个字符串数组， 但字符串是字符数组， 所以我们可以拿东西了一个档次 并应用基本 逻辑，使代码 看起来多了几分神秘，无可否认。 但是，有一个嵌套 循环的东西，类似于 什么，你可能还记得马里奥， 举例来说，如果你这样做，是这样的。 所以现在看到第19行，我 再次遍历我的论点， 从0一直到argc那样。 现在的行21--我 借用去年week--一招 我检查什么 长的argv支架I的。 我存储在正的答案。 然后我从J于一体 到n，其中j被初始化为0。 所以，约定计算。 一旦你使用了我，如果你有一个 嵌套循环，不能再次使用I， 否则你会揍，潜在的， 内环以外的值。 所以我用j通过约定。 我们可以使用k。 如果你比k的多了，你可能 有太多的嵌套，一般。 但现在，我发现的printf 线是略有不同的。 我不打印％S，我 当然，印刷％C，其中， 是一个占位符字符。 现在看到这个语法。 新。 我们以前没有见过。 但在逻辑上，这也就意味着 获得argv中第i个字符串 并获得第j个什么？ 听众：字符。 大卫马兰：字符的字符串。 所以可以用方括号 其次是方括号， 这是第一次跳水 进入ARGV的字符串， 然后将第二 方括号内为J 是在深入的字符 argv中的特定字符串。 然后，只为好措施， 我打印了新线在这里。 所以，现在让我继续前进，开 一个稍微大一点的窗口 所以我们可以看到这个动作。 让我进入该文件夹。 现在做让argv中，2-- whoops--作出的argv-2，./argv 2。 输入。 这是一个有点硬 垂直阅读， 但是这确实是名 程序，其次是一个空行。 现在让我继续前进，做富。 同样难读，但它的 的确打印每行一个字符。 如果我去做吧，这是现在 打印这些一行行。 因此，这里的外卖是没有这么多 ，哇，看这整齐的新把戏 在那里你可以在内容获取 的阵列的特定字符， 而是如何我们正在采取这些基本 这样的创意索引到一个数组中， 然后索引到一个 数组是数组， 而在应用了同样的想法， 稍微复杂的例子。 但基础实在不 改变，即使是自上周以来。 现在，这是有点及时， 在那，记得，零一周 我们打​​了一个电话本这样。 即使这是明显 物理的纸片， 种你能想到的 电话簿为一个数组。 当然，如果你要重新实现 这件这些纸片 在一台电脑，可能 你会使用的东西 像一个数组来存储所有这些 从A一路姓名和电话号码 到Z所以这是很好的，因为 它让我们有机会， 也许，要考虑你怎么可能 真正实现类似的东西。 由于有一系列的门这里。 所以，如果我could--我们需要一个 自愿到来吧。 让我们来看看。 一个陌生的面孔也许， 陌生的脸也许。 怎么样在橙色？ 这里。 橙色的衬衫，上来吧。 现在，让我们和举措继续 这些门上的侧 将这些闪开了一会儿。 你叫什么名字？ AJAY： 大卫马兰：阿贾伊。 大卫。 很高兴认识你。 好吧。 因此，我们有这六个背后 门数字上screen-- 或者说，七门上 screen--一大堆数字。 我已经告诉你什么 在advance--同意？ AJAY：事先没有。 大卫马兰：我只想要你做 现在是时候找到我，对我们来说， 真的，数量50， 一步一个脚印的时间。 AJAY：50号？ 大卫马兰：数字50。 而且你可以发现什么 后面这些门 只需用手指触摸它。 该死的。 [笑] [掌声] 非常出色。 行。 我们有一个可爱的礼物 奖你在这里。 你挑的电影，我们 上周讨论。 AJAY：哦，伙计。 哦，我从来没有见过太空炮弹。 大卫马兰：太空炮弹。 好吧。 因此，坚持只是一个瞬间。 How--让我们做这个 受教moment-- 你怎么去 寻找50号？ AJAY：我选择了随机。 马兰大卫：所以你选择了 随机真的很幸运。 AJAY：是的。 大卫马兰：确定。 优秀的。 所以，现在，你有没有 得到幸运的话，还有什么 可能发生背后的门？ 所以，如果我继续前进， 这里透露这些数字， 他们实际上是在随机顺序。 而最好的，你可以有 完成后，坦率地说，是，最终， 在最坏的情况下，检查了他们。 所以，你有超级幸运的，这 是不是我们所说的算法。 是的，恭喜。 但现在let's--幽默我，如果你能。 让我们在此选项卡在这里。 这里是明确的数字 似乎是随机的顺序， 而且他们。 但现在，如果我不是索赔 这背后的门 是被排序号码。 现在的目标是要还 找到我们的数50。 但这样做算法上，而 告诉我们你要去了解它。 如果你找到它，你把这部电影。 你不觉得，你给它回来。 AJAY：所以我要去检查结束 首先，确定是否there's-- [笑声及掌声] 大卫马兰：在这里你去。 让我们来看看1 Ajay的前辈， 肖恩，谁是没有那么幸运了。 好了，你在这里的任务， 肖恩，是下面的内容。 我隐藏在这些 门七位数， 但在一些宗门藏 以及其他的非负数。 你的目标是要想到这 号的最上一行作为仅有的阵列。 我们是件只是一个序列 纸与他们背后的数字。 你的目标是，只有使用顶部 阵这里，我找了七位数。 我们随后将要批判 你如何去这样做。 找到我们七位数，请。 号 5，19，13。 这不是一个脑筋急转弯。 1。 在这一点上你的分数不是很 好，所以你还不如继续下去。 3。 去。 坦白说，我不禁怀疑 什么你甚至想。 肖恩：我可以只从最上面一行。 大卫马兰：只有最上面一行。 所以，你有三个左。 所以找我7。 [听众呼喊几点建议] 因此，这两个都是惊人 非常不同的原因。 所以这是我们 离开片刻前， 这里的关键洞察力 在这些门有号 在他们身后被整理的，理想的 外卖的是，你可以做 在根本上更好 本次example-- 而事实上，这是肖恩的 第一次尝试用随机数 正如before--但只要 作为这些数进行排序， 像电​​话簿， 你能很明显吗？ 或者，你如何利用这些知识？ 是啊。 听众：你走到半路[听不清]。 马兰大卫：是啊。 没错。 所以Ajay的初始反应是 检查结束后，我记得， 然后排序，我们完成 这个例子很快。 但是，如果我们开始做这个多 有条不紊地沿着这些线路， 但是，在可能开始 中间，因为他们排序， 只要我们揭示 16号，所以我们知道 - ，让我们做的正是that--我们 因此，知道50，在今天的情况下， 已经该杀到右侧。 所以，就像在零一周时 我们在半撕电话簿 扔一半 的问题了，在这里同样的想法。 我们可以抛出这个半 这个问题了。 也可能是你 可能会做算法上， 一旦你知道，50必须 在正确的，如果它的任何地方， 是尝试在那里，在中间 的其余的门。 当然，图50是高 超过42，所以我们可以 抛出这个剩余 四分之一的问题了， 并且，最后，确定 像50。 但是，就像用 电话簿，这些数字 在给予我们已经 有序，这给我们留下 有问题，你怎么了 得到的东西进入的排序顺序？ 而且，坦率地说，代价是什么？ 这是一件事是 递给电话簿 然后通过找到打动你的朋友 电话号码真的很快，对不对？ 撕裂32页开始寻找 人出四十亿的网页， 我们说的是一个极端的例子。 但是有多少时候都不需要 Verizon公司进行排序的电话簿？ 它没有多少时间带我们 这七个数字排序？ 这是我们一直的问题 迄今完全忽略。 现在让我们回答这个问题。 而且我们都出电影了， 但是我们确实有一些压力球。 如果，比如说，8名志愿者 不介意加入我们了吗？ 让我们继续做，怎么样 你们四个，你们三个在这里？ 得到一些新的面孔。 和你们四个有？ 和now--我们不要偏见这里 - 和 数字8在这里就完了。 上来吧。 好吧。 所以，我们在这里为 你们每个人是一个数字。 如果你想去 未来，拿这个号码。 你叫什么名字？ ARTIE：阿蒂。 大卫马兰：阿蒂，好吧。 你是1号。 阿明：阿明。 大卫马兰：阿明。 大卫。 你是2号。 并继续前进，因为我的手 你的纸的片材， 排队了自己在音乐面前 站在相同的顺序在那里。 安迪：嗨，安迪。 大卫马兰：安迪，很高兴见到你。 3号。 雅各雅各。 大卫马兰：雅各，4号。 欢迎登机。 格兰特：格兰特。 大卫马兰：格兰特。 号码5。 ALANNA：Alanna。 大卫马兰：Alanna，6号。 FRANCES：弗朗西斯。 大卫马兰：弗朗西斯，7号。 和？ RACHEL：瑞秋。 大卫马兰：雷切尔，8号。 好吧。 来吧，让自己在这个秩序。 让我把剩下的一个 乐谱架的地方。 你在哪里需要一个立场？ 行。 来吧，只要把你的号码 那里的观众可以看到他们， 在乐谱架朝外。 并希望，我们的第一个 完整性检查这里 - 4，2，6。 哦，哦。 等待一分钟。 我们没有8。 我需要从你驱逐 这个例子莫名其妙。 号 不，没关系。 让我们来看看。 我们可以做到这一点。 支持。 我们走吧。 正确。 好吧。 所以，现在我们有8个，1，3 7 5。 行。 优秀的。 因此，目前的问题是，在 什么样的代价，并通过什么方法， 可我们实际上这些数字在这里进行排序 所以那种认为我们可以倒推， 最终，和decide--是不是真的 令人印象深刻的，是不是真的有效， 我可以分裂， 征服电话簿？ 是不是真的有效了 我可以分而治之 这些数字件 纸在黑板上， 如果，也许这将花费我们 发迹于时间或精力或CPU周期 真正让我们的数据 成一些有序？ 因此，让我们问这个问题。 所以，首先，这些数字都是 在几乎随机的顺序， 而我要建议 一种算法或过程 通过它，我们可以将这些人进行排序。 我要去接近 这个漂亮的天真。 我要去认识 这是种了很多对我来说 环绕在我的脑海 全部数据设定为一次。 但是你知道吗？ 我要做出一些 很简单的边际修正。 4和图2是不按顺序，如果 目标是从1到去多达8。 所以，你知道吗？ 我要拥有你 球员交换，如果切换 物理位置和 您的纸片。 现在4和6，这些都是为了。 我要离开的是。 图6和8中，那些符合规定。 要离开他们是。 8 AND1，乱序。 如果你们两个不会介意交换。 现在8和3，如果你们可以交换。 8和7，如果你们可以交换。 8和5，如果你们可以交换。 现在，我是不是做了什么？ 不，显然不是。 但我所做的 情况较好的，对不对？ 什么又是你的名字，8号？ RACHEL：瑞秋。 马兰大卫：所以瑞秋有 有效地冒泡很远， 一路的端 我的数字阵列在这里。 所以这个问题是种解决。 现在，很明显，2仍需要 动了一下，4和6和1。 但我似乎已经获得了 更近些的溶液。 因此，让我们应用同样的 天真的启发式一次。 2和4，确定。 4和6，确定。 图6和1，毫米毫米。 让我们来交换。 图6和3，毫米毫米。 让我们来交换。 6和7就可以了。 7和5，没了。 让我们来交换。 现在图7和8。 而你叫什么名字来着？ FRANCES：弗朗西斯。 大卫马兰：弗朗西斯。 所以，现在弗朗西斯是，即使一个更好的 位置，因为现在7和8 正确鼓泡到顶部。 因此，2和4，确定。 4和1，我们交换。 4和3，让我们交换。 4和6，你真行。 6和5，让我们交换。 而现在那些家伙都不错。 我们快到了。 2和1，乱序，所以交换。 现在让我做一个全面的检查。 图2和3，图3和4，图4和 5,5和6,6和7,8。 好了，我们就大功告成了。 但代价是什么没有我 这些数字在这里进行排序？ 那么，有多少步骤可能我做 整理这些人的时候走？ 好了，我们会回来的问题。 但是，坦率地说，如果你有 有点无聊，这是 种揭示，这是不 也许是最有效的算法。 事实上，坦率地说，我出汗 更来回走动。 这并没有觉得特别有效率。 因此，让我们试试别的。 如果你们能重置 你们这八个值。 好工作。 让我们来看看数字，对于刚 片刻之前，我们尝试别的东西， 在刚刚发生了什么。 在这里，你即将看到一个 这八人的可视化 由此蓝色和红色 线表示数字。 该高了吧， 更大的数目。 酒吧越短， 数字越小。 而且你会看到什么是在 随机顺序当中超过八人。 你会看到这些酒吧 越来越排序方式是相同的算法， 或指令集，其 我们会打电话给今后冒泡排序。 所以请注意，每一秒左右， 两个酒吧都照亮了红色， 由计算机进行比较。 然后如果大条和 小酒吧是乱序， 他们被交换给我。 现在，这是令人难以置信的繁琐 看这个，当然， 很长，但要注意的 takeaway--大条向右移动， 小棒移动到左侧。 让我们来终止这个进程 并加快这 要快很多，所以我们可以 得到一个什么样的高层次感， 的确，冒泡排序在做什么。 事实上，它的向上冒泡到 列表中的右手侧， 或阵列，更大的酒吧。 反之，小酒吧 鼓泡的方式，以左， 虽然以更快的速度 比我们以前做了。 因此，很难看到人， 但在视觉上这确实是 正在发生的事情。 但是，让我们尝试从根本上 不同的方法了。 让我们尝试不同的 算法即能满足您 球员开始在这些原 位置，这是这个顺序在这里。 而现在让我们继续。 而我要做的事 即使是简单的，对不对？ 现在回想起来，再两两交换 又一次，几乎是小聪明。 让我们做事情更天真， 在那里，如果我想这些人进行排序， 让我继续找 为最小的元素。 所以现在，4是 最小号我见过。 我要记住这一点。 不，2是更好的，记住这一点。 1更小。 3，7，5。 行。 埃德蒙顿你叫什么名字来着？ ARTIE：阿蒂。 大卫马兰：阿蒂。 因此，阿蒂，勇往直前。 我要拉你出来就行了。 如果你能回到这里来。 我需要腾出空间给他。 我们有一个决策点这里。 怎么可能，我们腾出阿蒂这里 在其中1号所属的开始？ 听众：移位。 大卫马兰：好了，我们 可能会改变每一个人。 但提出了一个优化。 这感觉有点恼人 我要问四人 一路向下移动。 我还能做什么？ 听众：切换。 大卫马兰：切换。 而你叫什么名字来着？ 雅各雅各。 大卫马兰：雅各移动。 更高效只需要有 与阿蒂雅各互换位置， 而不是迫使 这些人的所有四个， 非常感谢你，给 其正确的位置。 有什么好的关于阿蒂现在， 他在他的正确位置。 让我们再次做到这一点。 2，这是最小的数字我见过。 3，7，5。 行。 2，绝对是最小的。 没有做任何工作。 让我们再做一次。 6。 最小？ 8。 不。 4？ 哦。 我记得4。 3。 我记得3。 7,5。 最小的数字我已经 看到这一关就是3。 如果你会来上了。 我们去哪儿把你吗？ 而你叫什么名字？ ALANNA：Alanna。 大卫马兰：Alanna，我们 不得不赶你。 但是，这是更有效的， 只是换了两个人， 比有多人 实际上回避了。 现在，让我们再次做到这一点。 我会选择4，所以就来了。 和谁去动？ 8号，当然。 如果我现在发现5号，拜托了。 8号会得到再次驱逐。 我现在要去找到位数6。 7到位。 8就位。 我们刚才所做的是 一些所谓的选择排序， 如果我们想象这一点，它的 会觉得有一点不同。 让我们继续前进，从这个 菜单在这里，这visualization-- 让我们改变这个to--来吧，Firefox浏览器。 让我们改变这个选择排序。 让像以前一样的加快步伐， 现在开始的可视化。 该算法具有 不同的感觉。 在每次迭代中，坦率地说， 它更简单。 我只是选择的最小元素。 现在，坦率地说，我有点幸运， 时间，在它的排序超快。 这些元素是随机的。 这不是，因为我们最终会 看，根本快。 但是，让我们看到了第三次也是最后 此方法，因为要发生的事情。 因此，让我们继续前进，重新你们 一最后一次是在这里这个顺序。 而现在，我要 有一点更聪明， 只是圆了我们的算法。 我会做到这一点。 我会不会去 来回这么多。 坦率地说，我已经厌倦了 这一切的穿越。 我只是要带什么，我 在列表的开头给出 我要去排序 那，然后有。 所以，我们在这里。 4号。 我要插入数 4成排序的列表。 完成。 我现在声称，只是让这个更 显然，这部分我的列表进行排序。 这是一种愚蠢的索赔，但确确实实 4是按尺寸1的列表。 现在，我要承担数2。 2号，我现在要 插入到合适的位置。 那么，这是否属于2？ 显然，在这里。 所以，尽管回迁，如果你能。 而为什么你们不只是把 你的音乐代表了你这一次。 而且，我们强行插入您 到列表的开头。 所以，更多一点的工作。 我不得不提出雅各布身边， 而你叫什么名字？ 阿明：阿明。 大卫马兰：阿明。 但至少我没有去来回。 我只是以事，我去。 我只是将它们插入 在正确的地方。 6，其实这是很容易的。 让我们将你在那边，如果你 只是想稍微移动了。 8号，也非常的方便。 就在那边。 该死的。 1号，我们不能只 与阿明在这里交换， 因为这是怎么回事 乱了秩序。 因此，我们要多一点聪明。 因此，阿蒂，如果你能 备份了一下。 让我们继续前进，现在转移， 不像我们以前的算法， 让路给阿蒂 这里开头。 所以，在这一天结束时，我种 做什么，我想避免之前。 所以我的算法排序 逆转，智， 从它最初是什么。 我只是在做转移 在不同的点。 现在，我在3。 哦，该死的。 我们必须重新做更多的工作。 因此，让我们推你出去。 让我们继续前进8,6，4--哦oh--和 3是要去那里。 所以至少略有节余这个时候。 7，没有太多的工作要做。 所以，如果你想弹出 回来了，让我们来插入你。 最后，图5，如果你 想弹回，我们 需要转向你，你， 你，直到5到位。 所以，现在看到了这点 高水平的图形， 让我们做这个算法 可视化的一个额外的时间。 所以这个我们称之为插入排序。 我们会运行它就像 快，从这里开始吧。 而且，也有不同的感受。 这有点越来越好， 好，但它从来就不是完美 直到我走在光滑的这些差距。 因为，同样的，我只服用了 我正考虑由左到右。 所以，我没有那么幸运了 这一切都是完美的。 这就是为什么我们有这些小 我们在固定的时间mispositions。 因此，所有这些算法似乎 在略微不同的速度运行。 事实上，你想说的是 最好的或迄今最快？ 冒泡排序，第一个？ 选择排序，第二次？ 插入排序，第三？ 我听到了一些选择排序。 其他的想法？ 所以，事实证明， 所有这些算法 基本上是一样有效，因为 每个other--或者相反，正如 低效的，彼此 因为我们能做到从根本上 不是所有的三个好 这些算法。 而这一点善意的谎言的，太。 当我说是有效的 或者效率低下， 这至少为 超级大n值的。 当我们只有八人在这里， 或者是50元左右吧在屏幕上， 你会发现绝对差异 其中这3种算法。 但随着N，人数， 或号码的数目， 或者人在电话号码 书，或网页的数 在谷歌的数据库 变得越来越大， 我们会看到，所有这三个 算法实际上是非常差的。 而我们能做的根本 比这更好。 让我们来看看，最后， 什么这些算法可能 听起来像在 几人背景 并通过这种方式 可视化在这里 这将我们介绍给 一些算法。 让我们继续前进，并祝贺 在这里我们的参与者，所有的人 整理自己很好。 如果你想借此临别礼物。 你可以把你的号码也是如此。 你会看到什么， 或者更确切地说，听，现在， 是因为我们把声音 每个这些条 并将其与软件相关联， 不同频率的声音， 你可以用你的头脑更audioly 各地各有什么这些东西 看起来像。 其中第一个是插入排序 [音调] 这是冒泡排序。 [音调] 选择排序。 [音调] 一些所谓的合并排序。 [音调] 侏儒排序。 [音调] 这就是它的CS50。 我们会看到你在星期三。 旁白：现在，“深 思考“，由Daven法纳姆。 为什么一个循环？ 为什么不让它变得更好？ 我做了五圈。 [笑]