最有效的方法排序为X/N数组中的元素 - .NET

我有全都有时间戳标记的上次更新对象的数组。我想获得只包含最近更新项目的数组的子集。我将仅从50到100的数组中检索5个元素，并且性能是我的首要任务，所以我同意使用其中一个类方法对整个数组进行排序。这样做的最好方法是什么？最有效的方法排序为X/N数组中的元素 - .NET

是固定大小的数组？还是有一些物体被推到顶部？你为什么反对排序数组？ –

阵列将被固定在通过它进行排序时的大小，但我不知道这将是多大的前手。我反对排序整个事物，而不是整理它。我只是想让它排序五个元素，然后再打破。没有必要对其余的元素进行排序，因为它们不会被使用，数组也不会持久化，所以我不会看到未来的性能增益。 – evanmcdonnal

我会用一个insertion sort，打破了一旦你选择了所需数量的元素。该解决方案具有O（k * n）复杂度，其中k是要提取的元素的数量。

还有一些算法，找到一个排序的数组的第k最大元素为O（n）

一旦你找到了第K个最大元素X，你可以遍历数组，并挑选所有这比十，你都保证有完全相同的K-1元优于X.

2012-06-02 04:32:54

这看起来不错。如果没有人在接下来的几个小时内发布更好的答案，我会接受。 – evanmcdonnal

如果你只有100个元素更大的元素，那么我会简单地对它们进行排序。否则，我会使用基于堆的优先级队列实现。 O（n）来创建，每一次插入/删除都有一个与它相关的O（logn）成本。

2012-06-02 05:40:44 Kakira

回答