C# Sort 和 OrderBy 比较

C# Sort and OrderBy comparison

提问by user215675

I can sort a list using Sort or OrderBy. Which one is faster? Are both working on same algorithm?

我可以使用 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.

1.

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

2.

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);
    }
}

采纳答案by Darin Dimitrov

Why not measure it:

为什么不测量它：

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();
    }
}

On my computer when compiled in Release mode this program prints:

在我的计算机上以 Release 模式编译时，此程序打印：

Sort: 1162ms
OrderBy: 1269ms

---

---

UPDATE:

更新：

As suggested by @Stefan here are the results of sorting a big list fewer times:

正如@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);

Prints:

印刷：

Sort: 8965ms
OrderBy: 8460ms

In this scenario it looks like OrderBy performs better.

在这种情况下，看起来 OrderBy 表现更好。

---

---

UPDATE2:

更新2：

And using random names:

并使用随机名称：

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

Where:

在哪里：

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();
}

Yields:

产量：

Sort: 8968ms
OrderBy: 8728ms

Still OrderBy is faster

仍然 OrderBy 更快

回答by Marc Gravell

No, they aren't the same algorithm. For starters, the LINQ OrderByis documented as stable(i.e. if two items have the same Name, they'll appear in their original order).

不，它们不是相同的算法。对于初学者，LINQOrderBy被记录为稳定的（即，如果两个项目具有相同的Name，它们将以其原始顺序出现）。

It also depends on whether you buffer the query vs iterate it several times (LINQ-to-Objects, unless you buffer the result, will re-order per foreach).

它还取决于您是缓冲查询还是对其进行多次迭代（LINQ-to-Objects，除非您缓冲结果，否则将重新排序 per foreach）。

For the OrderByquery, I would also be tempted to use:

对于OrderBy查询，我也很想使用：

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

(for {yourchoice}one of CurrentCulture, Ordinalor InvariantCulture).

（对{yourchoice}之一CurrentCulture，Ordinal或InvariantCulture）。

List<T>.Sort

List<T>.Sort

This method uses Array.Sort, which uses the QuickSort algorithm. This implementation performs an unstable sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

此方法使用 Array.Sort，它使用 QuickSort 算法。此实现执行不稳定的排序；也就是说，如果两个元素相等，它们的顺序可能不会被保留。相反，稳定排序保留相等元素的顺序。

Enumerable.OrderBy

Enumerable.OrderBy

This method performs a stable sort; that is, if the keys of two elements are equal, the order of the elements is preserved. In contrast, an unstable sort does not preserve the order of elements that have the same key. sort; that is, if two elements are equal, their order might not be preserved. In contrast, a stable sort preserves the order of elements that are equal.

此方法执行稳定排序；也就是说，如果两个元素的键相等，则保留元素的顺序。相反，不稳定排序不会保留具有相同键的元素的顺序。种类; 也就是说，如果两个元素相等，它们的顺序可能不会被保留。相反，稳定排序保留相等元素的顺序。

回答by Omer Raviv

I think it's important to note another difference between Sortand OrderBy:

我认为重要的是要注意Sort和之间的另一个区别OrderBy：

Suppose there exists a Person.CalculateSalary()method, which takes a lot of time; possibly more than even the operation of sorting a large list.

假设有一个Person.CalculateSalary()方法，它需要很多时间；甚至可能比对大列表进行排序的操作还要多。

Compare

相比

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

Option 2may have superior performance, because it only calls the CalculateSalarymethod ntimes, whereas the Sortoption might call CalculateSalaryup to 2nlog(n)times, depending on the sort algorithm's success.

选项 2可能具有更好的性能，因为它只调用该CalculateSalary方法n次，而该Sort选项可能CalculateSalary最多调用2 nlog( n)次，具体取决于排序算法的成功。

回答by icaptan

you should calculate the complexity of algorithms used by the methods OrderBy and Sort. QuickSort has a complexity of n (log n) as i remember, where n is the length of the array.

您应该计算 OrderBy 和 Sort 方法使用的算法的复杂性。我记得 QuickSort 的复杂度为 n (log n)，其中 n 是数组的长度。

i've searched for orderby's too, but i could not find any information even in msdn library. if you have not any same values and sorting related to only one property, i prefer to use Sort() method; if not than use OrderBy.

我也搜索过 orderby，但即使在 msdn 库中也找不到任何信息。如果您没有任何与一个属性相关的相同值和排序，我更喜欢使用 Sort() 方法；如果不是，请使用 OrderBy。

回答by phoog

Darin Dimitrov's answer shows that OrderByis slightly faster than List.Sortwhen faced with already-sorted input. I modified his code so it repeatedly sorts the unsorted data, and OrderByis in most cases slightly slower.

Darin Dimitrov 的回答表明，这OrderBy比List.Sort面对已经排序的输入时略快。我修改了他的代码，因此它反复对未排序的数据进行排序，并且OrderBy在大多数情况下会稍微慢一些。

Furthermore, the OrderBytest uses ToArrayto force enumeration of the Linq enumerator, but that obviously returns a type (Person[]) which is different from the input type (List<Person>). I therefore re-ran the test using ToListrather than ToArrayand got an even bigger difference:

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

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

The code:

编码：

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();
    }
}

回答by user4951

I just want to add that orderby is way more useful.

我只想补充一点，orderby 更有用。

Why? Because I can do this:

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

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

Why complicated comparer? Just sort based on a field. Here I am sorting based on TotalBalance.

为什么要复杂的比较器？只需根据字段进行排序。这里我根据 TotalBalance 进行排序。

Very easy.

好简单。

I can't do that with sort. I wonder why. Do fine with orderBy.

我不能用排序来做到这一点。我想知道为什么。用 orderBy 做得很好。

As for speed it's always O(n).

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

回答by tigrou

In a nutshell :

简而言之 ：

List/Array Sort() :

列表/数组排序（）：

• Unstable sort.
• Done in-place.
• Use Introsort/Quicksort.
• Custom comparison is done by providing a comparer. If comparison is expensive, it might be slower than OrderBy() (which allow to use keys, see below).

• 不稳定排序。
• 就地完成。
• 使用 Introsort/Quicksort。
• 自定义比较是通过提供比较器来完成的。如果比较代价高昂，它可能比 OrderBy() （允许使用键，见下文）慢。

OrderBy/ThenBy() :

OrderBy/ThenBy() ：

• Stable sort.
• Not in-place.
• Use Quicksort. Quicksort is not a stable sort. Here is the trick : when sorting, if two elements have equal key, it compares their initial order (which has been stored before sorting).
• Allows to use keys (using lambdas) to sort elements on their values (eg : x => x.Id). All keys are extracted first before sorting. This might result in better performance than using Sort() and a custom comparer.

• 稳定排序。
• 没有到位。
• 使用快速排序。快速排序不是一种稳定的排序。这是技巧：排序时，如果两个元素具有相同的键，则比较它们的初始顺序（在排序之前已存储）。
• 允许使用键（使用 lambdas）对元素的值进行排序（例如 : x => x.Id）。在排序之前首先提取所有键。与使用 Sort() 和自定义比较器相比，这可能会带来更好的性能。

Sources: MDSN, reference sourceand dotnet/coreclrrepository (GitHub).

来源： MDSN、参考源和dotnet/coreclr存储库 (GitHub)。

Some of the statements listed above are based on current .NET framework implementation (4.7.2). It might change in the future.

上面列出的一些语句基于当前的 .NET 框架实现 (4.7.2)。未来可能会改变。