algorithm - 快速排序优于堆排序

Question

堆排序的最坏情况复杂度为 O(nlogn)，而 Quicksort 为 O(n^2)。但经验证据表明快速排序更优越。这是为什么？

Answer 1

其中一个主要因素是快速排序具有更好的引用位置——下一个要访问的内容通常在内存中与您刚刚查看的内容接近。相比之下，heapsort 跳跃得更多。由于靠得很近的事物可能会缓存在一起，因此快速排序往往更快。

但是，快速排序的最坏情况性能明显比堆排序差。因为一些关键应用程序需要保证速度性能，堆排序是处理此类情况的正确方法。