快速排序 - 为什么随机数据透视？

Question

看过不同的快速排序算法：

我没有看到使用随机数据透视的好处。与使用最后一个元素相比，递归调用quickSort（a []，int p，int r），选择随机数是否会随机提高效率？

THX

Answer 1

使用随机摆动的原因是，不让对手让你的算法命中最坏情况下的时间。换句话说，随机旋转你的算法在所有数据集上的预期性能同样好。