performance - 当我选择中值或众数之类的枢轴时，快速排序没有更快地工作

Question

我在测试我的 Quicksort 实现时遇到了问题。有人告诉我，当我们选择诸如中位数之类的数字作为枢轴时，该算法会更好地工作，但是，我的结果不是我所期望的。通常，当我选择第一个或最后一个元素作为枢轴时，会发生最好的情况，并且它们都是随机数，就像数组中的所有其他元素一样。我正在运行大量测试（超过 5000 次）并检查平均时间（没有时间寻找众数或中位数）。谢谢你。

Answer 1

计算数组的中位数或众数是一项昂贵的操作（尤其是选择中位数），因此即使您将获得良好的枢轴，寻找这些枢轴的额外开销也可能会消耗您的大部分效率收益。

随机快速排序（每次选择一个随机枢轴）最终成为实践中更好的选择。它的最坏情况是指数级不可能的，并且预期它会在 O(n log n) 时间内运行。生成随机数或伪随机数也比查找数组的中位数或众数要快得多。

最后，如果您确实选择了数组的模式，则根本无法保证您获得了良好的支点。事实上，如果你有一个没有重复的数组并且你选择模式的实现总是选择最小值或最大值，这可能会导致病态的情况。这将退化为 Θ(n ² ) 时间。

希望这可以帮助！