对数组中的 x/n 元素进行排序的最有效方法 - .NET
本文关键字：排序 有效 方法 NET 元素 数组 | 更新日期: 2023-09-27 18:36:01
我有一个对象数组，它们在上次更新时都有一个时间戳标记。我想获取数组的子集，该子集仅包含最近更新的项目。我将从 50 到 100 个数组中仅检索 5 个元素，性能是我的首要任务，因此我倾向于使用类方法之一对整个数组进行排序。最好的方法是什么？
我会使用插入排序，并在您选择了所需数量的元素后进行突破。此解决方案具有 O（k*n） 复杂度，其中 k 是要提取的元素数。
还有一些算法可以在 O（n） 中查找未排序数组中的第 K 个最大元素
如何在 O（n） 中长度为 n 的未排序数组中找到第 k 个最大的元素？
找到第 K 个最大的元素 X 后，您可以遍历数组并选择所有大于 X 的元素。保证您拥有完全优于 X 的 k-1 元素。
如果你只有 100 个元素，那么我会简单地对它们进行排序。否则，我将使用基于堆的优先级队列实现。O（n） 创建，从那时起的每个插入/删除都有与之相关的 O（logn） 成本。