sorting - 使用快速排序找到数组中第 k 个最小的项目 => 预期运行时间？

Question

如果我使用修改后的快速排序版本来查找数组中的第 k 个最小项，为什么预期的运行时间为 O(n)（如 Programming Pearls 书中所述）？

我正在使用的算法执行以下操作：

1) Runs quick sort on the array
2) If k is > the correct location of pivot, then run quicksort on the 2nd half.
Otherwise run it on the first half.

我的印象是这需要 O(n * logn) 的工作。

Answer 1

此链接可能有助于理解随机快速选择的证明，http ://pine.cs.yale.edu/pinewiki/QuickSelect ，

获取第 K 阶统计信息背后的想法是，选择一个枢轴，并按照快速排序的建议对数据进行分区，并找出要搜索的元素所在的分区。分区的复杂性为 O(n)。分区后，您需要选择一个结果分区进行进一步处理，这与快速排序不同，您必须同时处理这两个分区。

在下面的描述中，我不是想证明，而是想给出直观的想法来理解预期的复杂性，

为简单起见，让我们假设，在每次迭代中，pivot 将数组分成相等的两半，那么复杂度显然是 O(n)，因为

   n + (n/2) + (n/4) ... <= c.n, O(n)

为了直观理解，获得最坏情况的分区，您必须在每次迭代中处理 (n-1) 个元素，发生概率仅为 (1/n)。因此，无论如何，最坏情况的复杂度是 O(n^2)。

无论如何，如果您想要对预期的复杂性进行严格的证明，您可以通过提供的链接。

Answer 2

那不会是书中描述的算法。它更有可能在 (1)、(2) 等处进行一个分区。