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

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

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

Answer 2

三件事：

你可以在列表的一次传递中获得最大值和最小值，所以实际上我们为每次传递添加 1*O(n)。然而...
最大值和最小值的平均值不保证O(nlog(n))，因为最大值和最小值的平均值不一定是中值。如果你有一个已经排序的列表 (1,10,100,1000,10000)，这实际上会给出一个 O(n^2) 的解决方案，这对于一个已经排序的列表来说真的很糟糕（而且很可能会发生）。
从统计角度来看，随机选择一个基准点很可能会给您带来接近中位数的结果。从列表中取一个随机数，50% 的时间这个数字位于列表的中间 50%，这意味着在最坏的情况下它有 75% 的列表在一侧，25% 在另一侧。显然，当我们选择更接近真实中位数时，性能会更好。

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

Why choose a random pivot in quicksort

algorithm

sorting

quicksort