为什么合并sorting优先于快速sorting链接列表

我在一个论坛上阅读以下内容:

合并sorting对于像链接列表这样的不可变数据结构非常有效

当数据存储在内存中时,快速sorting通常比合并sorting更快。 但是,当数据集很大并且存储在外部设备(如硬盘驱动器)上时,合并sorting在速度上是明显的优势。 它最大限度地减less了外部驱动器的昂贵的读取

在链表上操作时,合并sorting只需要less量的辅助存储

有人能帮我理解上面的说法吗? 为什么合并sorting首选sorting巨大的链表? 以及如何最大限度地减less昂贵的读取到外部驱动器? 基本上我想明白为什么要select合并sorting一个大的链表。

快速sorting适用于sorting。 特别是,大部分操作可以通过交换数组中的元素对来定义。 但是,为了做到这一点,通常使用两个指针(或索引等)来“遍历”数组。一个从数组的开始处开始,另一个在结尾处。 然后两个人都朝着中间方向努力(当他们见面时,你完成了一个特定的分区步骤)。 这对文件来说是很昂贵的,因为文件主要是朝着一个方向读取,从头到尾。 从最后开始往回追求通常比较昂贵。

至less在最简单的化身中,合并sorting恰恰相反。 实现它的简单方法只需要在一个方向上查看数据, 但是需要将数据拆分为两个独立的部分,对这些部分进行sorting,然后将它们合并在一起。

通过一个链表,很容易在一个链表中取出(例如)交替的元素,并且操纵这些链接来创build来自这些相同元素的两个链表。 对于一个数组,如果你愿意创build一个与原始数据一样大的副本,那么将元素重新排列成交替的元素就变成了单独的数组,但是否则更加不重要。

同样,如果将源数组中的元素合并到具有数据顺序的新数组中,但是在不创build数据的全新副本的情况下进行合并,则与数组的合并很容易,这完全是另一回事。 使用链表,将两个源列表中的元素合并到一个目标列表中是很简单的 – 再次,您只需操作链接,而不需要复制元素。

至于使用Quicksort为外部合并sorting生成sorting的运行,它确实有效,但它(通常是)次优的。 为了优化合并sorting,您通常需要最大化每个sorting“运行”的长度。 如果您只是读入适合内存的数据,将其快速sorting并写出,则每次运行将被限制为(略小于)可用内存的大小。

尽pipe如此,你可以做得更好一些。 你首先读取一个数据块,而不是使用Quicksort,你会build立一个堆。 然后,当您从堆中将每个项目写入已sorting的“运行”文件时,从input文件中读取另一个项目。 如果它比刚刚写入磁盘的项目大,则将其插入到现有的堆中,然后重复。

较小的项目(即属于已经写入的项目之前)保持独立,并构build到第二个堆中。 当(并且只有当)你的第一个堆是空的,而第二个堆已经接pipe了所有的内存时,你退出写入项目到现有的“运行”文件,并开始一个新的。

这究竟有多有效取决于数据的初始顺序。 在最坏的情况下(input按相反的顺序sorting),它根本就不行。 在最好的情况下(input已经sorting),它可以让你通过input在一次运行中“sorting”数据。 在一般情况下(以随机顺序input),它可以使您每次sorting的运行时间大约加倍,这通常会使速度提高20-25%左右(尽pipe百分比取决于您的数据比可用内存多大)。

快速sorting取决于能够索引到一个数组或类似的结构。 如果可能的话,很难打败Quicksort。

但是你不能很快地直接把索引链接到链表中。 也就是说,如果myList是一个链表,那么myList[x]有可能写出这样的语法,将涉及从列表头开始,跟在第一个x链接之后。 对于Quicksort进行的每次比较,都必须进行两次,而这样做的确会很快。

磁盘上同样的东西:Quicksort将不得不寻找和阅读每一个想要比较的项目。

合并sorting在这些情况下更快,因为它会按顺序读取项目,通常会使log2(N)传递数据。 涉及的I / O要less得多,而链接列表中链接的时间要less得多。

当数据放入内存并且可以直接处理时,Quicksort速度很快。 当数据不适合内存或者当物品很昂贵的时候,Mergesort会更快。

请注意,大文件sorting通常会将文件加载到内存中,然后将其快速sorting并将其写入临时文件,然后重复,直到完成整个文件。 在这一点上有一些块,其中每一块都被sorting,然后程序进行N路合并以产生sorting的输出。

快速sorting会将logging移到列表的中间。 为了将项目移动到索引X,它必须从0开始并一次迭代一条logging。

mergesort将列表拆分成几个小列表,只比较列表的项目头。

合并sorting的设置通常比快速sorting所需的迭代花费更多。 但是,如果列表足够大,或者读取操作很昂贵(如从磁盘读取),则快速sorting所需的时间就成为主要因素。