algorithm - 为什么在快速排序中选择随机枢轴

Question

因此，随机选择一个枢轴在最坏情况下运行时间复杂度为 O(n²)，但是当枢轴被选择为列表的最小值和最大值的平均值时，您得到的最坏情况为 O (n log n).

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

在实现而不是将枢轴作为列表中的值时，它只是一个数字，因此这不是标准的快速排序，但我的问题仍然适用。

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

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²) 的影响:

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

您会发现，对于您的算法的每一次传递，正确的 部分总是只有 1 个元素。