为什么在实践中使用quicksort？

Question

Quicksort具有最差的O(n ²)性能,但仍然在实践中广泛使用.为什么是这样？

Answer 1

你不应该只关注最坏情况,只关注时间的复杂性.它更多的是平均而不是最差,而且是时间和空间.

快速排序:

• 平均时间复杂度为Θ(n log n);
• 可以用空间复杂度Θ(log n)来实现;

还考虑到大O表示法没有考虑任何常量,但在实践中,如果算法快几倍,它确实会有所不同.Θ(n log n)表示该算法在K  n  log(n)中执行,其中K是常数.Quicksort是具有最低K的比较排序算法.

Answer 2

O(nlogn)QuickSort的平均渐近阶数是,并且由于较小的常数(更紧密的循环),它通常比堆操作更有效.事实上,有一个理论线性时间中值选择算法,你可以用来总是找到最佳的枢轴,从而导致最坏的情况O(nlogn).但是,正常的QuickSort通常比这个理论上快.

为了使其更合理,请考虑QuickSort完成的概率.这只是意味着它几乎永远不会遇到那种糟糕的情况.O(n2)1/n!

Answer 3

有趣的是,quicksort平均比mergesort执行更多的比较 - 快速排序为1.44 n lg n(预期),而mergesort为n lg n.如果所有重要的事情都是比较,那么mergesort将比quicksort更受欢迎.

快速排序快速的原因是它具有许多其他理想的属性,在现代硬件上非常有效.例如,quicksort不需要动态分配.它可以在原始数组上就地工作,仅使用O(log n)堆栈空间(如果正确实现,则最坏情况)来存储递归所需的堆栈帧.尽管可以使用mergesort来执行此操作,但这样做通常会在合并步骤中造成巨大的性能损失.其他排序算法(如heapsort)也具有此属性.

此外,quicksort具有出色的参考位置.如果使用Hoare的就地分区算法完成分区步骤,则基本上是从阵列两端向内执行的两个线性扫描.这意味着快速排序将具有非常少量的高速缓存未命中,这在现代体系结构中对性能至关重要.另一方面,Heapsort没有非常好的局部性(它遍布整个数组),尽管大多数mergesort实现具有合理的局部性.

Quicksort也非常可并行化.一旦发生初始分区步骤以将阵列分成更小和更大的区域,那么这两个部分可以彼此独立地分类.许多排序算法可以并行化,包括mergesort,但由于上述原因,并行快速排序的性能往往优于其他并行算法.另一方面,Heapsort没有.

快速排序的唯一问题是它降级到O(n ²)的可能性,在大数据集上这可能非常严重.避免这种情况的一种方法是让算法对自身进行内省,并在其退化的情况下切换到较慢但更可靠的算法之一.这种称为introsort的算法是一种很好的混合排序算法,它可以在没有病态的情况下获得快速排序的许多好处.

综上所述:

• Quicksort就位,除了递归中使用的堆栈帧,它占用O(log n)空间.
• Quicksort具有良好的参考地点.
• Quicksort很容易并行化.

这解释了为什么quicksort倾向于优于在纸上可能更好的排序算法.

希望这可以帮助!

Answer 4

因为平均而言，它是最快的比较排序（就经过的时间而言）。