c# - 按值对 对进行高效排序

Question

我正在寻找对一堆 pairs<string, float> 进行排序的最有效方法按值计算，因为我需要获得大量对中的 3 个最高条目。

我的自然 react 是使用 sortedList，但显然它只能按键排序，而且我不能使用反向列表解决方案，因为我知道字符串是唯一的，但 float 可能不是。

我忽略了任何简单有效的解决方案吗？

Answer 1

如果您只需要知道前三个值，则不需要对整个列表进行排序 - 您可以只执行一次，一次存储前三个值。这将使它成为 O(n) 而不是 O(n log n)...但是你必须自己实现它。

如果您对 O(n log n) 满意，最简单的方法可能是使用 LINQ:

var ordered = pairs.OrderBy(pair => pair.Value).Take(3).ToList();

实现类似这样的东西可能不会太难:

public static IEnumerable<TSource> TakeTop<TSource, TKey>
    (this IEnumerable<TSource> source,
     Func<TSource, TKey> keySelector,
     int count)

复杂度可能为 O(n * count)。如果我有更多时间，我会为了好玩而做...