随机Quicksort

Question

两种实现随机Quicksort的方法,

方法1:选择随机数据透视

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

在随机化方面,method1与method2相同吗？

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

Answer 1

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