algorithm - 随机快速排序

Question

实现随机快速排序的两种方法，

方法一:选择一个随机枢轴

方法 2:生成输入的随机排列并将其提供给选择第一个元素作为主元的快速排序

method1 和 method2 在随机化方面是否相同？

注意:看起来方法 2 产生所有分区的可能性相同，但方法 1 没有。因此，如果它们不相同，那么我想了解性能影响是什么。

Answer 1

是的。在任何一种情况下，任何特定元素被选为枢轴的概率都是 1/len(input)。 (但是，第二种方法几乎肯定会慢一个常数因子，因为它需要额外的线性传递来生成随机排列。)