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

Answer 1

为什么不衡量它：

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

在我的电脑在Release模式下编译该程序打印时：

Sort: 1162ms 
OrderBy: 1269ms 

---

UPDATE：

正如所建议的@斯蒂芬在这里是少数次排列大列表的结果：

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 

在这种情况下，它看起来像排序依据执行得更好。

---

UPDATE2：

而且使用随机的名字：

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 

仍然排序依据是更快

Answer 2

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

它也取决于你是否缓冲查询与迭代它几次（LINQ到对象，除非你缓冲结果，将按照foreach重新排序）。

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

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

（为{yourchoice}的CurrentCulture，Ordinal或InvariantCulture一个）。

List<T>.Sort

该方法使用的Array.Sort，其 使用快速排序算法。这个 执行执行不稳定的 排序;也就是说，如果两个元素是 相等，则它们的顺序可能不会被保存为 。相反，稳定的分类 保留了 相等的元素的顺序。

Enumerable.OrderBy

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

Answer 3

我觉得要注意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方法ñ倍，而Sort选项可能会调用CalculateSalary高达2n log(n)倍，这取决于排序算法的成功。

Answer 4

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

我已经搜索了orderby's，但我甚至在msdn库中都找不到任何信息。 如果你没有任何相同的值和排序相关的只有一个属性，我更喜欢使用 Sort（）方法;如果不是，则使用OrderBy。

Answer 5

Darin Dimitrov的回答显示OrderBy在面对已排序的输入时比List.Sort稍快。我修改了他的代码，以便重复排序未排序的数据，并且在大多数情况下，它会稍微慢一些。

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