快速排序与合并排序

Question

为什么快速排序比合并排序更好？

Answer 1

通常,快速排序在实践中明显快于其他Θ(nlogn)算法,因为其内循环可以在大多数架构上有效实现,并且在大多数现实世界数据中,可以进行设计选择,从而最小化需要二次方的概率时间.

请注意,非常低的内存要求也是一大优点.

如果使用随机的64位数*N*预先初始化快速排序,并且每个部分的轴都在索引*N*mod*SectionSize*,则算法证明任何复杂度C的概率C,其中C比随着输入大小的增加,O(n log n)呈指数减小. (23认同)
+1。这是使用快速排序的一个很好的理由。 (3认同)
快速排序比合并排序多39%,但快速排序中的掉期数量小于合并排序.CPU的交换操作比比较操作更昂贵,如[here]所述(http://stackoverflow.com/questions/27887198/which-is-more-expensive-operation-swap-or-comparison-in-integer-array-在-JAVA).在家用笔记本电脑上进行测试快速排序需要"0.6秒"来对millon项进行排序,而不像合并排序需要"1秒",其中插入排序需要"2.8小时". (2认同)

Answer 2

当数据存储在内存中时,快速排序通常比合并排序更快.但是,当数据集很大并且存储在外部设备(如硬盘驱动器)上时,合并排序在速度方面是明显的赢家.它最大限度地减少了外部驱动器的昂贵读取,同时也很适合并行计算.

Answer 3

对于合并排序最坏的情况是O(n*log(n)),对于快速排序:O(n²).对于其他情况(平均,最好)都有O(n*log(n)).但是,快速排序是空间常量,其中合并排序取决于您要排序的结构.

你也可以直观地看到它.

Answer 4

虽然快速排序通常是比合并排序更好的选择,但合并排序肯定是更好的选择.最明显的时间是,你的算法运行速度比O(n ^ 2)更重要.Quicksort通常比这更快,但是考虑到理论上最差的输入,它可以在O(n ^ 2)中运行,这比最差的可能合并排序更糟糕.

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

mergesort闪耀的地方是你需要一个稳定的排序(比较相等的元素不重新排列)或当你使用顺序(而不是随机访问)"内存"时(例如你可以使用磁带驱动器有效地合并). (6认同)
@j_random_hacker:你的磁带机示例有点模糊; 更常见的例子可能是在从网络连接接收数据时对数据进行排序,或者排序不允许有效随机访问的数据结构,如链接列表 (6认同)

Answer 5

我个人想亲自测试快速排序和合并排序之间的区别,并查看1,000,000个元素的样本的运行时间.

然而,快速排序数据是随机的,如果数据是随机的,则快速排序表现良好,而不是合并排序的情况,即合并排序在数据排序与否时无关地执行.但是合并排序需要一个完整的额外空间,而快速排序则不是它的就地排序

我已经为他们编写了全面的工作计划,也将为说明图片.

@compski：我在您的代码的第 14 行看到了一个问题。而不是使用一个额外的数组空间，您正在创建无数会杀死内存的数组。这是仅使用一个额外数组的示例（参见第 24 行）。http://tech.bragboy.com/2010/01/merge-sort-in-java.html 让我知道这回答了你的问题。如果没有，我可以帮助你更多。 (2认同)

Answer 6

除了其他之外:合并排序对于链接列表等不可变数据结构非常有效,因此是(纯粹)函数式编程语言的不错选择.

实施不当的快速排序可能存在安全风险.

Answer 7

快速排序到位。您只需要在分区功能期间交换数据位置。Mergesort需要更多的数据复制。您需要另一个临时存储（通常与原始数据阵列大小相同）才能用于合并功能。