performance - 当我选择中位数或模式等枢轴时，快速排序的速度并不快

Question

我在测试快速排序实现时遇到了问题。有人告诉我，当我们选择一个数字(例如中位数)作为基准时，该算法会更好地工作，但是，我的结果不是我预期的。通常，最好的情况是当我选择第一个或最后一个元素作为主元时，它们都是随机数，就像数组中的所有其他元素一样。我正在运行大量测试(超过 5000 个)并检查平均时间(没有时间寻找众数或中位数)。谢谢。

Answer 1

计算数组的中位数或众数是一项代价高昂的操作(尤其是选择中位数)，因此即使您会获得良好的枢轴，查找这些枢轴的额外开销也可能会耗尽您的大部分效率 yield 。

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

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

希望这对您有所帮助!