随机QuickSort的优势是什么？

Question

在他们的书中 随机算法, Motwani和Raghavan通过描述其RANDQS函数（随机QuickSort）打开引言，其中用于将集合分为两个部分的枢轴随机选择。

一段时间以来，我一直在绞尽脑汁（诚然的能力不足）的大脑，但是我还没有看到这种算法比仅选择的中间元素（Index，而不是大小）具有什么优势。

我想我看不到的是：如果初始集合以随机顺序为单位，那么在集合中的随机位置选择元素与在固定位置选择元素之间有什么区别？

有人可以用相当简单的术语启发我吗？

Answer 1

如果输入阵列是随机分布的，则（如您指出的那样），始终在固定位置（例如中间一个）或以随机选择元素选择元素之间没有区别。

但是，如果您的输入数组并不是真正的顺序（几乎在所有实际情况下都是这种情况），则需要“ preshufle”数组，以使其中的元素以随机顺序放置，或者（等效）总是将随机元素作为枢轴。这样可以确保QuickSort的分区阶段将阵列分为几乎相等的子阵列，因此预期的运行时间仍然是$ O（n log n）$

因此，您的混乱似乎来自以下事实：您以某种方式假设（实际上）将分类算法可以期望输入阵列始终被随机分发。

Answer 2

正如Jernej指出的那样，以下假设是，输入的所有排列同样可能并不总是在现实中。第一个想法可能是输入输入数组。这将起作用，但是更容易分析随机选择枢轴的情况。这也称为 随机采样.