algorithm - 使用快速排序获取数组的 k 个最小元素

Question

如何使用快速排序从未排序的数组中找到 k 个最小的元素(而不只是排序并取 k 个最小的元素)？最坏情况下的运行时间是否相同 O(n^2)？

Answer 1

您可以优化快速排序，您所要做的就是在您的分区位于位置 k 之前，不要对数组的其他部分运行递归药水，而不是“第一”部分。如果您不需要对输出进行排序，则可以到此为止。

警告:前面的分析不严谨。

但是，我认为最坏情况下的时间复杂度仍然是 O(n^2)。当您总是选择最大或最小的元素作为您的主元，并且您陷入了冒泡排序(即您无法选择分而治之的主元)时，就会发生这种情况。

另一种解决方案(如果此集合的唯一目的是挑选出 k 个最小元素)是使用有限树高的最小堆 ciel(log(k))(或恰好是 k 个节点)。所以现在，对于最小堆中的每个插入，插入的最长时间是 O(n*log(k)) 和删除相同(相对于 O(n*log(n )) 在完整的堆排序中)。这将在线性时间最坏情况下按排序顺序返回数组。与合并排序相同。