.NET 排序 Array.Sort<T> 實(shí)現(xiàn)示例

更新時間：2021年09月30日 10:05:19 作者：SpringLeee

System.Array.Sort<T> 是.NET內(nèi)置的排序方法, 本文就詳細(xì)的介紹一下具體使用，具有一定的參考價值，感興趣的可以了解一下

先說結(jié)果, 實(shí)際上 Array.Sort 不止使用了一種排序算法, 為了保證不同的數(shù)據(jù)量的排序場景，都能有一個高性能的表現(xiàn)，實(shí)現(xiàn)中包括了插入排序,堆排序和快速排序, 接下來從通過源碼看看它都做了哪些事情。

Array.Sort

https://source.dot.net/#System.Private.CoreLib/Array.cs,ec5718fae85b7640

public static void Sort<T>(T[] array)
{
    if (array == null)
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.array);

    if (array.Length > 1)
    {
        var span = new Span<T>(ref MemoryMarshal.GetArrayDataReference(array), array.Length);
        ArraySortHelper<T>.Default.Sort(span, null);
    }
}

這里我們對 int 數(shù)組進(jìn)行排序, 先看一下這個Sort方法, 當(dāng)數(shù)組的長度大于1時, 會先把數(shù)組轉(zhuǎn)成 Span 列表, 然后調(diào)用了內(nèi)部的ArraySortHelper的Default對象的Sort方法。

ArraySortHelper

[TypeDependency("System.Collections.Generic.GenericArraySortHelper`1")]
internal sealed partial class ArraySortHelper<T>
    : IArraySortHelper<T>
{
    private static readonly IArraySortHelper<T> s_defaultArraySortHelper = CreateArraySortHelper();

    public static IArraySortHelper<T> Default => s_defaultArraySortHelper;

    [DynamicDependency("#ctor", typeof(GenericArraySortHelper<>))]
    private static IArraySortHelper<T> CreateArraySortHelper()
    {
        IArraySortHelper<T> defaultArraySortHelper;

        if (typeof(IComparable<T>).IsAssignableFrom(typeof(T)))
        {
            defaultArraySortHelper = (IArraySortHelper<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericArraySortHelper<string>), (RuntimeType)typeof(T));
        }
        else
        {
            defaultArraySortHelper = new ArraySortHelper<T>();
        }
        return defaultArraySortHelper;
    }
}

Default 會根據(jù)是否實(shí)現(xiàn)了 IComparable<T> 接口來創(chuàng)建不同的 ArraySortHelper, 因?yàn)樯厦嫖覍nt數(shù)組進(jìn)行排序, 所以調(diào)用的是 GenericArraySortHelper 的Sort方法。

GenericArraySortHelper

https://source.dot.net/#System.Private.CoreLib/ArraySortHelper.cs,280

internal sealed partial class GenericArraySortHelper<T>
        where T : IComparable<T>
    {
    // Do not add a constructor to this class because ArraySortHelper<T>.CreateSortHelper will not execute it

    #region IArraySortHelper<T> Members

    public void Sort(Span<T> keys, IComparer<T>? comparer)
    {
        try
        {
            if (comparer == null || comparer == Comparer<T>.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<byte>));
                        if (nanLeft == keys.Length)
                        {
                            return;
                        }
                        keys = keys.Slice(nanLeft);
                    }

                    IntroSort(keys, 2 * (BitOperations.Log2((uint)keys.Length) + 1));
                }
            }
            else
            {
                ArraySortHelper<T>.IntrospectiveSort(keys, comparer.Compare);
            }
        }
        catch (IndexOutOfRangeException)
        {
            ThrowHelper.ThrowArgumentException_BadComparer(comparer);
        }
        catch (Exception e)
        {
            ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_IComparerFailed, e);
        }
    }

首先會判斷排序的類型是否是浮點(diǎn)型, 如果是的會做一些排序的調(diào)整優(yōu)化，然后調(diào)用了 IntroSort 方法，并傳入了兩個參數(shù)，第一個Keys就是數(shù)組的Span列表，那第二個是什么呢? 它是一個int類型的depthLimit參數(shù)，這里簡單點(diǎn)理解就是算出數(shù)組的深度，因?yàn)楹筮厱鶕?jù)這個值進(jìn)行遞歸操作，然后進(jìn)入到 IntroSort 方法。

IntroSort

到這個方法這里就清晰很多了, 這是Array.Sort<T> 排序的主要內(nèi)容，接著往下看

https://source.dot.net/#System.Private.CoreLib/ArraySortHelper.cs,404

 private static void IntroSort(Span<T> 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;
    }
}

第一次進(jìn)入方法時，partitionSize 就是數(shù)組的長度, 這里有一個判斷條件，如下, IntrosortSizeThreshold 是一個值為16的常量，它是一個閾值, 如果數(shù)組的長度小于等于16, 那么使用的就是插入排序(InsertionSort), 為什么是16呢？這里通過注釋了解到, 從經(jīng)驗(yàn)上來看, 16及以下得數(shù)組長度使用插入排序的效率是比較高的。

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

如果數(shù)組的長度小于等于3時, 直接進(jìn)行對比交換, 如果長度大約3并且小于等于16的話, 使用插入排序(InsertionSort), 方法內(nèi)容如下:

https://source.dot.net/#System.Private.CoreLib/ArraySortHelper.cs,537

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--;

因?yàn)楹筮吺沁f歸操作，所以每次 depthLimit 都會減1, 當(dāng)深度為0排序還沒有完成的時候，就會直接使用堆排序(HeapSort)，方法內(nèi)容如下：

https://source.dot.net/#System.Private.CoreLib/ArraySortHelper.cs,990

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;

這里調(diào)用了另外一個方法 PickPivotAndPartition,
Pivot 基準(zhǔn), Partition 分區(qū), 這就是快速排序呀！而且還是使用了尾遞歸的快速排序，其中也使用了三數(shù)取中法，方法內(nèi)容如下

https://source.dot.net/#System.Private.CoreLib/ArraySortHelper.cs,945

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;
}