c# - 对数组中的 x/n 元素进行排序的最有效方法 - .NET

Question

我有一组对象，它们在上次更新时都有时间戳标记。我想获得只有最近更新的项目的数组子集。我将从 50 到 100 的数组中仅检索 5 个元素，性能是我的首要任务，因此我建议使用其中一种类方法对整个数组进行排序。这样做的最佳方法是什么？

Answer 1

一旦您选择了所需数量的元素，我将使用插入排序并中断。该解决方案具有 O(k*n) 复杂度，其中 k 是要提取的元素的数量。

还有一些算法可以在 O(n) 中找到未排序数组中的第 K 个最大元素

如何在 O(n) 中找到长度为 n 的未排序数组中的第 k 个最大元素？

一旦你找到了第 K 个最大的元素 X，你就可以遍历数组并选择所有大于 X 的元素。你可以保证恰好有 k-1 个元素优于 X。

Answer 2

如果您只有 100 个元素，那么我只需对它们进行排序。否则，我会使用基于堆的优先级队列实现。O(n) 创建，从那时起的每个插入/删除都有与之相关的 O(logn) 成本。