.NET 排序 Array.Sort<T> 实现示例_实用技巧_

 public static void Sort(T[] array) { if (array == null) ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array); if (array.Length > 1) { var span = new Span(ref MemoryMarshal.GetArrayDataReference(array), array.Length); ArraySortHelper.Default.Sort(span, null); } }

 [TypeDependency("System.Collections.Generic.GenericArraySortHelper`1")] internal sealed partial class ArraySortHelper : IArraySortHelper { private static readonly IArraySortHelper s_defaultArraySortHelper = CreateArraySortHelper(); public static IArraySortHelper Default => s_defaultArraySortHelper; [DynamicDependency("#ctor", typeof(GenericArraySortHelper<>))] private static IArraySortHelper CreateArraySortHelper() { IArraySortHelper defaultArraySortHelper; if (typeof(IComparable).IsAssignableFrom(typeof(T))) { defaultArraySortHelper = (IArraySortHelper)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericArraySortHelper), (RuntimeType)typeof(T)); } else { defaultArraySortHelper = new ArraySortHelper(); } return defaultArraySortHelper; } }

 internal sealed partial class GenericArraySortHelper where T : IComparable { // Do not add a constructor to this class because ArraySortHelper.CreateSortHelper will not execute it #region IArraySortHelper Members public void Sort(Span keys, IComparer? comparer) { try { if (comparer == null || comparer == Comparer.Default) { if (keys.Length > 1) { // For floating-point, do a pre-pass to move all NaNs to the beginning // so that we can do an optimized comparison as part of the actual sort // on the remainder of the values. if (typeof(T) == typeof(double) || typeof(T) == typeof(float) || typeof(T) == typeof(Half)) { int nanLeft = SortUtils.MoveNansToFront(keys, default(Span)); if (nanLeft == keys.Length) { return; } keys = keys.Slice(nanLeft); } IntroSort(keys, 2 * (BitOperations.Log2((uint)keys.Length) + 1)); } } else { ArraySortHelper.IntrospectiveSort(keys, comparer.Compare); } } catch (IndexOutOfRangeException) { ThrowHelper.ThrowArgumentException_BadComparer(comparer); } catch (Exception e) { ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e); } }

 private static void IntroSort(Span keys, int depthLimit) { Debug.Assert(!keys.IsEmpty); Debug.Assert(depthLimit >= 0); int partitionSize = keys.Length; while (partitionSize > 1) { if (partitionSize <= Array.IntrosortSizeThreshold) { if (partitionSize == 2) { SwapIfGreater(ref keys[0], ref keys[1]); return; } if (partitionSize == 3) { ref T hiRef = ref keys[2]; ref T him1Ref = ref keys[1]; ref T loRef = ref keys[0]; SwapIfGreater(ref loRef, ref him1Ref); SwapIfGreater(ref loRef, ref hiRef); SwapIfGreater(ref him1Ref, ref hiRef); return; } InsertionSort(keys.Slice(0, partitionSize)); return; } if (depthLimit == 0) { HeapSort(keys.Slice(0, partitionSize)); return; } depthLimit--; int p = PickPivotAndPartition(keys.Slice(0, partitionSize)); // Note we've already partitioned around the pivot and do not have to move the pivot again. IntroSort(keys[(p+1)..partitionSize], depthLimit); partitionSize = p; } }

 if (partitionSize <= Array.IntrosortSizeThreshold) { if (partitionSize == 2) { SwapIfGreater(ref keys[0], ref keys[1]); return; } if (partitionSize == 3) { ref T hiRef = ref keys[2]; ref T him1Ref = ref keys[1]; ref T loRef = ref keys[0]; SwapIfGreater(ref loRef, ref him1Ref); SwapIfGreater(ref loRef, ref hiRef); SwapIfGreater(ref him1Ref, ref hiRef); return; } InsertionSort(keys.Slice(0, partitionSize)); return; }

 private static void InsertionSort(Span keys) { for (int i = 0; i < keys.Length - 1; i++) { T t = Unsafe.Add(ref MemoryMarshal.GetReference(keys), i + 1); int j = i; while (j >= 0 && (t == null || LessThan(ref t, ref Unsafe.Add(ref MemoryMarshal.GetReference(keys), j)))) { Unsafe.Add(ref MemoryMarshal.GetReference(keys), j + 1) = Unsafe.Add(ref MemoryMarshal.GetReference(keys), j); j--; } Unsafe.Add(ref MemoryMarshal.GetReference(keys), j + 1) = t!; } } HeapSort if (depthLimit == 0) { HeapSort(keys.Slice(0, partitionSize)); return; } depthLimit--;

 private static void HeapSort(Span keys, Span values) { Debug.Assert(!keys.IsEmpty); int n = keys.Length; for (int i = n >> 1; i >= 1; i--) { DownHeap(keys, values, i, n); } for (int i = n; i > 1; i--) { Swap(keys, values, 0, i - 1); DownHeap(keys, values, 1, i - 1); } } private static void DownHeap(Span keys, Span values, int i, int n) { TKey d = keys[i - 1]; TValue dValue = values[i - 1]; while (i <= n >> 1) { int child = 2 * i; if (child < n && (keys[child - 1] == null || LessThan(ref keys[child - 1], ref keys[child]))) { child++; } if (keys[child - 1] == null || !LessThan(ref d, ref keys[child - 1])) break; keys[i - 1] = keys[child - 1]; values[i - 1] = values[child - 1]; i = child; } keys[i - 1] = d; values[i - 1] = dValue; } QuickSort int p = PickPivotAndPartition(keys.Slice(0, partitionSize), values.Slice(0, partitionSize)); IntroSort(keys[(p+1)..partitionSize], values[(p+1)..partitionSize], depthLimit); partitionSize = p;

 private static int PickPivotAndPartition(Span keys, Span values) { Debug.Assert(keys.Length >= Array.IntrosortSizeThreshold); int hi = keys.Length - 1; // Compute median-of-three. But also partition them, since we've done the comparison. int middle = hi >> 1; // Sort lo, mid and hi appropriately, then pick mid as the pivot. SwapIfGreaterWithValues(keys, values, 0, middle); // swap the low with the mid point SwapIfGreaterWithValues(keys, values, 0, hi); // swap the low with the high SwapIfGreaterWithValues(keys, values, middle, hi); // swap the middle with the high TKey pivot = keys[middle]; Swap(keys, values, middle, hi - 1); int left = 0, right = hi - 1; // We already partitioned lo and hi and put the pivot in hi - 1. And we pre-increment & decrement below. while (left < right) { if (pivot == null) { while (left < (hi - 1) && keys[++left] == null) ; while (right > 0 && keys[--right] != null) ; } else { while (GreaterThan(ref pivot, ref keys[++left])) ; while (LessThan(ref pivot, ref keys[--right])) ; } if (left >= right) break; Swap(keys, values, left, right); } // Put pivot in the right location. if (left != hi - 1) { Swap(keys, values, left, hi - 1); } return left; }