爲什麼mergesort更適合鏈接列表？

Question

爲什麼mergesort在排序列表時不考慮快速排序時考慮「走的路」？ 我在網上看過的一個講座中聽到了這個消息，並在幾個網站上看到了它。

Answer 1

Quicksort效率的主要來源之一是locality of reference，其中計算機硬件經過優化，以便訪問彼此接近的內存位置往往比訪問散佈在內存中的內存位置更快。快速分區中的分區步驟通常具有優良的局部性，因爲它可以訪問前後附近的連續陣列元素。因此，快速排序往往比其他排序算法（如堆排序）執行得更好，即使它經常進行大致相同數量的比較和交換，因爲在排序情況下，排序更加分散。

此外，快速排序通常比其他排序算法快得多，因爲它就地操作，無需創建任何輔助數組來保存臨時值。與合併排序相比，這可能是一個巨大的優勢，因爲分配和釋放輔助數組所需的時間可能會很明顯。在原地進行操作也可以提高快速排序的位置。

使用鏈接列表時，這些優點都不一定適用。由於鏈接列表單元格通常分散在整個內存中，因此訪問相鄰鏈接列表單元格時沒有局部獎勵。因此，quicksort的巨大性能優勢之一就被吃光了。同樣，就地工作的好處不再適用，因爲合併排序的鏈表算法不需要任何額外的輔助存儲空間。

這就是說，quicksort在鏈表上仍然非常快。合併排序的速度通常會更快，因爲它更平均地將列表分成兩半，每次迭代執行合併的工作量少於執行分區的步驟。

希望這會有所幫助！

Answer 2

find（）的成本比mergesort更有害於quicksort。

合併排序對數據執行更多「短程」操作，使其更適合鏈接列表，而快速排序可以更好地使用隨機訪問數據結構。