[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我搞砸了 -
[笑]
我不知道是什么 -