algorithm - 随机快速排序

Question

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

方法1：选择一个随机枢轴

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

就随机化而言，方法 1 与方法 2 相同吗？

注意：看起来 Method2 产生所有分区的可能性相同，但 method1 没有。因此，如果它们不一样，那么我想了解性能影响是什么。

Answer 1

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