一時好奇心起，想一窺.Net Framework 4.0內部究竟是使用何種算法排序。以前聽人說Framework內部是使用的快速排序，但究竟耳聽為虛，眼見為實。主要通過JetBrains dotPeek 1.2作為工具反編譯Framework的代碼進行查看，也參考了其他很多資料。本人才疏學淺，其中難免存在錯誤，希望大家不吝指教。
眾所周知，數組實質上是Array類的實例。呃，要是被代表了，可以通過如下方式驗證：
重載方法包含的參數有：
這一系列共有4個方法：
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[__DynamicallyInvokable]
public static void Sort(Array array)
{
if (array == null)
throw new ArgumentNullException("array");
Array.Sort(array, null, array.GetLowerBound(0), array.Length, null);
}
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[__DynamicallyInvokable]
[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public static void Sort(Array array, int index, int length)
{
Array.Sort(array, null, index, length, null);
}
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[__DynamicallyInvokable]
public static void Sort(Array array, IComparer comparer)
{
if (array == null)
throw new ArgumentNullException("array");
Array.Sort(array, null, array.GetLowerBound(0), array.Length, comparer);
}
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[__DynamicallyInvokable]
[TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
public static void Sort(Array array, int index, int length, IComparer comparer)
{
Array.Sort(array, null, index, length, comparer);
}
比較這4個方法，發現其歸根到底都調用了非泛型不帶關鍵字數組排序方法：
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecuritySafeCritical]
public static void Sort(Array keys, Array items, int index, int length, IComparer comparer)
{
if (keys == null)
throw new ArgumentNullException("keys");
if (keys.Rank != 1 || items != null && items.Rank != 1)
throw new RankException(Environment.GetResourceString("Rank_MultiDimNotSupported"));
if (items != null && keys.GetLowerBound(0) != items.GetLowerBound(0))
throw new ArgumentException(Environment.GetResourceString("Arg_LowerBoundsMustMatch"));
if (index < keys.GetLowerBound(0) || length < 0)
throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
if (keys.Length - (index - keys.GetLowerBound(0)) < length || items != null && index - items.GetLowerBound(0) > items.Length - length)
throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
if (length <= 1 || (comparer == Comparer.Default || comparer == null) && Array.TrySZSort(keys, items, index, index + length - 1))
return;
object[] keys1 = keys as object[];
object[] items1 = null;
if (keys1 != null)
items1 = items as object[];
if (keys1 != null && (items == null || items1 != null))
new Array.SorterObjectArray(keys1, items1, comparer).Sort(index, length);
else
new Array.SorterGenericArray(keys, items, comparer).Sort(index, length);
}
閱讀代碼，我們可以發現會首先嘗試Array的TrySZSort方法，成功則直接返回。接著當關鍵字數組為object[]且項數組為空或項數組也為object[]時，將會調用SorterObjectArray的排序方法，否則調用SorterGenericArray的排序方法
TrySZSort的方法代碼如下：
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail), SecurityCritical] [MethodImpl(MethodImplOptions.InternalCall)] private static extern bool TrySZSort(Array keys, Array items, int left, int right);
可以發現該方法由CLR內部實現，但是好在現在CoreCLR已經開源了，我們可以通過CoreCLR大致了解到這個函數是做什麼的。經過查找，發現在一個名叫ArrayHelper的類中發現該發現，代碼如下：
FCIMPL4(FC_BOOL_RET, ArrayHelper::TrySZSort, ArrayBase * keys, ArrayBase * items, UINT32 left, UINT32 right)
FCALL_CONTRACT;
VALIDATEOBJECT(keys);
VALIDATEOBJECT(items);
_ASSERTE(keys != NULL);
// <TODO>@TODO: Eventually, consider adding support for single dimension arrays with
// non-zero lower bounds. VB might care. </TODO>
if (keys->GetRank() != 1 || keys->GetLowerBoundsPtr()[0] != 0)
FC_RETURN_BOOL(FALSE);
_ASSERTE(left <= right);
_ASSERTE(right < keys->GetNumComponents() || keys->GetNumComponents() == 0);
TypeHandle keysTH = keys->GetArrayElementTypeHandle();
const CorElementType keysElType = keysTH.GetVerifierCorElementType();
if (!CorTypeInfo::IsPrimitiveType_NoThrow(keysElType))
FC_RETURN_BOOL(FALSE);
if (items != NULL) {
TypeHandle itemsTH = items->GetArrayElementTypeHandle();
if (keysTH != itemsTH)
FC_RETURN_BOOL(FALSE); // Can't currently handle sorting different types of arrays.
}
// Handle special case of a 0 element range to sort.
// Consider both Sort(array, x, x) and Sort(zeroLen, 0, zeroLen.Length-1);
if (left == right || right == 0xffffffff)
FC_RETURN_BOOL(TRUE);
switch(keysElType) {
case ELEMENT_TYPE_I1:
ArrayHelpers<I1>::IntrospectiveSort((I1*) keys->GetDataPtr(), (I1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_U1:
case ELEMENT_TYPE_BOOLEAN:
ArrayHelpers<U1>::IntrospectiveSort((U1*) keys->GetDataPtr(), (U1*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_I2:
ArrayHelpers<I2>::IntrospectiveSort((I2*) keys->GetDataPtr(), (I2*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_U2:
case ELEMENT_TYPE_CHAR:
ArrayHelpers<U2>::IntrospectiveSort((U2*) keys->GetDataPtr(), (U2*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_I4:
ArrayHelpers<I4>::IntrospectiveSort((I4*) keys->GetDataPtr(), (I4*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_U4:
ArrayHelpers<U4>::IntrospectiveSort((U4*) keys->GetDataPtr(), (U4*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_R4:
{
R4 * R4Keys = (R4*) keys->GetDataPtr();
R4 * R4Items = (R4*) (items == NULL ? NULL : items->GetDataPtr());
// Comparison to NaN is always false, so do a linear pass
// and swap all NaNs to the front of the array
left = ArrayHelpers<R4>::NaNPrepass(R4Keys, R4Items, left, right);
if(left != right) ArrayHelpers<R4>::IntrospectiveSort(R4Keys, R4Items, left, right);
break;
};
case ELEMENT_TYPE_I8:
ArrayHelpers<I8>::IntrospectiveSort((I8*) keys->GetDataPtr(), (I8*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_U8:
ArrayHelpers<U8>::IntrospectiveSort((U8*) keys->GetDataPtr(), (U8*) (items == NULL ? NULL : items->GetDataPtr()), left, right);
break;
case ELEMENT_TYPE_R8:
{
R8 * R8Keys = (R8*) keys->GetDataPtr();
R8 * R8Items = (R8*) (items == NULL ? NULL : items->GetDataPtr());
// Comparison to NaN is always false, so do a linear pass
// and swap all NaNs to the front of the array
left = ArrayHelpers<R8>::NaNPrepass(R8Keys, R8Items, left, right);
if(left != right) ArrayHelpers<R8>::IntrospectiveSort(R8Keys, R8Items, left, right);
break;
};
case ELEMENT_TYPE_I:
case ELEMENT_TYPE_U:
// In V1.0, IntPtr & UIntPtr are not fully supported types. They do
// not implement IComparable, so searching & sorting for them should
// fail. In V1.1 or V2.0, this should change.
FC_RETURN_BOOL(FALSE);
default:
_ASSERTE(!"Unrecognized primitive type in ArrayHelper::TrySZSort");
FC_RETURN_BOOL(FALSE);
}
FC_RETURN_BOOL(TRUE);
FCIMPLEND
大致可以看出，該方法的作用是對Framework的基本類型進行排序，排序也使用了內省排序。內省排序詳見後面。
我們來看一下SorterObjectArray的構造函數及Sort方法：
private object[] keys;
private object[] items;
private IComparer comparer;
internal SorterObjectArray(object[] keys, object[] items, IComparer comparer)
{
if (comparer == null)
{
comparer = Comparer.Default;
}
this.keys = keys;
this.items = items;
this.comparer = comparer;
}
構造函數很簡單，僅僅賦值字段
internal void Sort(int left, int length)
{
if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
{
this.IntrospectiveSort(left, length);
return;
}
this.DepthLimitedQuickSort(left, length + left - 1, 32);
}
初看一下代碼 ，發現關鍵語句是BinaryCompatibility.TargetsAtLeast_Desktop_V4_5，其決定了究竟使用了哪種排序方式。從字面意思上是說是否為桌面版本4.5及以上，經過驗證後也確實如此，但因為與主題關系不大，就不細說，僅簡單說下原理。
編譯器在編譯程序集時，會加上TargetFramework特性，.Network Framework通過檢測該特性來確定框架版本，如下是4.0的一個程序集示例：
private void DepthLimitedQuickSort(int left, int right, int depthLimit)
{
do
{
if (depthLimit == 0)
{
try
{
this.Heapsort(left, right);
break;
}
catch (IndexOutOfRangeException)
{
throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", new object[]
{
this.comparer
}));
}
catch (Exception innerException)
{
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException);
}
}
int num = left;
int num2 = right;
int median = Array.GetMedian(num, num2);
try
{
this.SwapIfGreaterWithItems(num, median);
this.SwapIfGreaterWithItems(num, num2);
this.SwapIfGreaterWithItems(median, num2);
}
catch (Exception innerException2)
{
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException2);
}
object obj = this.keys[median];
do
{
try
{
while (this.comparer.Compare(this.keys[num], obj) < 0)
{
num++;
}
while (this.comparer.Compare(obj, this.keys[num2]) < 0)
{
num2--;
}
}
catch (IndexOutOfRangeException)
{
throw new ArgumentException(Environment.GetResourceString("Arg_BogusIComparer", new object[]
{
this.comparer
}));
}
catch (Exception innerException3)
{
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException3);
}
if (num > num2)
{
break;
}
if (num < num2)
{
object obj2 = this.keys[num];
this.keys[num] = this.keys[num2];
this.keys[num2] = obj2;
if (this.items != null)
{
object obj3 = this.items[num];
this.items[num] = this.items[num2];
this.items[num2] = obj3;
}
}
num++;
num2--;
}
while (num <= num2);
depthLimit--;
if (num2 - left <= right - num)
{
if (left < num2)
{
this.DepthLimitedQuickSort(left, num2, depthLimit);
}
left = num;
}
else
{
if (num < right)
{
this.DepthLimitedQuickSort(num, right, depthLimit);
}
right = num2;
}
}
while (left < right);
}
調用時深度為32，每調用一次，深度減1，深度大於0時使用快速排序，當深度為0時即轉入堆排序。在使用快速排序時，選取首、尾和首尾中間三個索引中取值為中間的對象作為主元。然後取左右兩邊較長的序列進入下一輪快速排序。
用到的其余代碼如下：
internal void SwapIfGreaterWithItems(int a, int b)
{
if (a != b && this.comparer.Compare(this.keys[a], this.keys[b]) > 0)
{
object obj = this.keys[a];
this.keys[a] = this.keys[b];
this.keys[b] = obj;
if (this.items != null)
{
object obj2 = this.items[a];
this.items[a] = this.items[b];
this.items[b] = obj2;
}
}
}
private void Swap(int i, int j)
{
object obj = this.keys[i];
this.keys[i] = this.keys[j];
this.keys[j] = obj;
if (this.items != null)
{
object obj2 = this.items[i];
this.items[i] = this.items[j];
this.items[j] = obj2;
}
}
private void Heapsort(int lo, int hi)
{
int num = hi - lo + 1;
for (int i = num / 2; i >= 1; i--)
{
this.DownHeap(i, num, lo);
}
for (int j = num; j > 1; j--)
{
this.Swap(lo, lo + j - 1);
this.DownHeap(1, j - 1, lo);
}
}
private void DownHeap(int i, int n, int lo)
{
object obj = this.keys[lo + i - 1];
object obj2 = (this.items != null) ? this.items[lo + i - 1] : null;
while (i <= n / 2)
{
int num = 2 * i;
if (num < n && this.comparer.Compare(this.keys[lo + num - 1], this.keys[lo + num]) < 0)
{
num++;
}
if (this.comparer.Compare(obj, this.keys[lo + num - 1]) >= 0)
{
break;
}
this.keys[lo + i - 1] = this.keys[lo + num - 1];
if (this.items != null)
{
this.items[lo + i - 1] = this.items[lo + num - 1];
}
i = num;
}
this.keys[lo + i - 1] = obj;
if (this.items != null)
{
this.items[lo + i - 1] = obj2;
}
}
IntrospectiveSort的代碼如下:
private void IntrospectiveSort(int left, int length)
{
if (length < 2)
{
return;
}
try
{
this.IntroSort(left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(this.keys.Length));
}
catch (IndexOutOfRangeException)
{
IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer(this.comparer);
}
catch (Exception innerException)
{
throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), innerException);
}
}
private void IntroSort(int lo, int hi, int depthLimit)
{
while (hi > lo)
{
int num = hi - lo + 1;
if (num <= 16)
{
if (num == 1)
{
return;
}
if (num == 2)
{
this.SwapIfGreaterWithItems(lo, hi);
return;
}
if (num == 3)
{
this.SwapIfGreaterWithItems(lo, hi - 1);
this.SwapIfGreaterWithItems(lo, hi);
this.SwapIfGreaterWithItems(hi - 1, hi);
return;
}
this.InsertionSort(lo, hi);
return;
}
else
{
if (depthLimit == 0)
{
this.Heapsort(lo, hi);
return;
}
depthLimit--;
int num2 = this.PickPivotAndPartition(lo, hi);
this.IntroSort(num2 + 1, hi, depthLimit);
hi = num2 - 1;
}
}
}
private int PickPivotAndPartition(int lo, int hi)
{
int num = lo + (hi - lo) / 2;
this.SwapIfGreaterWithItems(lo, num);
this.SwapIfGreaterWithItems(lo, hi);
this.SwapIfGreaterWithItems(num, hi);
object obj = this.keys[num];
this.Swap(num, hi - 1);
int i = lo;
int num2 = hi - 1;
while (i < num2)
{
while (this.comparer.Compare(this.keys[++i], obj) < 0)
{
}
while (this.comparer.Compare(obj, this.keys[--num2]) < 0)
{
}
if (i >= num2)
{
break;
}
this.Swap(i, num2);
}
this.Swap(i, hi - 1);
return i;
}
在其中用到的FloorLog2代碼如下:
internal static int FloorLog2(int n)
{
int num = 0;
while (n >= 1)
{
++num;
n /= 2;
}
return num;
}
其余用到的方法請參見上面的DepthLimitedQuickSort，初始深度為長度的2的對數取下界的2倍，其流程圖如下:
[SecuritySafeCritical]
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[__DynamicallyInvokable]
public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)
{
if (array == null)
throw new ArgumentNullException("array");
if (index < 0 || length < 0)
throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
if (array.Length - index < length)
throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
if (length <= 1 || (comparer == null || comparer == Comparer<T>.Default) && Array.TrySZSort((Array) array, (Array) null, index, index + length - 1))
return;
ArraySortHelper<T>.Default.Sort(array, index, length, comparer);
}
查看ArraySortHelper<T>代碼，發現該類代碼也與泛型不帶關鍵字數組排序方法邏輯完全一致，就不再細說了。
泛型帶關鍵字數組排序方法共4個，而最終調用的是public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, IComparer<TKey> comparer)這個方法。該方法如下：
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
[SecuritySafeCritical]
public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, IComparer<TKey> comparer)
{
if (keys == null)
throw new ArgumentNullException("keys");
if (index < 0 || length < 0)
throw new ArgumentOutOfRangeException(length < 0 ? "length" : "index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
if (keys.Length - index < length || items != null && index > items.Length - length)
throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
if (length <= 1 || (comparer == null || comparer == Comparer<TKey>.Default) && Array.TrySZSort((Array) keys, (Array) items, index, index + length - 1))
return;
if (items == null)
Array.Sort<TKey>(keys, index, length, comparer);
else
ArraySortHelper<TKey, TValue>.Default.Sort(keys, items, index, length, comparer);
}
該方法在items為空時直接調用泛型帶關鍵字數組排序方法，在其他情況下調用ArraySortHelper<TKey, TValue>的排序方法。
查看ArraySortHelper<TKey, TValue>的代碼，發現該類代碼也與泛型帶關鍵字數組排序方法邏輯完全一致，就不再細說了。
ArrayList這貨雖然現在很少用了，但是畢竟了曾風光了一段時間，還是提一下，通過查看其代碼，發現底層還是調用的Array的非泛型不帶關鍵字數組的排序方法。這也不奇怪，跟List一樣，底層用的都是數組。
public virtual void Sort(int index, int count, IComparer comparer)
{
if (index < 0)
{
throw new ArgumentOutOfRangeException("index", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
}
if (count < 0)
{
throw new ArgumentOutOfRangeException("count", Environment.GetResourceString("ArgumentOutOfRange_NeedNonNegNum"));
}
if (this._size - index < count)
{
throw new ArgumentException(Environment.GetResourceString("Argument_InvalidOffLen"));
}
Array.Sort(this._items, index, count, comparer);
this._version++;
}
跟ArrayList類似，其底層調用的是Array的泛型不帶關鍵字數組的排序方法。代碼如下：
public void Sort(int index, int count, IComparer<T> comparer)
{
if (index < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
if (count < 0)
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
if (this._size - index < count)
ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);
Array.Sort<T>(this._items, index, count, comparer);
++this._version;
}
[__DynamicallyInvokable]
public void Sort(Comparison<T> comparison)
{
if (comparison == null)
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
if (this._size <= 0)
return;
Array.Sort<T>(this._items, 0, this._size, (IComparer<T>) new Array.FunctorComparer<T>(comparison));
}
通過查看代碼，發現OrderBy與OrderByDescending基本一致，都使用了OrderedEnumerable<TSource, TKey>類，代碼如下：
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
return (IOrderedEnumerable<TSource>) new OrderedEnumerable<TSource, TKey>(source, keySelector, (IComparer<TKey>) null, false);
}
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
{
return (IOrderedEnumerable<TSource>) new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, false);
}
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
return (IOrderedEnumerable<TSource>) new OrderedEnumerable<TSource, TKey>(source, keySelector, (IComparer<TKey>) null, true);
}
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> OrderByDescending<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
{
return (IOrderedEnumerable<TSource>) new OrderedEnumerable<TSource, TKey>(source, keySelector, comparer, true);
}
而OrderedEnumerable<TSource, TKey>繼承自OrderedEnumerable<TElement>，OrderedEnumerable<TSource, TKey>中排序使用了EnumerableSorter<TElement, TKey>，而EnumerableSorter<TElement, TKey>繼承自EnumerableSorter<TElement>。在EnumerableSorter<TElement>我們可以發現排序的關鍵代碼：
internal int[] Sort(TElement[] elements, int count)
{
this.ComputeKeys(elements, count);
int[] map = new int[count];
for (int index = 0; index < count; ++index)
map[index] = index;
this.QuickSort(map, 0, count - 1);
return map;
}
private void QuickSort(int[] map, int left, int right)
{
do
{
int left1 = left;
int right1 = right;
int index1 = map[left1 + (right1 - left1 >> 1)];
while (true)
{
do
{
if (left1 >= map.Length || this.CompareKeys(index1, map[left1]) <= 0)
{
while (right1 >= 0 && this.CompareKeys(index1, map[right1]) < 0)
--right1;
if (left1 <= right1)
{
if (left1 < right1)
{
int num = map[left1];
map[left1] = map[right1];
map[right1] = num;
}
++left1;
--right1;
}
else
break;
}
else
goto label_1;
}
while (left1 <= right1);
break;
label_1:
++left1;
}
if (right1 - left <= right - left1)
{
if (left < right1)
this.QuickSort(map, left, right1);
left = left1;
}
else
{
if (left1 < right)
this.QuickSort(map, left1, right);
right = right1;
}
}
while (left < right);
}
原來是快速排序。
查看代碼，發現ThenBy和ThenByDescending基本一致，都是傳入IOrderedEnumerable<TSource>，返回其CreateOrderedEnumerable方法調用。
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{ if (source == null) throw Error.ArgumentNull("source"); else
return source.CreateOrderedEnumerable<TKey>(keySelector, (IComparer<TKey>) null, false);
}
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> ThenBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
{ if (source == null) throw Error.ArgumentNull("source"); else
return source.CreateOrderedEnumerable<TKey>(keySelector, comparer, false);
}
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{ if (source == null) throw Error.ArgumentNull("source"); else
return source.CreateOrderedEnumerable<TKey>(keySelector, (IComparer<TKey>) null, true);
}
[__DynamicallyInvokable]
public static IOrderedEnumerable<TSource> ThenByDescending<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
{ if (source == null) throw Error.ArgumentNull("source"); else
return source.CreateOrderedEnumerable<TKey>(keySelector, comparer, true);
}
而在上面，我們已經發現了OrderBy與OrderByDescending都返回了OrderedEnumerable<TSource, TKey>，在其中找到CreateOrderedEnumerable方法。
IOrderedEnumerable<TElement> IOrderedEnumerable<TElement>.CreateOrderedEnumerable<TKey>(Func<TElement, TKey> keySelector, IComparer<TKey> comparer, bool descending)
{
OrderedEnumerable<TElement, TKey> orderedEnumerable = new OrderedEnumerable<TElement, TKey>(this.source, keySelector, comparer, descending);
orderedEnumerable.parent = this;
return (IOrderedEnumerable<TElement>) orderedEnumerable;
}
這說明正是在前面排序的基礎上進行再次排序。
C#集合--數組 - On the road.... - 博客園
比較排序算法 - 匠心十年 - 博客園
Introsort - Wikipedia, the free encyclopedia:
一並予以感謝
