为什么归并排序对于链表更好？

Question

在对列表进行排序时，为什么归并排序被认为是"正确的选择"而不是快速排序？我听过在线讲座中提到这个问题，并在几个网站上看到它。

- bb2

---

请查看以下内容： https://dev59.com/yXRB5IYBdhLWcg3w1Khe - Ivan Bohannon

Answer 1

快速排序的效率之一在于引用局部性（locality of reference），计算机硬件被优化以访问相邻内存位置比访问分散的内存位置更快。快速排序的分区步骤通常具有很好的局部性，因为它访问靠近前面和后面的连续数组元素。因此，尽管快速排序通常进行大约相同数量的比较和交换，但它往往比堆排序等其他排序算法表现得好得多，因为在堆排序的情况下，访问更加分散。

此外，快速排序通常比其他排序算法快得多，因为它可以原地操作，不需要创建任何辅助数组来保存临时值。与类似归并排序的算法相比，这是一个巨大的优势，因为分配和释放辅助数组所需的时间是可以看到的。原地操作也提高了快速排序的局部性。

当使用链表时，这些优点都不一定适用。由于链接列表单元格通常分散在内存中，因此没有访问相邻链接列表单元格的局部性奖励。因此，快速排序的巨大性能优势之一就被消耗掉了。同样，使用原地排序的好处也不再适用，因为归并排序的链表算法不需要任何额外的辅助存储空间。

尽管如此，快速排序在链表上仍然非常快。合并排序只是倾向于更快，因为它更平均地将列表对半分割，并且每次迭代执行合并所需的工作比执行分区步骤少。

希望能对您有所帮助！

- templatetypedef

---

在第三段的最后一行中，您写道：“同样，就地工作的好处也不再适用，因为归并排序的链表算法不需要任何额外的辅助存储空间。”为什么它不需要辅助存储空间？ - Geek

@Geek 我可能应该说“归并排序的链表算法不需要**O(n)**辅助存储空间。”标准的基于数组的归并算法需要在执行归并过程中分配额外的存储空间，因为元素需要移动。在使用链表的归并排序中，可以通过简单地重新链接它们来移动元素，而无需分配外部数组。 - templatetypedef

Answer 2

find() 的成本对于快速排序比归并排序更加有害。

归并排序在数据上执行更多的“短程”操作，使其更适用于链表，而快速排序更适合具有随机访问数据结构。

- cJ Zougloub

---

find()是什么意思？ - templatetypedef

寻找数据结构中的条目。对于链表，您始终在前进/倒带，就像播放磁带一样。 - cJ Zougloub

在链表快速排序中，您不需要使用数组上使用的随机访问分区函数。您可以通过迭代遍历列表并将每个元素分配到三个列表之一 - 一个“小于”列表，一个“大于”列表和一个“等于”列表，然后对后两个进行递归来对链表进行分区。您是正确的，标准分区很慢，但这并不本质上使链表快速排序变慢。 - templatetypedef

Answer 3

这是因为它更节省内存。就速度而言，它比较慢。链表必须迭代每个元素才能到达所需的元素，只有第一个元素和最后一个元素可以直接访问，在双向链表的情况下，这将使添加和删除更快，但如果不是在列表的第一个和最后一个元素，则会变慢，因为它必须迭代每个元素才能到达指定的索引。

另一方面，数组则不太节省内存，因为它可以容纳的元素数量是固定的，因此，如果数组中未使用所有可用空间，则会浪费空间，因为创建数组时，将分配在声明中指定的所选数据类型的元素数量。数组在删除和添加数据方面效率较低，因为在添加或删除数据后，整个数组必须重新排列。另一方面，数组可以更快地访问元素，确切地说，时间复杂度为O(1)。

总之，数组具有更快的整体搜索时间，在所有情况下，删除和添加时间的时间复杂度为O(m-n+1)，其中“m”是数组的大小，“n”是所需元素索引。链表在第一个和最后一个元素处具有O(1)添加和删除时间，但在中间部分的时间复杂度最差，因为它必须遍历列表的每个元素才能到达该元素。链表具有最佳的内存分配，因为链表可以在运行时更改其大小。

来源：https://stackoverflow.com/a/65286515/16587692

- teodor mihail