为什么在对链表进行排序时，归并排序比快速排序更受青睐

Question

为什么在对链表进行排序时，归并排序比快速排序更受青睐

algorithmquicksortmergesort

60

我在论坛上读到以下内容：

归并排序对于像链表这样的不可变数据结构非常有效

而且

当数据存储在内存中时，快速排序通常比归并排序更快。然而，当数据集很大并且存储在外部设备（如硬盘）上时，归并排序在速度方面是明显的赢家。它最小化了昂贵的外部驱动器读取次数

以及

在操作链表时，归并排序仅需要少量的辅助存储空间

有人可以帮我理解上述论点吗？为什么归并排序适用于对大型链表进行排序？以及它如何最小化对外部驱动器的昂贵读取？基本上，我想了解为什么会选择使用归并排序来对大型链表进行排序。

答：归并排序被认为是一种高效的排序算法，特别是对于处理大型数据集时。对于链表这样的数据结构，它比快速排序更适合，因为链表的随机访问时间很长，而归并排序的顺序访问方式更适合链表。此外，归并排序只需要常量级别的辅助存储空间来处理链表，而快速排序则需要线性空间。当数据存储在外部设备上时，归并排序之所以更快是因为它可以通过一次读取大块数据并将其分成小块来最小化访问外部设备的次数。无需反复从外部驱动器中读取数据，可以大大减少排序时间。

- maxpayne

3个回答

20

快速排序取决于能够对数组或类似结构进行索引。如果可以这样做，很难击败快速排序。

但是，无法快速直接地索引到链表中。也就是说，如果myList是一个链表，那么myList[x]（如果有这样的语法）将涉及从列表头开始，并沿着第一个x个链接进行跟踪。这必须对快速排序进行每次比较两次，这会变得非常昂贵。

同样，在磁盘上也是如此：快速排序将不得不搜索并读取它想要比较的每个项。

在这些情况下，归并排序更快，因为它按顺序读取项目，通常对数据进行log2(N)次传递。涉及的I/O要少得多，并且在链表中花费的时间也要少得多。

当数据适合内存并且可以直接寻址时，快速排序很快。当数据无法适应内存或访问某个项很昂贵时，归并排序更快。

请注意，大型文件排序通常会将尽可能多的文件加载到内存中，对其进行快速排序，并将其写入临时文件中，并重复此过程，直到遍历整个文件。在这一点上，会产生一些块，每个块都已排序，然后程序进行N路合并以生成已排序的输出。

- Jim Mischel

3

为什么我们说快速排序需要直接访问？这是因为在分区过程中需要进行反向迭代吗？如果是这样，不能使用双向链表来解决吗？ - Ayush Chaudhary

1

@AyushChaudhary 我想在使用双向链表时，重点是让枢轴点执行快速排序算法。一些实现使用结构的中间部分。反复计算可能会减少一些性能。但是，一些归并排序实现也需要使用结构的中间部分。所以，我想这个性能应该是相同的？ - Y_Y

3

快速排序会将记录移动到列表的中间。为了将项目移动到索引X，它必须从0开始，逐个迭代一条记录。

归并排序将列表分成几个小列表，并仅比较列表头中的项。

归并排序的设置通常比快速排序所需的迭代更昂贵。但是，当列表足够大或读取很昂贵（例如来自磁盘），快速排序迭代所需的时间成为主要因素。

- cadrell0

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jerry Coffin · Accepted Answer

快速排序适用于原地排序。具体而言，大多数操作可以定义为在数组中交换一对元素。为此，通常需要使用两个指针（或索引等）“遍历”数组。一个从数组的开头开始，另一个从末尾开始。然后两者沿着数组向中间移动（当它们相遇时，您完成了特定分区步骤）。由于文件主要面向从头到尾的单向读取，因此这很耗费资源。反向从末尾开始查找通常比较昂贵。

至少在其最简单的形式中，归并排序几乎完全相反。实现它的简单方法只需要沿一个方向查看数据，但涉及将数据分成两部分、对这些部分进行排序，然后将它们合并在一起。

对于链表，很容易从一个链表中获取交替的元素，并操纵链接以从这些相同的元素创建两个链表。对于数组，如果愿意创建与原始数据一样大的副本，则可以轻松地重新排列元素，使交替元素进入不同的数组，否则就变得更加复杂。

同样，如果将源数组中的元素合并到按顺序排列的新数组中，则使用数组进行合并很容易，但要在原地进行而不创建整个新数据的副本，则完全是另一回事。对于链表，将两个源列表中的元素合并到单个目标列表中非常简单——您只需操纵链接，而无需复制元素。

至于使用快速排序来生成外部归并排序的排序运行，它确实有效，但通常不是最优选择。为了优化归并排序，通常希望在生成每个排序“运行”时最大化其长度。如果简单地读入适合内存的数据，然后进行快速排序并写出它，那么每个运行将受限于可用内存的大小（略小于可用内存的大小）。

一般情况下，你可以比这种方式做得更好。你首先读入一块数据，但不是用快速排序算法，而是建立一个堆。然后，当你从堆中把每个元素写到排序后的“运行”文件中时，你会从输入文件中再读取另一个元素。如果它比你刚刚写入磁盘的元素大，你就将它插入到现有的堆中，然后重复该过程。

那些较小的元素（即属于已经写入的元素之前的元素），你要保留并构建成第二个堆。只有当第一个堆为空且第二个堆占据了所有内存空间时，你才停止向现有的“运行”文件写入元素，并开始新的操作。

这种方法的效果取决于数据的初始顺序。在最坏的情况下（输入按相反顺序排列），它根本没有作用。在最好的情况下（输入已经排序），它让你可以在单次输入中“排序”数据。在平均情况下（输入的顺序是随机的），它使每个排序后的运行时间增加约一倍，这通常会提高速度约20-25%（尽管百分比取决于数据的大小与可用内存的差异）。