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。