快速排序与堆排序 [英] Quicksort vs heapsort

问题描述

快速排序和堆排序都进行就地排序.哪个更好?哪些应用和案例是首选?

Both quicksort and heapsort do in-place sorting. Which is better? What are the applications and cases in which either is preferred?

推荐答案

这篇论文有一些分析.

另外，来自维基百科:

最直接的竞争对手快速排序是堆排序.堆排序是通常比快速排序，但最坏的情况是运行时间总是 Θ(nlogn).快速排序是通常更快，尽管仍有最坏情况表现的可能性除了 introsort 变体，当情况不好时切换到堆排序被检测到.如果事先知道该堆排序将是有必要，直接使用它会比等待 introsort 更快切换到它.

The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always Θ(nlogn). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant, which switches to heapsort when a bad case is detected. If it is known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it.

这篇关于快速排序与堆排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！