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

Question

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

Answer 1

我会使用 insertion sort并在您选择了所需数量的元素后退出。该解决方案的复杂度为 O(k*n)，其中 k 是要提取的元素数。

也有在O(n)的未排序数组中找到第K大元素的算法

How to find the kth largest element in an unsorted array of length n in O(n)?

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