[Powered by Google Translate] [归并排序] [罗布·鲍登 - 哈佛大学] [这是CS50。 -  CS50.TV] 让我们来谈谈有关合并排序。 到目前为止，您已经看到冒泡排序，插入排序，选择排序。 虽然我种我的手，我的意思更好地波， 合并排序通常执行比这3类。 

但在谈论合并排序之前，让我们来谈谈关于合并的2个排序的列表。 我们会给你打电话的过程中，2排序的列表，像这样的， 使一个单一的排序列表中的他们 - 合并列表。 如何才能做到这一点呢？ 好了，一个想法，就是坚持一个列表到其他列表 ，然后在结果列表进行排序。 

虽然这个工作，这是一个许多不必要的工作。 我们可以做得更快比刚排序。 请注意，一个错误的观念，是采取交替杯，从每个列表中。 虽然这可能看起来像这样的作品，在第一， 这样做，我们最终4，8，15，23，16  - 通知，16日和23出来的地方。 这是因为，在合并后的名单应该会出现连续的2个元素 是在相同的初始列表。 15和16都在左侧列表中的。 关键是要充分利用已排序的事实，这两个列表。 这意味着，如果我们只是看在两个列表中的第一个元素 -  在这里，4和8  - 其中之一也必须合并后的列表中的第一个元素。 好了，这是为什么？ 这两个列表都已经排序， 等4个或8时，必须是最小的元素，我们结合2列出了。 在这种情况下，最小的是4， 因此，我们可以拿出4，我们的合并列表中的第一个元素。 现在我们将继续合并剩余的3个元素的第一个列表 和4个元素的第二列表。 

再次，我们只需要看看这两个列表中的第一个元素。 中的较小者的2必须是我们的合并列表中的第二个元素。 这一次，8和15之间，最小的是8，所以我们插入， 作为我们的排序的列表的第二个元素。 我们可以继续比较这两个列表中的第一个元素 并除去2的小的。 15日和23日，15相比较小，所以这是我们的第三个元素。 现在比较16和23中，图16是较小的。 所以这是第四个元素。 

请注意，2个元素是从同一个列表中的行。 这是为什么合并后的清单不能只是备用2个列表元素。 比较50和23，23小，所以我们选择。 在50和42之间，42是较小的。 在50和108之间，50是较小的。 最后，我们只是有108个，所以一定要在我们的名单。 请注意，我们有一个很好的，排序的列表。 每次我们比较了2列出了前2个元素 我们能够确定合并后的列表中的下一个元素。 这意味着，如果最终的列表包含n个号码，其中，n是8， 然后，我们需要在最n次比较这些数字放到合适的地方。 这样的算法的所述以线性时间运行， 不过不用担心，在这里。 

使用我们的算法进行合并，我们就可以进行快速的合并排序算法。 所以，让我们的名单重置。 归并排序的过程中，有2个大的步骤。 首先，连续分裂列表杯分为两半 直到我们有一堆名单，他们只用1杯。 不要担心，如果列表中包含一个奇数 你不能让他们之间的一个完全干净的切割。 只需随便挑哪一个清单，包括额外的杯子中。 所以，让我们这些列表拆分。 现在，我们有2个列表。 现在，我们有4个列表。 

现在，我们有8个列表，每个列表中的单杯。 所以这是它的第1步。 对于第2步，我们多次合并对使用合并算法，我们以前学过的列表。 合并108和15，我们结束了15日，108。 ，合并50和4​​，我们最终有4个，50。 合并8和42，我们有8个，42。 合并23和16，我们最终有16个，23。 现在我们的列表大小为2。 请注意，每个的4列出的是排序条件。 

因此，我们可以再次开始合并对列表。 合并15和108以及4和50  -  先来的4个，然后是15，然后是50，然后是108。 合并8，42，16，23， 我们先来的8个，然后16，然后23，然后42。 所以现在我们有2列出了大小为4，每一个排序。 所以，现在我们合并这两个列表。 首先，我们采取了4。 然后，我们采取了8。 然后我们把15和16，然后23，然后42，然后50，然后108。 我们就大功告成了。 我们现在有一个排序的列表。 因此，如何快速是这样的，到底是什么？ 在技​​术方面，归并排序是O（n日志n）， 而所有的冒泡排序，插入排序，选择排序为O（n²）。 事实上，你会学习很快，你将不能够拿出一种 执行在一般情况下比O（n日志n）。 再次，不要担心这个大O表示法，如果你还没有看到它。 

只知道，这意味着如果我们想要，排序一个真正的大名单 冒泡排序，插入排序，选择排序可能 明显长于合并排序。 这并不意味着会更快归并排序的所有列表 甚至是任何单独的列表中下一个一定规模的。 例如，插入排序可能是最快的排序为所有小于5个元素的列表。 在实践中，合并排序通常更快尽可能小为50个元素的列表。 

但这些额外的速度不会没有代价的。 与其他各种不同的是，一个列表，修改列表中的地方 直到我们得到一个排序的列表，归并排序需要一些额外的空间 合并2列出了一起。 我们不能立即使用的名单，被合并存储合并列表 因为我们可能会覆盖仍需要合并的元素。 这个空间是一个位的价格，但它通常是不讲理的。 这就是归并排序。 

我的名字是罗布·波顿，这是CS50。 [CS50.TV]  - 选择排序。 [笑] 哦，得了采取的太多，因为我交换，我是如何呈现它。 在左侧的列表。这是一个错字。 [misspoke我搞砸了 -  [笑] 我不知道是什么 -