>> [音乐播放]
>> DOUG LLOYD：OK，这样的合并 排序是另一种算法
我们可以用它来梳理 数组的元素。
但是，正如我们看到的，它有一个 很根本的区别
从选择排序，冒泡 排序和插入排序
这使得它真的很聪明。
>> 合并背后的基本理念 排序是更小的数组排序
然后再结合这些阵列 在一起，或合并them--
因此，在有序的name--。
该归并排序的方式做 这是通过利用一个工具
被称为递归，这是什么 我们要谈论不久，
但我们还没有真正谈过呢。
>> 这里的背后归并排序的基本思想。
对数组进行排序的左半部分， 假设n大于1。
而我的意思是，当我说 假设n大于1是
我想我们可以同意，如果一个数组 仅由一个单一的元件的，
它的排序。
我们实际上并不需要 做任何事情来了。
我们只需将其声明进行排序。
这只是一个单一的元件。
>> 这样的伪码，同样，是 对数组进行排序的左一半，
然后排序右半阵列， 然后合并两半。
现在，已经你可能会 思考，它只是一种
听起来你推迟喜欢the-- 你实际上没有做任何事情。
你是说左边的排序 上半年，排序的右半​​部分，
但你不能告诉 我怎么你这样做。
>> 但要记住，只要 阵列是一个单一元件，
我们可以宣布它排序。
然后，我们就可以将它们组合在一起。
而这实际上是 背后归并排序基本思想，
是要打破它，这样 你的数组的大小之一。
然后你从那里重建家园。
>> 合并排序是肯定 一个复杂的算法。
而且它也是一个小 复杂的可视化。
所以希望，可视化，我 这里将帮助你跟着。
我会尽我所能叙述的事情 并继续通过这个多一点
慢慢比其他的 只是希望得到你的头
各地背后归并排序的思想。
>> 因此，我们有相同的阵列作为 其他排序算法视频
如果你看过them-- 六元素的数组。
在这里，我们的伪代码排序 左半，排序右半
合并的两半一起。
因此，让我们利用这个非常暗砖红色 数组和排序它的左半边。
>> 所以暂且，我们将 忽略右边的东西。
它的存在，但我们 不是在这一步呢。
我们不是在排序 阵列的右半。
我们在左边的排序 一半的阵列。
而贪图 被多一点
清晰的，这样我就可以参考 到了哪一步，我们是上，
我要去切换 颜色这套橙色的。
现在，我们还在谈论 原来阵列相同的左一半。
但我希望，通过能够 指各种物品的颜色，
它会让它多了几分 不清楚什么是怎么回事。
>> 好了，现在我们有一个 三元数组。
我们怎么样的这个左半 阵列，这仍然是这个步骤？
我们试图向左排序 一半的砖红色array--的
其中左一半 我现在已经橙色。
>> 好了，我们可以尝试 再次重复这个过程。
因此，我们仍然在 试图梳理中间
完整阵列的左半部。
的左半 阵列，我只是去
任意决定的左半 将比右半较小，
因为这恰巧 包括三个部分。
>> 所以我会说， 左半阵列的左半
只是五行说。
五，作为一个单一的元素 阵列，我们知道如何排序。
所以五是排序。
我们只是要声明。
这是一个单元素数组。
>> 所以，我们现在已经排序 左half--的左半
或者更确切地说，我们已经排序 橙色的左半部。
所以，现在，为了仍然完整 整个阵列的左半边，
我们需要的右半排序 的橙色或这个东西。
我们该怎么做呢？
好了，我们有两个元素的数组。
因此，我们可以排序的左半 阵列，这是两个。
两个是单一元件。
因此，它的排序默认情况下。 然后，我们可以排序的右半
该部分阵列，所述一个的。
这类型的默认。
>> 现在这是第一次 我们已经达成了合并的步骤。
我们已经完成了，虽然 那种我们现在嵌套down--
这就是那种棘手的 递归的是，
你需要保持你的 脑袋一下我们在哪里。
因此，我们在左边的已排序 一半的橙色部分。
>> 而现在，我们在整理的中间 橙色部的右半部分。
而在这过程中，我们 现在即将要上台阶，
合并的两半一起。
当我们在看的两半 阵列的，我们看到两个和一个。
该元件是小？
一。
>> 那么哪一个元素是小？
嗯，这是两个或没有。
因此，这两种。
所以，现在，想再次回到框架 我们所处的背景下，
我们已经整理了 橙色的左半
和原点的右半部。
我知道我已经改变了颜色 再次，但是这就是我们。
而我之所以这样做 是因为这个过程是
要继续下去，迭代下降。
我们已经排序的左 半前橙色
和前橙色的右半部分。
>> 现在，我们需要合并这些 两半了。
这是我们的第一步。
所以我们考虑所有的 元素是现在绿，
原数组的左半部。
我们合并这些 使用相同的过程
我们为合并两个 和一个刚才。
>> 左半，最小 左边一半元件是五。
上的最小元素 右半边是其中之一。
其中哪些是小？
一。
>> 上的最小元素 左半边是五。
上的最小元素 右半边为两个。
什么是最小的？
二。
然后最后五 什么都没有，可以说五位。
>> 好了，这么大的画面，让我们 休息一秒钟
并找出我们在哪里。
如果我们从开始 一开始，我们
现在已经完成了 整体阵列只
的伪代码一步在这里。
我们已经整理了 阵列的左半部。
>> 回想一下，原 为了五岁，二，一。
通过经历这个过程 和筑巢下来，重复，
继续打破问题 分解成更小和更小的部分，
现在我们已经完成 步骤的伪代码之一
对于整个起动阵列。
我们已经整理了左前卫。
>> 所以，现在，让我们定格在那里。
现在，让我们来排序的权利 原来的一半数组。
而我们要做到这一点 经历同样的迭代
打破下来的过程 然后将它们合并在一起。
>> 这样的左半 红色，或左半
原稿的右半部 阵，我会说是三。
再次，我是一致的在这里。
如果你有一个奇怪的 元件的数目，它
并没有真正也罢 你让左边的一个小
或者是正确的要小。
>> 重要的是，只要你 遇到在进行这个问题
合并，就需要保持一致。
要么你总是需要 使一个左侧小
或总是需要使 右侧小。
在这里，我选择永远 使左侧小
当我的数组，还是我的 子阵列，是一个奇怪的大小。
>> 三是单一元件， 所以它的排序。
我们充分利用这一假设 我们整个过程为止。
所以，现在让我们来排序的权利 一半的右边一半的，
或红色的右半边。
>> 同样，我们需要拆分下来。
这不是一个单一的元件阵列。
我们不能宣布它排序。
所以首先，我们要 在左半排序。
>> 左半是单一元件， 所以它的排序默认情况下。
然后，我们要排序的权利 一半，这是单一元件。
它的排序默认情况下。现在， 我们可以合并这两个在一起。
四个较小，并 然后6越小。
>> 此外，我们还有什么在这一点上做了什么？
我们已经排序的左 一半的右边一半。
或回到原来的 这是有颜色的，
我们已经排序的左 一半的较软的红色。
它最初是一个黑砖 红现在是一个更柔和的红色，
或者，这是一个较软的红色。
>> 然后我们排序 的较软红右半边。
现在的，很好，他们是绿色还是一样，只 因为我们正在经历一个过程。
我们要重复 这一遍又一遍。
>> 所以，现在，我们可以合并这些 两半。
这就是我们在这里做。
所以黑线刚 划分左半
与这种部分的右半部分。
>> 我们比较的最小值 在array--左侧
还是原谅了我，最小 左半的值
到的右侧的值最小 一半，并找到三个较小。
而现在有点优化的，对不对？
有其实也没什么 留在左侧。
>> 没有什么剩余 在左侧，
所以我们可以有效地 只是move--我们可以声明
它的其余部分实际上是 排序，只是它钉住
对，因为没有什么 别人进行比较的。
我们知道，右侧 右侧是排序。
>> 好了，现在让我们再次冻结和 找出我们所处的故事。
在整个阵列， 我们有什么成就？
我们实际上已经完成 现在步骤一和步骤二。
我们的排序左半，和 我们整理了右半边。
>> 所以，现在，这一切仍然是我们 这些两半合并在一起。
所以我们比较具有最低值 阵列的每个一半的元件
反过来，然后继续。
一个是小于3，所以一去。
>> 二是不到三年，所以二除。
三是小于5，所以三去。
四是小于5，因此四去。
然后，五是不到六个月， 六是所有仍然存在。
>> 现在，我知道，这是一个很大的步骤。
而且我们留下了很多 记忆在我们唤醒。
而这正是那些灰色方格。
它可能感觉就像是拿了 很多的时间比插入排序，气泡
排序或选择排序。
>> 但实际上，由于 很多这些过程
都发生在同一时间 - 这是一件好事，我们将再次
谈论当我们谈论 递归在未来video--
这种算法实际上 显然是根本
比什么不同 我们已经看到前
但是也显著 更有效。
>> 这是为什么？
那么，在最坏的 的情况下，我们有
分裂n个元素了 然后重新组合它们。
但是，当我们重新组合 他们，我们在做什么
基本上是翻倍 较小的数组的大小。
我们有一大堆的一个元素 阵列我们有效
合并成2个元素的数组。
然后我们把这些 二元阵列
并结合在一起成 4元件阵列，等等，
等等，依此类推，直到我们 有一个单个n元件阵列。
>> 但究竟有多少倍增 它才能让到n？
回想一下电话簿的例子。
多少次，我们要撕 电话薄了一半，要多
次我们是否撕电话簿 在一半中，如果电话簿的大小
翻倍？
这里只有一个，对不对？
>> 因此，有某种 这里对数的元素。
但是，我们也还是要至少 看看所有的n个元素。
因此，在最坏的情况下， 合并排序运行时间为n日志ñ。
我们来看看 所有的n个元素，
我们必须把它们混合起来 一起在记录n个步骤。
在最好的情况下， 该阵列是完全排序。
那很棒。
但基于算法，​​我们这里有， 我们还是要分裂和重组。
虽然在这种情况下， 再结合是一种无效的。
它是不需要的。
但是，我们仍然要经过 整个过程呢。
>> 因此，在最好的情况下 而在最坏的情况下，
该算法运行在的n log n次。
合并排序肯定是有点棘手 比其他主排序算法
我们谈到CS50但 实质上更加强大。
>> 所以，如果你发现 有时需要它
或用它来排序 大型数据集，得到
你的头左右递归的想法 将是真正强大。
而这将让你的 节目真的更有效
使用分类合并与其他任何东西。
我是道格·劳埃德。
这是CS50。