arrays - 对 n 元素数组进行排序，使前 k 个元素按升序排列最低(就地算法)

Question

这是一道我被卡住的作业题。

我需要对一个 n 元素数组进行排序，使前 k 个元素最低并且按升序排列。对于k <= n/log(n)，算法应该是O(n)。

我的解决方案:我想到的一个简单的解决方案是堆化 (O(n)) 数组。然后删除 k 个元素并将堆/数组的起始索引从 0 移动到 1 - 2 - 3(依此类推，一直到 k)。这将是 O(n+k*lg(n)+k*n) = O(kn+k*lg(n))。对于给定的 k 条件，它将是 O(n^2/log(n) + n)。

另一种可能的实现方式是使用基数排序，时间复杂度为 O(n)，但我感觉这不是正确的解决方案，因为我要对整个数组进行排序，而他们只要求对 k 个元素进行排序。

您不必给我答案，提示会很有帮助。

Answer 1

我喜欢你的堆想法。我实际上认为它会在您列出的时间范围内工作，并且您的分析中存在一些小故障。

假设您执行以下操作:在您的数组中构建一个就地堆，然后将最少的 k 个元素出列，将剩余的 n - k 个元素留在数组中。如果你考虑元素将在哪里结束，你应该将数组中的 k 个最小元素按升序存储在数组的后面，而 n - k 剩余元素将按堆顺序放在前面。如果您看不到这一点，请考虑堆排序的工作原理 - 在 k 出队后，最大的 k 个元素在后面按降序排列，其余元素在前面堆排序。在这里，我们将最小堆换成了最大堆，因此出现了奇怪的顺序。结果，如果你在最后反转数组，你应该在前面有升序排列的 k 个最小元素，然后是 n - k 个剩余元素。

这将正确找到 k 个最小的元素，运行时间确定如下:

• heapify 的成本:O(n)
• k 次出队的成本:O(k log n)
• 反转数组的代价:O(n)
• 总成本:O(n + k log n)

现在，假设 k ≤ n/log n。那么运行时就是

O(n + k log n) = O(n + (n / log n) log n) = O(n)

大功告成!该算法工作得很好。另外，它需要 O(1) 的辅助空间(堆可以就地构建，并且可以在 O(1) 的空间中反转数组)。

不过，您可以做得更好。 @timrau 在评论中建议您使用 quickselect(或者更一般地说，任何线性时间选择算法)。这些算法重新排列数组，将最低的 k 个元素按某种顺序放在数组的前 k 个槽中，将剩余的 n-k 个元素按某种顺序放在最后 n-k 个槽中。这样做需要时间 O(n) 而不管 k(漂亮!)。所以假设你这样做，然后只对前 k 个元素进行排序。这需要时间 O(n + k log k)，渐近优于 O(n + k log n) 时间的基于堆的算法。

在已知的线性时间选择算法中，如果您小心的话，quickselect 和 median-of-medians 算法都可以就地实现，因此这种方法所需的总空间为 O(1)。