.NET源代码的内部排序实现
使用JetBrains的DotPeek工具能够方便地查看.net的部分源代码。于是看了一下.NET的内部是怎样实现排序的算法。
在System.Collections.Generic 命名空间下能够看到ArraySortHelper<T>的实现。
public void Sort(T[] keys, int index, int length, IComparer<T> comparer) { try { if (comparer == null) comparer = (IComparer<T>) Comparer<T>.Default; if (BinaryCompatibility.TargetsAtLeast_Desktop_V4_5) ArraySortHelper<T>.IntrospectiveSort(keys, index, length, comparer); else ArraySortHelper<T>.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, IComparer<T> comparer) { if (length < 2) return; ArraySortHelper<T>.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<T> 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<T>.SwapIfGreater(keys, comparer, lo, hi); break; } else if (num == 3) { ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi - 1); ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper<T>.SwapIfGreater(keys, comparer, hi - 1, hi); break; } else { ArraySortHelper<T>.InsertionSort(keys, lo, hi, comparer); break; } } else if (depthLimit == 0) { ArraySortHelper<T>.Heapsort(keys, lo, hi, comparer); break; } else { --depthLimit; num = ArraySortHelper<T>.PickPivotAndPartition(keys, lo, hi, comparer); ArraySortHelper<T>.IntroSort(keys, num + 1, hi, depthLimit, comparer); } } } private static int PickPivotAndPartition(T[] keys, int lo, int hi, IComparer<T> comparer) { int index = lo + (hi - lo) / 2; ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, index); ArraySortHelper<T>.SwapIfGreater(keys, comparer, lo, hi); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index, hi); T obj = keys[index]; ArraySortHelper<T>.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<T>.Swap(keys, i, j); else break; } ArraySortHelper<T>.Swap(keys, i, hi - 1); return i; }
而.NET4.5下面使用的是还有一种排序的方案。
在排序的数字小于16个的时候,直接使用插入排序。
private static void InsertionSort(T[] keys, int lo, int hi, IComparer<T> comparer) { 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, IComparer<T> comparer, int depthLimit) { while (depthLimit != 0) { int index1 = left; int index2 = right; int index3 = index1 + (index2 - index1 >> 1); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index3); ArraySortHelper<T>.SwapIfGreater(keys, comparer, index1, index2); ArraySortHelper<T>.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<T>.DepthLimitedQuickSort(keys, left, index2, comparer, depthLimit); left = index1; } else { if (index1 < right) ArraySortHelper<T>.DepthLimitedQuickSort(keys, index1, right, comparer, depthLimit); right = index2; } if (left >= right) return; } ArraySortHelper<T>.Heapsort(keys, left, right, comparer); }
而假设大于4GB的数量时,使用堆排序。
private static void Heapsort(T[] keys, int lo, int hi, IComparer<T> comparer) { int n = hi - lo + 1; for (int i = n / 2; i >= 1; --i) ArraySortHelper<T>.DownHeap(keys, i, n, lo, comparer); for (int index = n; index > 1; --index) { ArraySortHelper<T>.Swap(keys, lo, lo + index - 1); ArraySortHelper<T>.DownHeap(keys, 1, index - 1, lo, comparer); } } private static void DownHeap(T[] keys, int i, int n, int lo, IComparer<T> 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; }
最后,附上swap函数的实现:
private static void SwapIfGreater(T[] keys, IComparer<T> comparer, 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; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。