max*_*yne 60 algorithm mergesort quicksort
我在论坛中阅读了以下内容:
合并排序对于链接列表等不可变数据结构非常有效
和
当数据存储在内存中时,快速排序通常比合并排序更快.但是,当数据集很大并且存储在外部设备(如硬盘驱动器)上时,合并排序在速度方面是明显的赢家.它最大限度地减少了外部驱动器的昂贵读取
和
在链表上操作时,合并排序只需要少量的辅助存储
有人能帮助我理解上述论点吗？为什么合并排序首选排序庞大的链表？它如何最大限度地减少对外部驱动器的昂贵读取？基本上我想了解为什么会选择合并排序来排序大链表.
Jer*_*fin 48
快速排序适用于就地分类.特别是,大多数操作可以根据交换数组中的元素对来定义.但是,要做到这一点,通常使用两个指针(或索引等)"遍历"数组.一个从数组的开头开始,另一个在结束时开始.然后两者都向中间工作(当他们见面时你完成了特定的分区步骤).这对于文件来说是昂贵的,因为文件主要面向从一个方向读取,从头到尾.从结束开始并向后寻求通常相对昂贵.
至少在其最简单的化身中,合并排序几乎完全相反.实现它的简单方法只需要在一个方向上查看数据,但需要将数据分成两个单独的部分,对部分进行排序,然后将它们合并在一起.
使用链接列表,可以轻松地(例如)在一个链表中交替使用元素,并操纵链接以从这些相同的元素创建两个链接列表.使用数组,如果您愿意创建与原始数据一样大的副本,那么重新排列元素使交替元素进入单独的数组很容易,但在其他方面则更为重要.
同样,如果您将源数组中的元素合并到一个新数组中并且数据按顺序合并,那么与数组合并很容易 - 但是在没有创建数据的全新副本的情况下这样做是完全不同的故事.使用链接列表,将两个源列表中的元素合并到一个目标列表中是微不足道的 - 再次,您只需操作链接,而无需复制元素.
至于使用Quicksort为外部合并排序生成排序运行,它确实有效,但它(通常)是次优的.要优化合并排序,通常需要在生成时最大化每个排序"运行"的长度.如果您只是读入适合内存的数据,请将其编写并写出来,每次运行将限制为(略小于)可用内存的大小.
但是,作为一项规则,你可以做得比这更好.首先阅读一个数据块,但不是在其上使用Quicksort,而是构建一个堆.然后,当您将每个项目从堆中写入已排序的"运行"文件时,您将从输入文件中读取另一个项目.如果它大于您刚写入磁盘的项目,则将其插入现有堆中,然后重复.
较小的项(即,在已经写入的项之前属于),您保持独立,并构建到第二个堆中.当(并且仅当)您的第一个堆为空,并且第二个堆已经占用了所有内存时,您将退出将项目写入现有的"运行"文件,并从新文件开始.
这究竟有多有效取决于数据的初始顺序.在最坏的情况下(输入按逆序排序)它根本没有好处.在最好的情况下(输入已经排序),它允许您通过输入在一次运行中"排序"数据.在一般情况下(以随机顺序输入),它允许您将每个排序运行的长度大约加倍,这通常会将速度提高大约 20-25%(尽管百分比取决于您的数据大于可用内存的大小) ).
Jim*_*hel 20
Quicksort依赖于能够索引到数组或类似结构.如果可能的话,很难击败Quicksort.
但是你不能很快直接索引到链表.也就是说,如果myList是链表,那么myList[x],是否可以编写这样的语法,将涉及从列表的头部开始并跟随第一个x链接.对于Quicksort所做的每一次比较,这都必须完成两次,而且这将非常快.
磁盘上也是如此:Quicksort必须寻找和读取它想要比较的每个项目.
在这些情况下合并排序更快,因为它按顺序读取项目,通常使log2(N)通过数据.涉及的I/O要少得多,并且链接列表中的链接花费的时间要少得多.
当数据适合内存并且可以直接寻址时,Quicksort很快.当数据不适合内存或者到达项目的成本很高时,Mergesort会更快.
请注意,大文件排序通常会尽可能多地将文件加载到内存中,然后将其写入Quicksort并将其写入临时文件,并重复直到它已经遍历整个文件.此时存在一些块,每个块都被排序,然后程序进行N路合并以产生排序的输出.