Array.Sort 使用快速排序. 不稳定.
Order By 使用变种的快速排序. 稳定.
If you use .NET Reflector or ILSpy to crack open Enumerable.OrderBy and drill down into its internal implementation, you can see that the OrderBy sorting algorithm is a variant of QuickSort that does a stable sort. (See System.Linq.EnumerableSorter<TElement>.) Thus, Array.Sort andEnumerable.OrderBy can both be expected to have O(N log N) execution times, where N is the number of elements in the collection.
注意第二段代码中, 当c == 0且next不存在的时候, return index1 - index2;
(next 代表的是 thenby中的选择项)
这样就保证了比较相同的时候, 仍然保持了原来的先后顺序. 稳定了.
internal abstract class EnumerableSorter<TElement>
{
internal abstract void ComputeKeys(TElement[] elements, int count);
internal abstract int CompareKeys(int index1, int index2);
internal int[] Sort(TElement[] elements, int count) {
ComputeKeys(elements, count);
int[] map = new int[count];
for (int i = 0; i < count; i++) map[i] = i;
QuickSort(map, 0, count - 1);
return map;
}
void QuickSort(int[] map, int left, int right) {
do {
int i = left;
int j = right;
int x = map[i + ((j - i) >> 1)];
do {
while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
if (i > j) break;
if (i < j) {
int temp = map[i];
map[i] = map[j];
map[j] = temp;
}
i++;
j--;
} while (i <= j);
if (j - left <= right - i) {
if (left < j) QuickSort(map, left, j);
left = i;
}
else {
if (i < right) QuickSort(map, i, right);
right = j;
}
} while (left < right);
}
}
internal class EnumerableSorter<TElement, TKey> : EnumerableSorter<TElement>
{
internal Func<TElement, TKey> keySelector;
internal IComparer<TKey> comparer;
internal bool descending;
internal EnumerableSorter<TElement> next;
internal TKey[] keys;
internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement> next)
{
this.keySelector = keySelector;
this.comparer = comparer;
this.descending = descending;
this.next = next;
}
internal override void ComputeKeys(TElement[] elements, int count)
{
keys = new TKey[count];
for (int i = 0; i < count; i++) keys[i] = keySelector(elements[i]);
if (next != null) next.ComputeKeys(elements, count);
}
internal override int CompareKeys(int index1, int index2)
{
int c = comparer.Compare(keys[index1], keys[index2]);
if (c == 0)
{
if (next == null) return index1 - index2;
return next.CompareKeys(index1, index2);
}
return descending ? -c : c;
}
}
一个完整的可以运行示例如下,
测试数据演示了排序的稳定性.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Globalization;
using System.Linq.Expressions;
using System.Reflection;
using System.Runtime;
using System.Collections;
namespace ConsoleApplication1
{
internal struct Buffer<TElement>
{
internal int count;
internal TElement[] items;
/// <summary>
/// 将可枚举的泛型变成数组形式
/// </summary>
/// <param name="source"></param>
internal Buffer(IEnumerable<TElement> source)
{
TElement[] tElementArray = null;
int count = 0;
ICollection<TElement> tElements = source as ICollection<TElement>;
if (tElements == null)
{
foreach (TElement tElement in source)
{
if (tElementArray != null)
{
if ((int)tElementArray.Length == count)
{
TElement[] tElementArray1 = new TElement[count * 2];
Array.Copy(tElementArray, 0, tElementArray1, 0, count);
tElementArray = tElementArray1;
}
}
else
{
tElementArray = new TElement[4];
}
tElementArray[count] = tElement;
count++;
}
}
else
{
count = tElements.Count;
if (count > 0)
{
tElementArray = new TElement[count];
tElements.CopyTo(tElementArray, 0);
}
}
this.items = tElementArray;
this.count = count;
}
internal TElement[] ToArray()
{
if (this.count != 0)
{
if ((int)this.items.Length != this.count)
{
TElement[] tElementArray = new TElement[this.count];
Array.Copy(this.items, 0, tElementArray, 0, this.count);
return tElementArray;
}
else
{
return this.items;
}
}
else
{
return new TElement[0];
}
}
}
internal abstract class EnumerableSorter<TElement>
{
internal abstract void ComputeKeys(TElement[] elements, int count);
internal abstract int CompareKeys(int index1, int index2);
internal int[] Sort(TElement[] elements, int count)
{
ComputeKeys(elements, count);
int[] map = new int[count];
for (int i = 0; i < count; i++) map[i] = i;
QuickSort(map, 0, count - 1);
return map;
}
void QuickSort(int[] map, int left, int right)
{
do
{
int i = left;
int j = right;
int x = map[i + ((j - i) >> 1)];
do
{
while (i < map.Length && CompareKeys(x, map[i]) > 0) i++;
while (j >= 0 && CompareKeys(x, map[j]) < 0) j--;
if (i > j) break;
if (i < j)
{
int temp = map[i];
map[i] = map[j];
map[j] = temp;
}
i++;
j--;
} while (i <= j);
if (j - left <= right - i)
{
if (left < j) QuickSort(map, left, j);
left = i;
}
else
{
if (i < right) QuickSort(map, i, right);
right = j;
}
} while (left < right);
}
}
internal class EnumerableSorter<TElement, TKey> : EnumerableSorter<TElement>
{
internal Func<TElement, TKey> keySelector;
internal IComparer<TKey> comparer;
internal bool descending;
internal EnumerableSorter<TElement> next;
internal TKey[] keys;
internal EnumerableSorter(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TElement> next)
{
this.keySelector = keySelector;
this.comparer = comparer;
this.descending = descending;
this.next = next;
}
internal override void ComputeKeys(TElement[] elements, int count)
{
keys = new TKey[count];
for (int i = 0; i < count; i++) keys[i] = keySelector(elements[i]);
if (next != null) next.ComputeKeys(elements, count);
}
internal override int CompareKeys(int index1, int index2)
{
int c = comparer.Compare(keys[index1], keys[index2]);
if (c == 0)
{
if (next == null) return index1 - index2;
return next.CompareKeys(index1, index2);
}
return descending ? -c : c;
}
}
internal abstract class OrderedEnumerable<TElement> : IOrderedEnumerable<TElement>
{
internal IEnumerable<TElement> source;
public IEnumerator<TElement> GetEnumerator()
{
Buffer<TElement> buffer = new Buffer<TElement>(source);
if (buffer.count > 0)
{
EnumerableSorter<TElement> sorter = GetEnumerableSorter(null);
int[] map = sorter.Sort(buffer.items, buffer.count);
sorter = null;
for (int i = 0; i < buffer.count; i++) yield return buffer.items[map[i]];
}
}
internal abstract EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next);
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
IOrderedEnumerable<TElement> IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
OrderedEnumerable<TElement, TKey> result = new OrderedEnumerable<TElement, TKey>(source, keySelector, comparer, descending);
result.parent = this;
return result;
}
}
internal class OrderedEnumerable<TElement, TKey> : OrderedEnumerable<TElement>
{
public OrderedEnumerable<TElement> parent;
public Func<TElement, TKey> keySelector;
public IComparer<TKey> comparer;
public bool descending;
internal OrderedEnumerable(IEnumerable<TElement> source, Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
if (source == null) throw new Exception("source");
if (keySelector == null) throw new Exception("keySelector");
this.source = source;
this.parent = null;
this.keySelector = keySelector;
this.comparer = comparer != null ? comparer : Comparer<TKey>.Default;
this.descending = descending;
}
internal override EnumerableSorter<TElement> GetEnumerableSorter(EnumerableSorter<TElement> next)
{
EnumerableSorter<TElement> sorter = new EnumerableSorter<TElement, TKey>(keySelector, comparer, descending, next);
if (parent != null) sorter = parent.GetEnumerableSorter(sorter);
return sorter;
}
}
public static class MyExtension
{
public static IOrderedEnumerable<TSource> OrderByTest<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
return new OrderedEnumerable<TSource, TKey>(source, keySelector, null, false);
}
public static IOrderedEnumerable<TSource> OrderByTest<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
{
return new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, false);
}
public static IOrderedEnumerable<TSource> ThenByTest<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
if (source == null) throw new ArgumentNullException("source");
return source.CreateOrderedEnumerable<TKey>(keySelector, null, false);
}
public static IOrderedEnumerable<TSource> ThenByTest<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
{
if (source == null) throw new ArgumentNullException("source");
return source.CreateOrderedEnumerable<TKey>(keySelector, comparer, false);
}
}
class User
{
public string Name;
public int Age;
public string Tag;
public override string ToString()
{
return $"Name={Name}, Age={Age}, Tag={Tag} ";
}
}
class Program
{
static void Main(string[] args)
{
var data = new User[] {
new User { Name="C", Age=3 },
new User { Name="C", Age=5,Tag="b" }, //通过tag验证稳定性. 前面的还在前面.
new User { Name="C", Age=5,Tag="a" },
new User { Name="D", Age=8 },
new User { Name="B", Age=6 },
new User { Name="A", Age=7 },
};
var r = data.OrderByTest(x=>x.Name).ThenByTest(x=>x.Age).ToArray();
foreach (var item in r)
{
Console.WriteLine(item);
}
Console.ReadKey();
}
}
}
