为什么在快速排序中选择随机主元

Question

因此，随机选择一个主元在最坏情况下运行时间为 O(n ² )，但是当将主元选择为列表的最小值和最大值的平均值时，您会得到最坏情况 O(n log n)。

当然，由于查找最小值和最大值，每次递归都会增加 2*O(n)，而不是随机生成器的常数 O(1)。当将其实现为枢轴时，您将在递归树的叶子处对列表进行排序，而不是在标准算法中将元素从根到叶子进行排序。

当实现而不是枢轴作为列表上的值时，它只是一个与之比较的数字，所以这不是标准的快速排序，但我的问题仍然适用。

下面是我写得不好的伪代码：

func sort(List n):
    if n.length < 2
     return n;
    min = n.minValue
    max = n.maxValue
    avg = (min+max) /2 
    List left = list of elements in n less than avg
    List right = list of elements in n greater than avg
    sort(left)
    sort(right)

Answer 1

当列表包含以下元素时，如果选择最小值和最大值的平均值作为基准，则算法的复杂度为 O(n ^{2 )：}

1, 3, 7, 15, 31, 63, ..., 2 ⁿ -1

您可能会发现，对于算法的每次传递，该right部分始终只有 1 个元素。