一時(shí)好奇心起，想一窺.Net Framework 4.0內(nèi)部究竟是使用何種算法排序。以前聽(tīng)人說(shuō)Framework內(nèi)部是使用的快速排序，但究竟耳聽(tīng)為虛，眼見(jiàn)為實(shí)。主要通過(guò)JetBrains dotPeek 1.2作為工具反編譯Framework的代碼進(jìn)行查看，也參考了其他很多資料。本人才疏學(xué)淺，其中難免存在錯(cuò)誤，希望大家不吝指教。
眾所周知，數(shù)組實(shí)質(zhì)上是Array類(lèi)的實(shí)例。呃，要是被代表了，可以通過(guò)如下方式驗(yàn)證：
初一看，數(shù)組的排序方法似乎很多，如下圖：
但是只要我們?cè)僬J(rèn)真分析一下，可以發(fā)現(xiàn)可以根據(jù)是否為泛型，是否帶關(guān)鍵字?jǐn)?shù)組將排序方法分成4類(lèi)，其余的全是重載方法。即：
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);
重載方法包含的參數(shù)有：
這一系列共有4個(gè)方法：
[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個(gè)方法，發(fā)現(xiàn)其歸根到底都調(diào)用了非泛型不帶關(guān)鍵字?jǐn)?shù)組排序方法：
[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);}
閱讀代碼，我們可以發(fā)現(xiàn)會(huì)首先嘗試Array的TrySZSort方法，成功則直接返回。接著當(dāng)關(guān)鍵字?jǐn)?shù)組為object[]且項(xiàng)數(shù)組為空或項(xiàng)數(shù)組也為object[]時(shí)，將會(huì)調(diào)用SorterObjectArray的排序方法，否則調(diào)用SorterGenericArray的排序方法
TrySZSort的方法代碼如下：
[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail), SecurityCritical][MethodImpl(MethodImplOptions.InternalCall)]PRivate static extern bool TrySZSort(Array keys, Array items, int left, int right);
可以發(fā)現(xiàn)該方法由CLR內(nèi)部實(shí)現(xiàn)，但是好在現(xiàn)在CoreCLR已經(jīng)開(kāi)源了，我們可以通過(guò)CoreCLR大致了解到這個(gè)函數(shù)是做什么的。經(jīng)過(guò)查找，發(fā)現(xiàn)在一個(gè)名叫ArrayHelper的類(lèi)中發(fā)現(xiàn)該發(fā)現(xiàn)，代碼如下：
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
大致可以看出，該方法的作用是對(duì)Framework的基本類(lèi)型進(jìn)行排序，排序也使用了內(nèi)省排序。內(nèi)省排序詳見(jiàn)后面。
我們來(lái)看一下SorterObjectArray的構(gòu)造函數(shù)及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;}
構(gòu)造函數(shù)很簡(jiǎn)單，僅僅賦值字段
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);}
初看一下代碼 ，發(fā)現(xiàn)關(guān)鍵語(yǔ)句是BinaryCompatibility.TargetsAtLeast_Desktop_V4_5，其決定了究竟使用了哪種排序方式。從字面意思上是說(shuō)是否為桌面版本4.5及以上，經(jīng)過(guò)驗(yàn)證后也確實(shí)如此，但因?yàn)榕c主題關(guān)系不大，就不細(xì)說(shuō)，僅簡(jiǎn)單說(shuō)下原理。
編譯器在編譯程序集時(shí)，會(huì)加上TargetFramework特性，.Network Framework通過(guò)檢測(cè)該特性來(lái)確定框架版本，如下是4.0的一個(gè)程序集示例：
DepthLimitedQuickSort從字面意思來(lái)看，是深度限制快速排序，其代碼如下：
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); }
調(diào)用時(shí)深度為32，每調(diào)用一次，深度減1，深度大于0時(shí)使用快速排序，當(dāng)深度為0時(shí)即轉(zhuǎn)入堆排序。在使用快速排序時(shí)，選取首、尾和首尾中間三個(gè)索引中取值為中間的對(duì)象作為主元。然后取左右兩邊較長(zhǎng)的序列進(jìn)入下一輪快速排序。
用到的其余代碼如下：
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;}
其余用到的方法請(qǐng)參見(jiàn)上面的DepthLimitedQuickSort，初始深度為長(zhǎng)度的2的對(duì)數(shù)取下界的2倍，其流程圖如下:
可以看到，不論是DepthLimitedQuickSort還是IntrospectiveSort，都是內(nèi)省排序的變種。內(nèi)省排序是一種混合排序算法，以快速排序開(kāi)始并在超過(guò)一定的遞歸深度后轉(zhuǎn)換為堆排序。解決了快速排序在最壞情況下時(shí)間復(fù)雜度變?yōu)镺(n2)的問(wèn)題。隨便說(shuō)一句，在STL中也使用了內(nèi)省排序。
至于遞歸深度的選擇，在Framework 4.5以上，是
，以下是32。這正是O(n log n) 。對(duì)于32來(lái)說(shuō)，2的32方是4G，而CLR上運(yùn)行的程序分配的內(nèi)存不為超過(guò)2G。（不要問(wèn)我是怎么知道的，我們的項(xiàng)目大約在超過(guò)1.2個(gè)G的時(shí)候崩潰過(guò)，當(dāng)然在不同情況下最大可用內(nèi)存不一樣）
SorterGenericArray與SorterObjectArray基本一樣，只是將在SorterObjectArray的索引器替換Array的GetValue和SetValue。就不再細(xì)說(shuō)了。
從上面也可以看出，非泛型不帶關(guān)鍵字?jǐn)?shù)組排序方法本質(zhì)上正是調(diào)用的非泛型帶關(guān)鍵字?jǐn)?shù)組排序的public static void Sort(Array array, int index, int length, IComparer comparer)方法，而非泛型帶關(guān)鍵值數(shù)組的其余三個(gè)方法本質(zhì)也同樣是調(diào)用該方法，而該方法在前面已經(jīng)分析過(guò)了，就不再說(shuō)了。
泛型不帶關(guān)鍵字?jǐn)?shù)組排序方法共5個(gè)，而最終調(diào)用的是public static void Sort<T>(T[] array, int index, int length, IComparer<T> comparer)這個(gè)方法。該方法如下：
[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>代碼，發(fā)現(xiàn)該類(lèi)代碼也與泛型不帶關(guān)鍵字?jǐn)?shù)組排序方法邏輯完全一致，就不再細(xì)說(shuō)了。
泛型帶關(guān)鍵字?jǐn)?shù)組排序方法共4個(gè)，而最終調(diào)用的是public static void Sort<TKey, TValue>(TKey[] keys, TValue[] items, int index, int length, IComparer<TKey> comparer)這個(gè)方法。該方法如下：
[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為空時(shí)直接調(diào)用泛型帶關(guān)鍵字?jǐn)?shù)組排序方法，在其他情況下調(diào)用ArraySortHelper<TKey, TValue>的排序方法。
查看ArraySortHelper<TKey, TValue>的代碼，發(fā)現(xiàn)該類(lèi)代碼也與泛型帶關(guān)鍵字?jǐn)?shù)組排序方法邏輯完全一致，就不再細(xì)說(shuō)了。
ArrayList這貨雖然現(xiàn)在很少用了，但是畢竟了曾風(fēng)光了一段時(shí)間，還是提一下，通過(guò)查看其代碼，發(fā)現(xiàn)底層還是調(diào)用的Array的非泛型不帶關(guān)鍵字?jǐn)?shù)組的排序方法。這也不奇怪，跟List一樣，底層用的都是數(shù)組。
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類(lèi)似，其底層調(diào)用的是Array的泛型不帶關(guān)鍵字?jǐn)?shù)組的排序方法。代碼如下：
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));}
通過(guò)查看代碼，發(fā)現(xiàn)OrderBy與OrderByDescending基本一致，都使用了OrderedEnumerable<TSource, TKey>類(lèi)，代碼如下：
[__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>繼承自O(shè)rderedEnumerable<TElement>，OrderedEnumerable<TSource, TKey>中排序使用了EnumerableSorter<TElement, TKey>，而EnumerableSorter<TElement, TKey>繼承自EnumerableSorter<TElement>。在EnumerableSorter<TElement>我們可以發(fā)現(xiàn)排序的關(guān)鍵代碼：
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);}
原來(lái)是快速排序。
查看代碼，發(fā)現(xiàn)ThenBy和ThenByDescending基本一致，都是傳入IOrderedEnumerable<TSource>，返回其CreateOrderedEnumerable方法調(diào)用。
[__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);}
而在上面，我們已經(jīng)發(fā)現(xiàn)了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;}
這說(shuō)明正是在前面排序的基礎(chǔ)上進(jìn)行再次排序。
C#集合--數(shù)組 - On the road.... - 博客園
比較排序算法 - 匠心十年 - 博客園
Introsort - Wikipedia, the free encyclopedia:
一并予以感謝
新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
