C#排序和OrderBy比较

Question

我可以使用Sort或者OrderBy对列表进行排序，哪个更快？它们都使用相同的算法吗？

List<Person> persons = new List<Person>();
persons.Add(new Person("P005", "Janson"));
persons.Add(new Person("P002", "Aravind"));
persons.Add(new Person("P007", "Kazhal"));

1.

persons.Sort((p1,p2)=>string.Compare(p1.Name,p2.Name,true));

2.

var query = persons.OrderBy(n => n.Name, new NameComparer());

class NameComparer : IComparer<string>
{
    public int Compare(string x,string y)
    {
      return  string.Compare(x, y, true);
    }
}

- user215675

---

我很惊讶没有任何回答提到这点，但最大的区别在于：OrderBy 会创建一个已排序的数组或列表的副本，而 Sort 则是直接就地排序。 - PRMan

如题所说，我想补充一下OrderBy是稳定的排序方法，而Sort在16个元素以内也是稳定的，因为如果元素大于16个，则会切换到其他不稳定的算法。编辑：稳定指维护具有相同关键字的元素之间的相对顺序。 - Eklavyaa

@PRMan 不是的，OrderBy 创建了一个延迟枚举。只有在对返回的枚举调用 ToList 等方法时，才会得到一个排序后的副本。 - Stewart

@Stewart，您不认为在System.Core/System/Linq/Enumerable.cs中将Array.Copy或Collection.Copy复制到TElement[]的缓冲区中是一种复制吗？如果您在IEnumerable上调用ToList，则可能会同时在内存中拥有3个副本。这对于非常大的数组是一个问题，这也是我观点的一部分。此外，如果您需要多次相同的排序顺序，则一次就地调用Sort比重复对List进行排序更有效，因为它是永久性的。 - PRMan

@PRMan 哦，你的意思是内部构建了一个排序副本。但仍然不准确，因为OrderBy不会创建副本 - 据我所见，这是由GetEnumerator方法在实际开始循环遍历集合时完成的。我刚刚尝试了一下我的代码，发现从LINQ表达式中填充变量的代码几乎瞬间运行完毕，但当你进入foreach循环时，它会花费时间进行排序。我想当我有更多时间时，应该花些时间去尝试弄清楚它在幕后是如何工作的。 - Stewart

Answer 1

不，它们不是相同的算法。首先，LINQ的OrderBy方法被记录为“stable”（即如果两个项目具有相同的名称，则它们将按照其原始顺序出现）。

这还取决于您是缓冲查询还是多次迭代它（除非您缓冲结果，否则LINQ-to-Objects会根据foreach重新排序）。

对于OrderBy查询，我也会倾向于使用：

OrderBy(n => n.Name, StringComparer.{yourchoice}IgnoreCase);

(对于yourchoice中的一个，可以选择CurrentCulture，Ordinal或InvariantCulture。)

List<T>.Sort

该方法使用Array.Sort，它使用快速排序算法。该实现执行不稳定排序；也就是说，如果两个元素相等，则它们的顺序可能无法保留。与之相反，稳定排序会保留相同键的元素的顺序。

Enumerable.OrderBy

该方法执行稳定排序；也就是说，如果两个元素的键相等，则元素的顺序被保留。与之相反，不稳定排序不保留具有相同键的元素的顺序。

- Marc Gravell

---

如果你使用.NET Reflector或者ILSpy打开Enumerable.OrderBy并深入其内部实现，你会发现OrderBy排序算法是快速排序的一种变体，能够进行稳定排序（参见System.Linq.EnumerableSorter<TElement>）。因此，我们可以期望Array.Sort和Enumerable.OrderBy都具有O(N log N)的执行时间复杂度，其中N是集合中元素的数量。 - John Beyer

@Marc 我不太明白，如果两个元素相等但它们的顺序没有保留，那么差异会是什么。对于原始数据类型，这显然不是问题。但即使对于引用类型，如果我要排序，则出现在另一个名称为Marc Gravell的人之前的人名为Marc Gravell（例如 :)），那会有什么影响呢？我不是质疑你的答案/知识，而是在寻找此场景的应用。 - Mukus

@Mukus 想象一下，你按姓名（或出生日期）对公司通讯录进行排序，不可避免地会出现重复的条目。最终问题是：它们会发生什么？子顺序是否被定义？ - Marc Gravell

Answer 2

为什么不去测量它：

class Program
{
    class NameComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return string.Compare(x, y, true);
        }
    }

    class Person
    {
        public Person(string id, string name)
        {
            Id = id;
            Name = name;
        }
        public string Id { get; set; }
        public string Name { get; set; }
    }

    static void Main()
    {
        List<Person> persons = new List<Person>();
        persons.Add(new Person("P005", "Janson"));
        persons.Add(new Person("P002", "Aravind"));
        persons.Add(new Person("P007", "Kazhal"));

        Sort(persons);
        OrderBy(persons);

        const int COUNT = 1000000;
        Stopwatch watch = Stopwatch.StartNew();
        for (int i = 0; i < COUNT; i++)
        {
            Sort(persons);
        }
        watch.Stop();
        Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

        watch = Stopwatch.StartNew();
        for (int i = 0; i < COUNT; i++)
        {
            OrderBy(persons);
        }
        watch.Stop();
        Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);
    }

    static void Sort(List<Person> list)
    {
        list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
    }

    static void OrderBy(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
    }
}

在我的电脑上，以发布模式编译时，该程序会打印出：

Sort: 1162ms
OrderBy: 1269ms

---

更新:

如@Stefan建议，这里是对一个大列表进行少排序的结果:

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
    persons.Add(new Person("P" + i.ToString(), "Janson" + i.ToString()));
}

Sort(persons);
OrderBy(persons);

const int COUNT = 30;
Stopwatch watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
    Sort(persons);
}
watch.Stop();
Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

watch = Stopwatch.StartNew();
for (int i = 0; i < COUNT; i++)
{
    OrderBy(persons);
}
watch.Stop();
Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

输出：

Sort: 8965ms
OrderBy: 8460ms

在这种情况下，看起来 OrderBy 的性能更好。

---

更新2：

并使用随机名称：

List<Person> persons = new List<Person>();
for (int i = 0; i < 100000; i++)
{
    persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
}

其中：

private static Random randomSeed = new Random();
public static string RandomString(int size, bool lowerCase)
{
    var sb = new StringBuilder(size);
    int start = (lowerCase) ? 97 : 65;
    for (int i = 0; i < size; i++)
    {
        sb.Append((char)(26 * randomSeed.NextDouble() + start));
    }
    return sb.ToString();
}

返回：

Sort: 8968ms
OrderBy: 8728ms

然而，OrderBy更快。

- Darin Dimitrov

---

我认为，对一个非常小的列表（3个项目）进行1000000次排序和对一个非常大的列表（1000000个项目）进行少数几次排序有很大的区别。两者都非常重要。在实践中，列表的中等大小（什么是中等？...先暂时设定为1000个项目）最为有趣。我认为，对只有3个项目的列表进行排序没有太多意义。 - Stefan Steinegger

请注意，“更快”和“明显更快”之间存在区别。在您的最后一个例子中，差异约为0.25秒。用户会注意到吗？对于用户等待近9秒钟以获取结果是否不可接受？如果两个问题的答案都是“否”，那么从性能角度来看，选择哪个并不重要。 - Eric Lippert

请注意，此处的测试在启动秒表之前对列表进行排序，因此我们正在比较这两种算法在面对排序输入时的性能表现。这可能与它们在面对未排序输入时的相对性能差异很大。 - phoog

在我看来，这些结果相当令人惊讶，考虑到与原地的List<T>.Sort实现相比，LINQ需要额外的内存。我不确定他们是否在更新的.NET版本中改进了这一点，但在我的电脑上（i7第三代64位.NET 4.5发布版）Sort在所有情况下都优于OrderBy。此外，通过查看 OrderedEnumerable<T> 源代码，似乎它在最后调用 Quicksort 对索引数组进行原地排序之前创建了三个附加数组（首先是Buffer<T>，然后是投影键的数组，然后是索引的数组）。 - vgru

在所有这些操作之后，最后是 ToArray 调用，它创建了结果数组。内存操作和数组索引是非常快的操作，但我仍然无法找到这些结果背后的逻辑。 - vgru

Answer 3

Darin Dimitrov的回答表明，当面对已排序的输入时，OrderBy比List.Sort略快。我修改了他的代码，使其反复排序未排序的数据，结果在大多数情况下，OrderBy稍微慢一些。

此外，OrderBy测试使用ToArray强制枚举Linq枚举器，但这显然返回一个类型(Person[])与输入类型(List<Person>)不同。因此，我重新运行了测试，使用ToList而不是ToArray，得到了更大的差异：

Sort: 25175ms
OrderBy: 30259ms
OrderByWithToList: 31458ms

代码：

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

class Program
{
    class NameComparer : IComparer<string>
    {
        public int Compare(string x, string y)
        {
            return string.Compare(x, y, true);
        }
    }

    class Person
    {
        public Person(string id, string name)
        {
            Id = id;
            Name = name;
        }
        public string Id { get; set; }
        public string Name { get; set; }
        public override string ToString()
        {
            return Id + ": " + Name;
        }
    }

    private static Random randomSeed = new Random();
    public static string RandomString(int size, bool lowerCase)
    {
        var sb = new StringBuilder(size);
        int start = (lowerCase) ? 97 : 65;
        for (int i = 0; i < size; i++)
        {
            sb.Append((char)(26 * randomSeed.NextDouble() + start));
        }
        return sb.ToString();
    }

    private class PersonList : List<Person>
    {
        public PersonList(IEnumerable<Person> persons)
           : base(persons)
        {
        }

        public PersonList()
        {
        }

        public override string ToString()
        {
            var names = Math.Min(Count, 5);
            var builder = new StringBuilder();
            for (var i = 0; i < names; i++)
                builder.Append(this[i]).Append(", ");
            return builder.ToString();
        }
    }

    static void Main()
    {
        var persons = new PersonList();
        for (int i = 0; i < 100000; i++)
        {
            persons.Add(new Person("P" + i.ToString(), RandomString(5, true)));
        } 

        var unsortedPersons = new PersonList(persons);

        const int COUNT = 30;
        Stopwatch watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            Sort(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("Sort: {0}ms", watch.ElapsedMilliseconds);

        watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            OrderBy(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("OrderBy: {0}ms", watch.ElapsedMilliseconds);

        watch = new Stopwatch();
        for (int i = 0; i < COUNT; i++)
        {
            watch.Start();
            OrderByWithToList(persons);
            watch.Stop();
            persons.Clear();
            persons.AddRange(unsortedPersons);
        }
        Console.WriteLine("OrderByWithToList: {0}ms", watch.ElapsedMilliseconds);
    }

    static void Sort(List<Person> list)
    {
        list.Sort((p1, p2) => string.Compare(p1.Name, p2.Name, true));
    }

    static void OrderBy(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToArray();
    }

    static void OrderByWithToList(List<Person> list)
    {
        var result = list.OrderBy(n => n.Name, new NameComparer()).ToList();
    }
}

- phoog

---

我现在在 LinqPad 5 (.net 5) 中运行测试代码，OrderByWithToList 和 OrderBy 所需的时间相同。 - dovid

Answer 4

我认为有必要指出Sort和OrderBy之间的另一个区别：

假设存在一个Person.CalculateSalary()方法，它需要很长时间; 可能比对一个大列表进行排序的操作还要久。

对比一下：

// Option 1
persons.Sort((p1, p2) => Compare(p1.CalculateSalary(), p2.CalculateSalary()));
// Option 2
var query = persons.OrderBy(p => p.CalculateSalary()); 

选项2的性能可能更好，因为它只调用CalculateSalary方法 n 次，而Sort选项可能会根据排序算法的成功，最多调用CalculateSalary达到2n log(n)次。

- Omer Raviv

---

虽然如此，该问题有解决方案，即将数据保存在数组中，并使用Array.Sort过载，该过载接受两个数组，一个是键，另一个是值。在填充键数组时，您将调用CalculateSalary n次。显然，这并不像使用OrderBy那样方便。 - phoog

Answer 5

简而言之：

列表/数组的Sort()方法：

• 不稳定排序。
• 在原地进行。
• 使用Introsort/Quicksort算法。
• 通过提供比较器来实现自定义比较。如果比较是昂贵的，可能比OrderBy()慢（后者允许使用键，请参见下文）。

OrderBy/ThenBy()方法：

• 稳定排序。
• 非原地进行。
• 使用Quicksort算法。Quicksort算法不是稳定排序算法。这里的诀窍是：在排序时，如果两个元素具有相等的键，则比较它们的初始顺序（在排序之前存储的顺序）。
• 允许使用lambda表达式的键（例如：x => x.Id）根据值对元素进行排序。在排序之前先提取所有键。这可能比使用Sort()和自定义比较器更快。

来源： MDSN、参考源码和dotnet/coreclr代码库（GitHub）。

上述部分陈述是基于当前.NET框架实现（4.7.2）。未来可能会有所改变。

- tigrou

Answer 6

我只是想补充一下 orderby 更有用。

为什么？因为我可以这样做：

Dim thisAccountBalances = account.DictOfBalances.Values.ToList
thisAccountBalances.ForEach(Sub(x) x.computeBalanceOtherFactors())
thisAccountBalances=thisAccountBalances.OrderBy(Function(x) x.TotalBalance).tolist
listOfBalances.AddRange(thisAccountBalances)

为什么要使用复杂的比较器？只需根据一个字段进行排序即可。这里我是根据TotalBalance进行排序的。

非常简单。

使用sort无法做到这一点，我不知道为什么。但使用orderBy可以轻松实现。

至于速度，它始终是O(n)。

- user4951

---

问题：你答案中的O(n)时间（我假设）是指OrderBy还是Comparer？我认为快速排序无法达到O（N）的时间。 - Kevman