快速排序与合并排序

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

1> Benoît..：

---

请参阅维基百科上的Quicksort:

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

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

---

如果使用随机的64位数*N*预先初始化快速排序,并且每个部分的轴都在索引*N*mod*SectionSize*,则算法证明任何复杂度C的概率C,其中C比随着输入大小的增加,O(n log n)呈指数减小.

---

快速排序比合并排序多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> 小智..：

---

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

3> Marcin Gil..：

---

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

看到这个比较.

你也可以直观地看到它.

---

那是错的.quicksort的可接受实现首先对最小的子范围进行排序.

4> Brandon Yarb..：

---

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

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

---

mergesort闪耀的地方是你需要一个稳定的排序(比较相等的元素不重新排列)或当你使用顺序(而不是随机访问)"内存"时(例如你可以使用磁带驱动器有效地合并).

---

@j_random_hacker:你的磁带机示例有点模糊; 更常见的例子可能是在从网络连接接收数据时对数据进行排序,或者排序不允许有效随机访问的数据结构,如链接列表

5> bragboy..：

---

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

快速排序能够在156毫秒内完成,而 Merge排序在247毫秒内完成相同的操作

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

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

6> Dario..：

---

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

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

---

链表的问题不是可变性,而是缺乏有效的随机访问,即你坚持使用在线算法(合并排序,插入排序)

7> 小智..：

---

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