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

So choosing a pivot at random has O(n²) running at worst case but when the pivot is chosen as the average of min value and max value of the list you get a worst case 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)

Your algorithm suffers O(n²) if you choose average of min value and max value as pivot when the list contains the following elements:

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

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