快速排序中位数3运行时间

Question

我正在考虑快速排序算法，选择分区函数中的枢轴作为数组中三个（一致）随机选择项的中值。有人知道一般情况下的运行时间吗？

Answer 1

小假设：所有元素都不相同。

有了这个假设，即使您选择pivot作为一个随机元素，平均运行时间为O（n * log n）。 最乐观的情况也是O（n * log n）。 选择三个随机元素的中位数不会使平均情况更糟糕，所以它也必须是O（n * log n）。 通过查看中位数得出的结果与平均数的偏差较小。 这种快速排序的版本更不好运气。

如果元素不必不同，请考虑一个案例，他们都是平等的。 如果你的算法仍然在O（n * log n）时间内工作，它可能会完全相同。