>> DOUG LLOYD：所以在CS50，我们了解了 多种排序和搜索的
算法。
有时也可以是 一个小技巧，以保持
跟踪什么算法做什么。
我们真的只 撇去表面上也是如此，
还有很多其他的搜索 和排序算法。
所以在这部影片让我们 只需要几分钟的时间
尝试和提炼每个算法 到其核心要素
这样你就可以记住的最 有关的重要信息
并能够阐明 差异，如果有必要的。
>> 首先是选择排序。
后面的选择排序的基本思想 被发现的最小的未分类的元素
在一个阵列，并交换它与 该数组的第一个未排序的元素。
我们说，在最坏情况下 的运行时间为：N的平方。
如果你想召回原因，采取 来看看选择排序视频。
最好的情况下运行时间 是也可为N的平方。
>> 冒泡排序，背后的想法 一个是交换相邻对。
所以，这可以帮助你的关键 记住这里的区别。
选择排序是，到目前为止， 找到smallest--泡沫
排序是交换相邻的一对。
我们交换相邻的一对 元件的，如果他们
都失灵，从而有效地 泡到右侧较大的因素，
并在同一时间它也开始 移动到左侧较小的元素。
最坏情况下的情况下运行时间 冒泡排序为n的平方。
最好的情况下运行时间 冒泡排序为n。
因为在这种情况 我们不actually--
我们可能不需要 做任何掉期的。
我们只需要进行一次 通过在所有n个元素。
>> 在插入排序中， 这里基本思路正在发生变化。
这就是关键字插入排序。
我们正在经历步骤一次 从阵列从左到右。
当我们这样做，我们 要转变要素
我们已经看到，以腾出空间 较小的需要适应的地方
早在那个排序的部分。
因此，我们所建立的有序阵列中的一个 元件在一个时间，从左到右，
我们的东西转移，以腾出空间。
最糟糕的情况下的运行时间 插入排序为n的平方。
最好的情况下的运行时间为n。
>> 合并类别 - 关键字 这里被分割和合并。
我们分裂了全阵列，无论是 这六个要素，八大要素，
万elements--将其切 降了一半，一半，一半，
直到我们有下阵 正一个元素的数组。
一组N个一个元素的数组。
因此，我们开始与一个 1000元阵，
而我们得到的地步，我们 有1000个一单元阵列。
然后，我们开始合并这些子阵列 回到一起以正确的顺序。
因此，我们采取两个一元的阵列 并创建一个两元素数组。
我们需要两两元素数组 并创建一个四元数组
等等等等，直到我们 再次重修一个n元素的数组。
>> 最糟糕的情况下的运行时间 归并排序是N次日志N。
我们有n个元素，但 这个重新组合的过程
需要记录n步获得 回到一个完整的阵列。
运行时，最好的情况下也的n log 5.2，由于这个过程中并没有真正的
关心阵列是否 排序或不下手。
的过程是相同的，有 没办法短路的事情。
因此n日志N在最坏情况下， N日志N的最好的情况下。
>> 我们谈了大约两个 搜索算法。
所以线性搜索是关于迭代。
我们继续进行跨越阵列 一次，由左到右，
努力寻找数 我们正在寻找。
最坏情况下的运行时间是n的大澳。
这可能需要我们遍历 横跨每一个元件
找到我们正在寻找的元素 为，无论是在最后的位置，
或根本没有。
但是，我们不能确认，直到 我们已经看过了一切。
米最好的情况，我们马上找到。
最好的情况下的运行时间 线性搜索是1欧米茄。
>> 最后，出现了二分搜索， 这就需要配套阵列。
请记住，这是一个非常 重要的考虑因素
与二进制搜索工作时。
这是一个先决条件使用它 - 你正在寻找通过数组
必须进行排序。
否则，关键字 是分而治之。
拆分数组半 消除一半的元素
每一次当你继续完成。
由于这种分而治之的 和分裂的事情了一半的方法，
最坏情况下的运行时间 的二进制搜索是
日志N，其基本上 不是线性搜索n值更好。
在最好的情况运行时间仍为之一。
>> 我们可能会立即发现 我们第一次做一个划分，但是，
再次，请记住， 虽然二进制搜索
大大高于线性搜索更好 由于是日志N对N，
你可能要经过工作 先整理你的阵列中，这
可能会使它不那么有效视 在迭代排序的大小。
>> 我是道格·劳埃德，这是CS50。