这是一个我被卡住的家庭作业问题。
我需要对一个有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个元素。
你不必给我答案，只要给点提示就可以了。
我喜欢你的堆的想法。实际上，我认为它可以在你列出的时间范围内工作，你的分析中有一点小故障。
假设您做了以下操作:在数组中构建一个就地堆，然后将最小k个元素取出队列，将剩下的n- k个元素保留在数组中。如果你考虑元素的最终位置，你应该把数组中最小的k个元素按升序存储在数组的后面，剩下的n - k个元素按堆的顺序存储在数组的前面。如果您看不清楚，请考虑一下堆排序是如何工作的——在k个去队列之后，最大的k个元素在后面按降序排列，剩下的元素在前面按堆顺序排列。这里，我们把最小堆换成了最大堆，因此排序很奇怪。因此，如果您在最后反转数组，您应该在前面按升序排列k个最小的元素，然后是剩下的n - k个元素。
这将正确地找到k个最小的元素，并且运行时间确定如下:
- 堆化成本:0 (n)
- k次排队花费:O(k log n)
- 数组反转的代价:O(n)
- 总成本:O(n + k log n)
现在，假设k ≤n/log n，则运行时间为
O (n + k O (log n)) = O (n + n/log n O (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)时间算法渐近地更好。
在已知的线性时间选择算法中，如果你小心的话，快速选择和中位数的中间值算法都可以就地实现，所以这种方法所需的总空间是O(1)。
我突然想到，你可以用稍微修改的堆选择算法来实现这一点，它是O(n log k).虽然逐渐比Quickselect的O(n)复杂度"差"，但当k与n相比非常小时，堆选择可以优于Quickselect。但是，如果要从100万个列表中选择前1000个项目，堆选择几乎肯定会更快。
无论如何，要做到这一点，您在数组的前面构建一个大小为k的max-heap(使用标准BuildHeap函数)，从数组中的前k项开始。这需要O(k)然后，像这样处理数组中其余的项:for (i = k; i < length; ++i)
{
if (array[i] < array[0]) // If item is smaller than largest item on heap
{
// put large item at the current position
temp = array[i];
array[i] = array[0];
// put new item at the top of heap and sift it down
array[0] = temp;
SiftDown(0);
}
}
这将花费O(n log k)时间，但限制因素实际上是你必须在条件中执行代码的次数。只有当一个项小于堆中已经存在的最大项时，这个步骤才会进行处理。最坏的情况是当数组是反向排序的时候。否则它会出奇的快。
完成后，最小的k个元素位于数组的前面。
然后你必须对它们排序，这是O(k log k)
所以完整的过程是O(k + n log k + k log k).同样，当k比n小得多时，这比快速选择要快得多。