内置.NET集合排序器的性能

enumerable.orderby()将IEnumerable<gt;拖到数组中,并使用快速排序。o(n)储存要求。它是由system.core.dll中的一个内部类完成的, EnumerableSort<TElement>.QuickSort() . 如果您有一个列表,存储成本会使它与简单的列表排序没有竞争力,因为列表<>排序到位。LINQ通常通过使用IS运算符检查IEnumerable的真正功能来进行优化。因为list<>。sort具有破坏性,所以在这里不起作用。

列出<>。排序和数组。排序使用就地快速排序。

SortedList<>对于插入具有O(n)复杂性,控制了查找插入点的O(log(n))复杂性。因此,将n个未排序的项目放入其中将花费o(n^2)。SortedDictionary<gt;使用红黑树,使insert o(log(n))的复杂性。因此,O(nlog(n))填充它,与摊余快速排序相同。

通过Reflector的快速Gander告诉我列表排序方法使用了QuickSort http://en.wikipedia.org/wiki/Quicksort 通过system.collections.generic.genericarraysorthelper

SortedList使用array.binarysearch找出在每个添加项上插入内容的位置。

枚举器没有排序逻辑

对于大多数情况,快速排序是一个很好的排序选择,但是如果您对输入数据很不走运,它可以接近o(n^2)。

如果您怀疑输入数据是 巨大的 对于快速排序来说,一堆不吉利(已经排序)的数据。一个技巧是先将数据随机化(总是很便宜),然后对随机数据进行排序。QuickSort算法可以实现一些技巧来缓解对已经排序(或接近排序)的输入数据进行排序的问题,我不知道BCL实现是否执行了这些操作。

是的,你的假设听起来不错。我做了一个小测试来证实这一点。

在5000000个整数上,

data.Sort();                           //  500 ms
data = data.OrderBy(a => a).ToList();  // 5000 ms

找出每种方法性能的一种方法是测量它:

List<int> createUnsortedList()
{
    List<int> list = new List<int>();
    for (int i = 0; i < 1000000; ++i)
        list.Add(random.Next());
    return list;
}

void Method1()
{
    List<int> list = createUnsortedList();
    list.Sort();
}

void Method2()
{
    List<int> list = createUnsortedList();
    list.OrderBy(x => x).ToList();
}

结果:

• 方法1:0.67秒(list.sort)
• 方法2:3.10秒(orderby)

这表明,即使对于非常大的列表,orderby的性能也是合理的,但不如在列表上使用内置排序方法快。这可能是因为orderby的代码稍微灵活一些——它需要一个键选择器,必须对每个元素进行评估。