一時好奇心起，想一窺.Net Framework 4.0內部究竟是使用何種算法排序。以前聽人說Framework內部是使用的快速排序，但究竟耳聽為虛，眼見為實。主要通過JetBrains dotPeek 1.2作為工具反編譯Framework的代碼進行查看，也參考了其他很多資料。本人才疏學淺，其中難免存在錯誤，希望大家不吝指教。
眾所周知，數組實質上是Array類的實例。呃，要是被代表了，可以通過如下方式驗證：
初一看，數組的排序方法似乎很多，如下圖：
但是只要我們再認真分析一下，可以發現可以根據是否為泛型，是否帶關鍵字數組將排序方法分成4類，其余的全是重載方法。即：
public static void Sort<T>(T[] array);public static void Sort(Array array);public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items);public static void Sort(Array keys[], Array items);
重載方法包含的參數有：
這一系列共有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的一個程序集示例：
DepthLimitedQuickSort從字面意思來看，是深度限制快速排序，其代碼如下：
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倍，其流程圖如下:
可以看到，不論是DepthLimitedQuickSort還是IntrospectiveSort，都是內省排序的變種。內省排序是一種混合排序算法，以快速排序開始并在超過一定的遞歸深度后轉換為堆排序。解決了快速排序在最壞情況下時間復雜度變為O(n2)的問題。隨便說一句，在STL中也使用了內省排序。
至于遞歸深度的選擇，在Framework 4.5以上，是
，以下是32。這正是O(n log n) 。對于32來說，2的32方是4G，而CLR上運行的程序分配的內存不為超過2G。（不要問我是怎么知道的，我們的項目大約在超過1.2個G的時候崩潰過，當然在不同情況下最大可用內存不一樣）
SorterGenericArray與SorterObjectArray基本一樣，只是將在SorterObjectArray的索引器替換Array的GetValue和SetValue。就不再細說了。
從上面也可以看出，非泛型不帶關鍵字數組排序方法本質上正是調用的非泛型帶關鍵字數組排序的public static void Sort(Array array, int index, int length, IComparer comparer)方法，而非泛型帶關鍵值數組的其余三個方法本質也同樣是調用該方法，而該方法在前面已經分析過了，就不再說了。
泛型不帶關鍵字數組排序方法共5個，而最終調用的是public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)這個方法。該方法如下：
[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:
一并予以感謝
新聞熱點
疑難解答
