使用JetBrains的DotPeek工具能够方便地查看.net的部分源代码。于是看了一下.NET的内部是怎样实现排序的算法。
在System.Collections.Generic 命名空间下能够看到ArraySortHelper<T>的实现。
public void Sort(T[] keys, int index, int length, IComparercomparer) { try { if (comparer == null) comparer = (IComparer ) Comparer .Default; if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) ArraySortHelper .IntrospectiveSort(keys, index, length, comparer); else ArraySortHelper .DepthLimitedQuickSort(keys, index, length + index - 1, comparer, 32); } catch (IndexOutOfRangeException ex) { IntrospectiveSortUtilities.ThrowOrIgnoreBadComparer((object) comparer); } catch (Exception ex) { throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_IComparerFailed"), ex); } }
发如今.NET4.5以上的版本号，開始使用一种叫做 Introspective Sort的排序方法。
internal static void IntrospectiveSort(T[] keys, int left, int length, IComparercomparer) { if (length < 2) return; ArraySortHelper .IntroSort(keys, left, length + left - 1, 2 * IntrospectiveSortUtilities.FloorLog2(keys.Length), comparer); } private static void IntroSort(T[] keys, int lo, int hi, int depthLimit, IComparer comparer) { for (; hi > lo; { int num; hi = num - 1; } ) { int num = hi - lo + 1; if (num <= 16) { if (num == 1) break; if (num == 2) { ArraySortHelper .SwapIfGreater(keys, comparer, lo, hi); break; } else if (num == 3) { ArraySortHelper .SwapIfGreater(keys, comparer, lo, hi - 1); ArraySortHelper .SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper .SwapIfGreater(keys, comparer, hi - 1, hi); break; } else { ArraySortHelper .InsertionSort(keys, lo, hi, comparer); break; } } else if (depthLimit == 0) { ArraySortHelper .Heapsort(keys, lo, hi, comparer); break; } else { --depthLimit; num = ArraySortHelper .PickPivotAndPartition(keys, lo, hi, comparer); ArraySortHelper .IntroSort(keys, num + 1, hi, depthLimit, comparer); } } } private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer comparer) { int index = lo + (hi - lo) / 2; ArraySortHelper .SwapIfGreater(keys, comparer, lo, index); ArraySortHelper .SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper .SwapIfGreater(keys, comparer, index, hi); T obj = keys[index]; ArraySortHelper .Swap(keys, index, hi - 1); int i = lo; int j = hi - 1; while (i < j) { do ; while (comparer.Compare(keys[++i], obj) < 0); do ; while (comparer.Compare(obj, keys[--j]) < 0); if (i < j) ArraySortHelper .Swap(keys, i, j); else break; } ArraySortHelper .Swap(keys, i, hi - 1); return i; }
而.NET4.5下面使用的是还有一种排序的方案。
在排序的数字小于16个的时候，直接使用插入排序。
private static void InsertionSort(T[] keys, int lo, int hi, IComparercomparer) { for (int index1 = lo; index1 < hi; ++index1) { int index2 = index1; T x; for (x = keys[index1 + 1]; index2 >= lo && comparer.Compare(x, keys[index2]) < 0; --index2) keys[index2 + 1] = keys[index2]; keys[index2 + 1] = x; } }
而假设大于16个的时候，且当递归深度在32次之内的话（也就是数字小于4GB的数量时），使用高速排序。
internal static void DepthLimitedQuickSort(T[] keys, int left, int right, IComparercomparer, int depthLimit) { while (depthLimit != 0) { int index1 = left; int index2 = right; int index3 = index1 + (index2 - index1 >> 1); ArraySortHelper .SwapIfGreater(keys, comparer, index1, index3); ArraySortHelper .SwapIfGreater(keys, comparer, index1, index2); ArraySortHelper .SwapIfGreater(keys, comparer, index3, index2); T obj1 = keys[index3]; do { while (comparer.Compare(keys[index1], obj1) < 0) ++index1; while (comparer.Compare(obj1, keys[index2]) < 0) --index2; if (index1 <= index2) { if (index1 < index2) { T obj2 = keys[index1]; keys[index1] = keys[index2]; keys[index2] = obj2; } ++index1; --index2; } else break; } while (index1 <= index2); --depthLimit; if (index2 - left <= right - index1) { if (left < index2) ArraySortHelper .DepthLimitedQuickSort(keys, left, index2, comparer, depthLimit); left = index1; } else { if (index1 < right) ArraySortHelper .DepthLimitedQuickSort(keys, index1, right, comparer, depthLimit); right = index2; } if (left >= right) return; } ArraySortHelper .Heapsort(keys, left, right, comparer); }
而假设大于4GB的数量时，使用堆排序。
private static void Heapsort(T[] keys, int lo, int hi, IComparer最后，附上swap函数的实现：comparer) { int n = hi - lo + 1; for (int i = n / 2; i >= 1; --i) ArraySortHelper .DownHeap(keys, i, n, lo, comparer); for (int index = n; index > 1; --index) { ArraySortHelper .Swap(keys, lo, lo + index - 1); ArraySortHelper .DownHeap(keys, 1, index - 1, lo, comparer); } } private static void DownHeap(T[] keys, int i, int n, int lo, IComparer comparer) { T x = keys[lo + i - 1]; for (; i <= n / 2; { int num; i = num; } ) { num = 2 * i; if (num < n && comparer.Compare(keys[lo + num - 1], keys[lo + num]) < 0) ++num; if (comparer.Compare(x, keys[lo + num - 1]) < 0) keys[lo + i - 1] = keys[lo + num - 1]; else break; } keys[lo + i - 1] = x; }
private static void SwapIfGreater(T[] keys, IComparercomparer, int a, int b) { if (a == b || comparer.Compare(keys[a], keys[b]) <= 0) return; T obj = keys[a]; keys[a] = keys[b]; keys[b] = obj; } private static void Swap(T[] a, int i, int j) { if (i == j) return; T obj = a[i]; a[i] = a[j]; a[j] = obj; }