快速排序 vs 归并排序

Question

快速排序 vs 归并排序

algorithmsorting

124

为什么快速排序可能比归并排序更好？

- Ganesh M

1

@ qrdl：排序算法的属性远不止速度。 - Georg Schölly

在一个有16个寄存器的处理器上，比如64位模式下的PC，对于像排序伪随机整数数组这样的情况，四路归并排序可以与标准快速排序一样快或稍微快一些。4路归并排序执行的总操作次数与2路相同，但是它的比较次数是1.5倍，移动次数是0.5倍，并且比较的缓存友好性比移动高一些。公平地说，由于使用4路归并排序是一种优化，因此双轴快速排序应该会更快一点。大多数计算机都有几千兆字节的内存，所以归并排序的空间开销通常不是问题。 - rcgldr

11个回答

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

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

- DarthVader · Answer 1

快速排序是原地排序。你只需要很少的额外内存，这非常重要。

选择好的中位数可以使其更加高效，但即使选择不好的中位数，也能保证Theta(nlogn)的时间复杂度。