algorithm - 为什么随机快速排序被认为比标准快速排序更好？

Question

用 Cormen 自己的话说 - “不同之处在于，使用确定性算法时，特定的输入可能会引发最坏情况的行为。但是，使用随机算法时，任何输入都不会总是引发最坏情况的行为。”

添加随机主元如何改变任何东西，该算法在某些特定输入下仍然会表现不佳，并且同等地考虑每种输入，这并不比标准快速排序更好，唯一的区别是我们实际上并没有这样做知道哪个特定输入将导致最坏情况的时间复杂度。那么为什么随机版本被认为更好呢？

Answer 1

考虑以下版本的快速排序，我们始终选择最后一个元素作为枢轴。现在考虑以下数组:

int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};

当使用我们的快速排序版本对该数组进行排序时，它将始终选择最小的元素作为其主元，即最后一个元素。在第一次迭代中，它将像这样更改数组:

arr = [1, 8, 7, 6, 5, 4, 3, 2, 9];

现在，它将在子数组上递归:

s1 = [1, 8, 7, 6, 5, 4, 3, 2];
s2 = [9];

在s1中，它将再次选择2作为其枢轴，只有8和2会互换位置。所以，这样的话，如果我们尝试建立一个递推关系，由于其复杂性，它将是

T(n) = T(n-1) + O(n)

对应于O(n^2)。

因此，对于此数组，标准版本始终需要 O(n^2) 时间。

在随机版本中，我们首先将最后一个元素与数组中的某个随机元素交换，然后选择它作为主元。因此，对于给定的数组，该主元将随机分割数组，很可能在中间。所以，现在的重现将是

T(n) = 2T(n/2) + O(n)

这将是O(n * Log(n))。

这就是为什么我们认为随机快速排序比标准快速排序更好，因为随机快速排序中出现错误分割的可能性非常低。