algorithm - 中位数快速排序 O(n log n)

Question

我真的不明白为什么我们不总是选择中值元素作为基准。这可以在 O(n) 中完成，因此总运行时间为 O(n log n)。

我只是假设在中值搜索的 O(n) 中可能隐藏了一个很大的常数。

Answer 1

来自Wikipedia Quicksort page :

Conversely, once we know a worst-case selection algorithm is available, we can use it to find the ideal pivot (the median) at every step of quicksort, producing a variant with worst-case O(n log n) running time. In practical implementations, however, this variant is considerably slower on average.

换句话说，强制保证O(n log n)的代价一般是不值得付出的。该页面以及 selection algorithms 上有更多信息。页面。