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