为什么合并排序更适合链表？

Question

为什么在对列表进行排序时，mergesort被认为是“最佳选择”，而不是快速排序？我在网上看到的一次演讲中听到了这一点，并在几个网站上看到了它。

Answer 1

快速排序效率的主要来源之一是locality of reference，其中对计算机硬件进行了优化，使得访问彼此靠近的内存位置往往比访问分散在内存中的内存位置更快。快速排序中的分区步骤通常具有很好的局部性，因为它访问靠近前面和后面的连续数组元素。因此，快速排序往往比其他排序算法(如堆排序)执行得更好，尽管它通常执行大致相同数量的比较和交换，因为在堆排序的情况下，访问更加分散。

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

在使用链表时，这些优点都不一定适用。因为链接列表单元格通常分散在内存中，所以访问相邻的链接列表单元格不会带来局部性的好处。因此，快速排序的巨大性能优势之一被吃掉了。同样，就地工作的好处不再适用，因为合并排序的链表算法不需要任何额外的辅助存储空间。

也就是说，快速排序在链表上仍然非常快。合并排序只是倾向于更快，因为它更均匀地将列表一分为二，并且在每次迭代中进行合并比进行分区步骤所做的工作更少。

希望这能有所帮助！

Answer 2

find()的开销对快速排序的危害比合并排序更大。

合并排序对数据执行更多的“短范围”操作，使其更适合于链表，而快速排序更适合随机访问数据结构。