为什么在对链接列表进行排序时优先使用合并排序而不是快速排序

为什么在对链接列表进行排序时优先使用合并排序而不是快速排序

快速排序非常适合就地排序。特别是，大多数 *** 作可以根据交换数组中的元素对来定义。为此，通常使用两个指针（或索引等）在数组中“遍历”，一个指针从数组的开头开始，另一个指针从数组的结尾开始。然后两者都朝着中间方向工作（当它们相遇时，您将完成一个特定的分区步骤）。这对于文件来说是昂贵的，因为文件主要是针对从头到尾的单一方向读取的。从头开始然后向后寻找通常是相对昂贵的。

至少在最简单的形式上，合并排序几乎是相反的。实现它的简单方法只需要在一个方向上浏览数据， 而是
将数据分为两个单独的部分，对这些部分进行排序，然后将它们合并在一起。

使用链表，可以很容易地在一个链表中采用（例如）交替元素，然后 *** 纵这些链以从相同元素创建两个链表。对于数组，如果您愿意创建与原始数据一样大的副本，而又不那么琐碎，则重新排列元素以便将交替的元素放入单独的数组很容易。

同样，如果将源数组中的元素按顺序合并到具有数据的新数组中，则与数组合并很容易-
但是在不创建数据的全新副本的情况下就地进行合并则完全不同。使用链接列表，将两个源列表中的元素合并到一个目标列表中是微不足道的-
再次，您只需 *** 作链接，而无需复制元素。

至于使用Quicksort生成外部合并排序的排序运行，它确实可以工作，但通常（确定）次优。要优化合并排序，通常需要在生成每个排序的“运行”时将其长度最大化。如果您只读取适合内存的数据，然后对其进行快速排序并写出，则每次运行将被限制为（略小于）可用内存的大小。

通常，您可以做得比那更好。您从读取数据块开始，但是您没有在上面使用Quicksort，而是建立了一个堆。然后，当您将每一项从堆中写入已排序的“运行”文件时，您将从输入文件中读取
另 一项。如果它大于您刚刚写入磁盘的项目，则将其插入到现有堆中，然后重复。

较小的项目（即，在已写入的项目之前属于项目）分开存放，并放入第二个堆中。当（且仅当）第一个堆为空且第二个堆已接管所有内存时，您停止将项目写入现有的“运行”文件，并开始一个新的堆。

确切的效果取决于数据的初始顺序。在最坏的情况下（输入以相反的顺序排序）根本没有好处。在最佳情况下（输入已排序），它使您可以通过输入一次对数据进行“排序”。在一般情况下（以随机顺序输入），它可使您将每次排序运行的长度大约增加一倍，这通常会提高速度
约 20-25％（尽管百分比会根据数据比可用内存大多少而变化） ）。