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)。分区后，您需要仅选择一个结果分区进行进一步处理，这与快速排序不同，在快速排序中您必须处理两者。

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

为了简单起见，让我们假设，在每次迭代中，枢轴将数组分成两半，那么复杂度显然是 O(n)，如下所示

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

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

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