快速排序和归并排序对内存中适合的顺序数据与慢速访问磁盘上的顺序数据的性能比较。

Question

快速排序和归并排序对内存中适合的顺序数据与慢速访问磁盘上的顺序数据的性能比较。

javaalgorithmsortingquicksortmergesort

14

以下引用来自Wikipedia Merge Sort页面的“与其他排序算法比较”部分：

在典型的现代架构中，高效的快速排序实现通常优于归并排序以对RAM-based数组进行排序。[需要引证]另一方面，归并排序是一种稳定的排序方法，更有效地处理难以访问的连续媒体。

我的问题：

如果要排序的数据可以全部放入内存中，为什么快速排序比归并排序表现更好？如果所有需要的数据都被缓存或在内存中，那么访问快速排序和归并排序不都应该很快吗？
为什么归并排序在处理访问缓慢的顺序数据（例如在数据无法全部放入内存的情况下从磁盘中读取）时更有效率？
在由n个元素组成的原始数据（数据是连续的）数组arr中。在归并排序中必须读取和比较的元素对是arr[0]和arr[n/2]（发生在最后合并）。现在考虑在快速排序中必须读取和比较的元素对是arr[1]和arr[n]（发生在第一次分区，假设我们将随机选择的枢轴与第一个元素交换）。我们知道数据是以块的形式读取并加载到缓存或磁盘中（如果我错了，请纠正我），那么使用归并排序时，所需数据在加载到一个块中的可能性就更大了吗？它似乎总是比较更接近的元素，因此归并排序似乎总是更占优势。我知道这是错误的（请参见下面的图表），因为快速排序显然更快......我知道归并排序不是原地排序，需要额外的内存，这可能会减慢速度。除此之外，我的分析中还缺少哪些要素？

这些图片来自于普林斯顿大学计算机科学中的归并排序和快速排序幻灯片。

我的动机：

我想理解上述概念，因为它们是为什么在排序链表或非连续数据时使用归并排序，而在排序数组或连续数据时使用快速排序的主要原因之一。以及为什么在Java中使用归并排序来对对象进行排序，而使用快速排序来对基本类型进行排序。

更新：Java 7 API实际上使用TimSort来对对象进行排序，这是归并排序和插入排序的混合体。对于基本类型，则使用双轴快速排序。这些更改自Java SE 7开始实施。这与排序算法的稳定性有关。为什么Java的Arrays.sort方法使用两种不同的排序算法处理不同类型的数据？

编辑：

我希望得到一个回答，涉及以下方面：

我知道这两种排序算法在移动次数、读取和比较方面有所不同。如果这些原因导致了我在问题列表中看到的行为（我怀疑），那么请详细解释排序算法的步骤和过程是如何导致在从磁盘或内存中获取数据时具有优势或劣势的。
欢迎提供示例。我更喜欢通过示例学习。

注意：如果您正在阅读@rcgldr的答案，请查看我们在聊天室中的对话，其中有很多好的解释和细节。https://chat.stackoverflow.com/rooms/161554/discussion-between-rcgldr-and-oliver-koo

- OLIVER.KOO

1

在一台典型的个人电脑上，快速排序不会比归并排序快3倍，而是会快10%到20%，具体取决于快速排序中用于避免最坏情况的检查。 - rcgldr

1个回答

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

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

- rcgldr · Accepted Answer

主要区别在于归并排序需要移动的数据更多，但比快速排序少比较次数。即使在对本地类型数组进行排序的情况下，快速排序仅比归并排序快大约15％，至少在我使用伪随机64位无符号整数的大型数组进行测试时如此。这应该是快速排序的最佳情况，在我的系统上（Intel 3770K 3.5GHz，Windows 7 Pro 64位，Visual Studio 2015，对1600万个伪随机64位无符号整数进行排序），快速排序用时1.32秒，而归并排序用时1.55秒，1.32/1.55 ~= 0.85，因此快速排序比归并排序快约15％。我的测试使用了没有检查避免最坏情况O（n ^ 2）时间或O（n）空间的快速排序。随着对快速排序添加检查以减少或防止最坏情况（例如，如果递归变得太深，则回退到堆排序），速度优势会降至不到10％（这是我在VS2015的std :: sort（修改的快速排序）与std :: stable_sort（修改的归并排序）之间获得的差异）。

若要对“字符串”进行排序，则更可能正在对指向这些字符串的指针（或引用）数组进行排序。归并排序更快，因为移动涉及指针，而比较涉及间接级别和字符串比较。

选择快速排序而不是归并排序的主要原因不是速度，而是空间需求。归并排序通常使用与原始数组大小相同的第二个数组。快速排序和自顶向下的归并排序还需要递归的log（n）堆栈帧，而对于快速排序，限制堆栈空间为log（n）堆栈帧是通过仅对较小分区进行递归并循环回到处理更大分区来完成的。

就缓存问题而言，大多数最近的处理器具有4或8路关联高速缓存。在归并排序期间，在两个输入运行中，其中一个输出运行将位于3个高速缓存线之一中。快速排序在交换之前会扫描数据，因此扫描的数据将位于高速缓存中，尽管如果正在比较/交换的两个元素相距足够远，则在单独的行中。

对于外部排序，通常采用底部向上归并排序的某种变体。这是因为归并操作是顺序执行的（唯一的随机访问发生在开始一个新运行对时），这在硬盘或者在过去的老式磁带驱动器中是很快的（需要至少3个磁带驱动器）。每次读取或写入可以针对非常大的数据块进行，这减少了硬盘中每个元素的平均访问时间，因为每个I/O操作都会读取或写入大量的数据元素。

值得注意的是，大多数库中的归并排序也是底部向上归并排序的某种变体。自顶向下归并排序主要是作为教学环境的实现。

如果在16个寄存器的处理器上（例如64位模式下的X86），对本地类型的数组进行排序，其中8个寄存器用作4个运行的起始和结束指针（或引用），那么4路归并排序通常与快速排序相当或略快，假定编译器将指针或引用优化为基于寄存器的方式。这是类似于快速排序的一个折衷方案，4路归并排序比传统的2路归并排序执行更多的比较操作（1.5倍）但移动元素更少（0.5倍）。

需要注意的是，这些排序是CPU密集型而不是内存密集型。我制作了一个多线程版本的底部向上归并排序，在使用4个线程的情况下，排序速度提高了3倍。以下链接为使用4个线程的Windows示例代码:

https://codereview.stackexchange.com/questions/148025/multithreaded-bottom-up-merge-sort