问快速排序与合并排序

EN

当数据存储在内存中时，快速排序通常比合并排序快。然而，当数据集很大并且存储在硬盘驱动器等外部设备上时，合并排序在速度方面显然是赢家。它最大限度地减少了对外部驱动器的昂贵读取，同时也非常适合并行计算。

虽然快速排序通常是比合并排序更好的选择，但在某些情况下，合并排序在理论上是更好的选择。最明显的情况是算法的运行速度要快于O(n^2)，这非常重要。快速排序通常比这更快，但考虑到理论上最糟糕的输入，它的运行时间可能是O(n^2)，这比最糟糕的合并排序更糟糕。

快速排序也比合并排序更复杂，特别是如果你想编写一个真正可靠的实现，所以如果你的目标是简单性和可维护性，合并排序成为一种很有前途的替代方案，性能损失非常小。

我个人想亲自测试一下Quick sort和merge sort之间的区别，并查看了一个包含1,000,000个元素的样本的运行时间。

Quick sort was able to do it in 156 milliseconds与Merge sort did the same in 247 milliseconds

然而，快速排序数据是随机的，如果数据是随机的，快速排序效果很好，而合并排序不是这样，也就是说，无论数据是否排序，合并排序都执行相同的操作。但是合并排序需要一个完整的额外空间，而快速排序不需要，因为它是就地排序

我已经为他们写了全面的工作方案，也将插图。