C#是否有类似于std::nth_element的等效函数？

Question

我正在将一些C++代码移植到C#。

C#是否有与std::nth_element()等效的功能，还是我需要自己实现？

- Drew Dormann

Answer 1

我猜想您正在寻找一个访问器，它通过对集合进行部分排序来返回无序集合的第N个元素。当您有一个非常大的集合并且基于某个排序谓词感兴趣其中的一个元素时，这往往是有用的。

据我所知，.NET BCL或LINQ扩展都没有提供等效的方法。所有排序方法（包括Enumerable.OrderBy）都会对集合进行完整排序。

如果您需要一个高效的Nth版本，则需要在IEnumerable上编写自己的扩展方法。如果您要自己编写，可以查看Quick Select算法，其性能为O(n)。

如果暴力版本足够，请使用LINQ：

var someCollection = new []{ 5, 2, 8, 9, 0, 1, 3, 12, 4 };

var fifthItem = someCollection.NthItem(5);

public static class NthExtensions 
{
    public static T NthItem(this IEnumerable<T> coll, int n) 
    {
        return coll.OrderBy(x => x).Skip(n - 1).First();
    }
}

- LBushkin

Answer 2

不，它不会。你需要手写选择算法（最好使用快速选择）。

- Dario

Answer 3

没有直接的等价物。您可以潜在地使用LINQ的OrderBy和Take/Skip在任何IEnumerable上实现相同的目标，但是整个集合将在此过程中被排序。

- Reed Copsey

---

我在想，如果OrderBy是通过函数式实现的（例如通过归并排序），那么take/skip与惰性求值的组合是否实际上只会执行所请求的部分排序。例如，在Haskell中，head (sort list))是查找列表最小值的有效O(n)方法。有什么提示吗？ - Dario

@Dario: 理论上讲，它是有可能的，但当前的实现并没有。 - Reed Copsey

虽然这本来很有趣 :) - Dario