algorithm - 对链接列表进行排序时,合并排序优先于快速排序

  显示原文与译文双语对照的内容
110 0

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

合并排序对于不可变 datastructures ( 如链接列表) 非常有效

当数据存储在内存中时,快速排序通常比合并排序快。 然而,当数据集庞大,存储在诸如硬盘这样的外部设备上时,合并排序在速度方面是明显的赢家。 它最小化了昂贵的外部驱动器读取

在对链表进行操作时,合并排序只需要少量的辅助存储

有人能帮助我理解上面的论点? 为什么合并排序对排序大型链接列表是首选的? 它如何将昂贵的读取到外部驱动器? 基本上我想理解为什么要选择合并排序来排序大链接列表。

时间: 原作者:

68 3

快速排序依赖于能够索引到 array 或者类似结构。 如果有可能的话,快速快速的快速排序是很困难的。

但是不能直接将索引直接索引到链接列表中。 也就是说,如果 myList 是链接列表,那么 myList[x] 就可以编写这种语法,包括从列表的头部开始,并且遵循第一个 x 链接。 对于每个比较的比较,必须要做两次,而且这会得到昂贵的实际速度。

在磁盘上相同的东西:快速排序必须寻找和阅读它想要比较的每个项目。

由于在这些情况下,合并排序的速度更快,通常会使 log2(N) 通过数据。 相关的I/O 越少,链接列表中的链接花费的时间就越少。

快速排序在数据符合内存时快速,可以直接寻址。 当数据不适合内存或者成本高的时候,就更快了。

注意,大型文件排序通常只能将文件加载到内存中,并将它的写入临时文件。 这里时有一些块,每个块都排序,然后程序进行n 路合并以生成排序的输出。

原作者:
...