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

Question

我正在考虑一种快速排序算法，选择分区函数中的枢轴作为数组中三个（均匀）随机选择的项目的中位数。有谁知道平均案例的运行时间？

Answer 1

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

有了这个假设，即使你选择枢轴作为一个随机元素，平均运行时间也是 O(n * log n)。最乐观的情况也是 O(n * log n)。选择三个随机元素的中位数不会使平均情况变得更糟，因此它也必须是 O(n * log n)。通过查看中位数，您获得的是与平均值的较小偏差。这种版本的快速排序更加倒霉。

如果元素不必不同，请考虑一种情况，它们都相等。如果你的算法在 O(n * log n) 时间内仍然有效，它可能都是一样的。