为什么mergesort更适合链表？

Question

为什么在排序列表而不是快速排序时,mergesort被认为是"走的路"？我在网上看过的一个讲座中听到了这个,并在几个网站上看到过.

Answer 1

快速排序的主要效率来源之一是参考位置,其中计算机硬件经过优化,因此访问彼此靠近的存储位置往往比访问分散在整个存储器中的存储位置更快.快速排序中的分区步骤通常具有出色的局部性,因为它访问前后靠近的连续数组元素.因此,quicksort往往比其他排序算法(如heapsort)表现得更好,即使它经常进行大致相同数量的比较和交换,因为在heapsort的情况下,访问更加分散.

此外,快速排序通常比其他排序算法快得多,因为它可以就地运行,而无需创建任何辅助数组来保存临时值.与merge sort之类的东西相比,这可能是一个巨大的优势,因为分配和释放辅助数组所需的时间是显而易见的.就地操作还可以改善快速入口的位置.

使用链接列表时,这些优点都不一定适用.因为链表单元格通常分散在整个存储器中,所以访问相邻链表单元格没有位置加值.因此,quicksort的巨大性能优势之一被消耗殆尽.同样,就地工作的好处不再适用,因为合并排序的链表算法不需要任何额外的辅助存储空间.

也就是说,快速排序在链表上仍然非常快.合并排序往往更快,因为它更均匀地将列表拆分为一半,并且每次迭代执行合并所做的工作少于执行分区步骤.

希望这可以帮助!