为什么选择Quicksort中的随机数据透视 [英] Why choose a random pivot in quicksort

问题描述

因此，随机选择一个枢轴会使O（n ² ）在最坏的情况下运行，但是当选择该枢轴作为列表的最小值和最大值的平均值时，您会得到最坏的情况O （n log n）。

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).

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

Of course there are the added 2*O(n) on each recursion due to finding the min and max values as opposed to the constant O(1) of the random generator has. When implementing this as the pivot you get the list sorted at the leaves of the recursion tree instead in the standard algorithm elements get sorted from the root to leaves.

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

When implementing instead of the pivot being a value on the list it is just a number compared to so this is not the standard quicksort but my question still applies.

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

Below is my poorly written pseudo code:

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)

推荐答案

当列表包含以下元素时，如果选择最小值和最大值的平均值作为枢轴，则您的算法将遭受O（n ² ） ：

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个元素。

You could find that for each pass of your algorithm, the right part always has only 1 element.

这篇关于为什么选择Quicksort中的随机数据透视的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！