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; }
InsertionSort如果数组的长度小于等于3时, 直接进行对比交换, 如果长度大约3并且小于等于16的话, 使用插入排序(InsertionSort), 方法内容如下:
private static void InsertionSort(Span<T> 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--;
因为后边是递归操作，所以每次 depthLimit 都会减1, 当深度为0排序还没有完成的时候，就会直接使用堆排序(HeapSort)，方法内容如下：
private static void HeapSort(Span<TKey> keys, Span<TValue> 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<TKey> keys, Span<TValue> 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;
这里调用了另外一个方法 PickPivotAndPartition,
Pivot 基准, Partition 分区, 这就是快速排序呀！而且还是使用了尾递归的快速排序，其中也使用了三数取中法，方法内容如下
private static int PickPivotAndPartition(Span<TKey> keys, Span<TValue> 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; }
总结本文主要介绍了System.Array.Sort<T> 排序的内部实现, 发现它使用了插入排序,堆排序和快速排序，大家有兴趣可以看一下Java或者Golang的排序实现，希望对您有用。
到此这篇关于.NET 排序 Array.Sort<T> 实现分析的文章就介绍到这了,更多相关.NET 排序 Array.Sort<T>内容请搜索脚本之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持脚本之家！
您可能感兴趣的文章: